淺談壓縮感知（二）：理論基礎(chǔ)

淺談壓縮感知（二）：理論基礎(chǔ)

主要內(nèi)容：

信號(hào)的稀疏表示編碼測(cè)量（采樣過程） 恢復(fù)算法（非線性） 一、信號(hào)與圖像的稀疏表示

在DSP（數(shù)字信號(hào)處理）中，有個(gè)很重要的概念：變換域（某個(gè)線性空間：一組基函數(shù)支撐起來的空間）

一般而言，我們的信號(hào)都是在時(shí)域或空域中來表示，其實(shí)我們可以在其他變換域中通過某些正交基函數(shù)的線性組合來表示信號(hào)。如：sinusoids, wavelets, curvelets, Gabor functions,. . .

對(duì)于某個(gè)變換域或空間，其基函數(shù)是確定的，只要得到系數(shù)α的這一組值，即可通過該系數(shù)向量來表示信號(hào)。

那么系數(shù)α該怎么求呢？

說了這么多，為什么要通過變換域的系數(shù)來表示信號(hào)呢？

很明顯，系數(shù)向量α的大小遠(yuǎn)小于原始信號(hào)，這一個(gè)壓縮和降維的過程（稀疏性），有利于存儲(chǔ)、傳輸和處理。

下面以圖片為例，介紹傳統(tǒng)的圖像表示方法DCT和現(xiàn)代的圖像表示方法小波變換：

Classical Image Representation: DCT

Discrete Cosine Transform (DCT)

Basically a real-valued Fourier transform (sinusoids)

如上圖所示，左邊為原始圖像，右邊為DCT變換后的圖像。

該圖像表示二維的頻率幅值系數(shù)，可以看出，右下角的大部分系數(shù)接近于0。也就是說圖像的大部分能量都集中在左上角的低頻部分（稀疏性），

因此我們只要保留左上角的信息（壓縮），就可以很好地重建出左邊的圖像。（有損）

這也就是JEPG圖像壓縮標(biāo)準(zhǔn)的基礎(chǔ)：DCT變換。

DCT重建（反變換）的圖像特點(diǎn)：平滑區(qū)域表現(xiàn)很好，邊緣可能會(huì)模糊或出現(xiàn)振鈴（因?yàn)槟承└哳l信號(hào)丟失）

Modern Image Representation: 2D Wavelets

有關(guān)小波變換的知識(shí)，這里就不詳述，可以參考：http://www.zhihu.com/topic/19621077/top-answers

如上圖所示，左邊為原始圖像，中間為尺度圖像，右邊為小波變換后的系數(shù)結(jié)構(gòu)

系數(shù)框架：大系數(shù)很少，小系數(shù)很多（稀疏性）

這也是JPEG2000壓縮標(biāo)準(zhǔn)的基礎(chǔ)：小波變換。

小波變換重建（反變換）的圖像特點(diǎn)：平滑區(qū)域表現(xiàn)很好，邊緣更加尖銳（在邊緣處理上，比DCT好）

小波變換的圖像重建：

小波系數(shù)的分布：

小波變換的重建：

這一部分主要介紹了變換域，以及信號(hào)在變換域的稀疏表示，并以圖像的DCT和小波變換為例，來闡述信號(hào)在變換域的稀疏性。

稀疏性的作用總結(jié)：

壓縮去噪降維二、編碼測(cè)量

跟傳統(tǒng)采集不同，壓縮感知采集的不是像素點(diǎn)，而是一組線性組合的測(cè)量值。

下面的公式表示每一個(gè)測(cè)量值yi的計(jì)算過程，f表示信號(hào)，Φ表示測(cè)量矩陣，兩者的內(nèi)積之和即為yi。

經(jīng)過M次測(cè)量之后，即得到所需要的M個(gè)測(cè)量數(shù)據(jù)Y。

問題是測(cè)量矩陣應(yīng)該怎么選擇呢？

為了能夠重構(gòu)信號(hào)，測(cè)量矩陣的選擇尤其重要，矩陣需要滿足與信號(hào)的稀疏表示基Ψ不相關(guān)。（RIP性質(zhì)，具體不詳述）

實(shí)驗(yàn)證明：高斯隨機(jī)矩陣、一致球矩陣、二值隨機(jī)矩陣、局部傅立葉矩陣、局部哈達(dá)瑪矩陣以及托普利茲矩陣等能在很大概率上滿足上述條件。

?

測(cè)量公式如下：

三、稀疏重建算法

假設(shè)信號(hào)是K-sparse，測(cè)量矩陣是高斯隨機(jī)矩陣，現(xiàn)在通過采集獲得了M個(gè)測(cè)量值，我們?nèi)绾位謴?fù)出我們的信號(hào)呢？

測(cè)量過程：

重建過程：（數(shù)學(xué)建模：L1 Minimization，當(dāng)然還有其他方法，后續(xù)再敘述）

需要多少個(gè)測(cè)量值才能夠有效地恢復(fù)出信號(hào)呢？一個(gè)、兩個(gè)很明顯是不行的，N個(gè)顯然就沒有了壓縮的意義，那么至少多少才合適呢？

下面的公式給出了一個(gè)估計(jì)值：

變換域重建：

舉例：