淺談壓縮感知（二）：理論基礎

主要內(nèi)容：

信號的稀疏表示編碼測量（采樣過程） 恢復算法（非線性） 一、信號與圖像的稀疏表示

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

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

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

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

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

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

下面以圖片為例，介紹傳統(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圖像壓縮標準的基礎：DCT變換。

DCT重建（反變換）的圖像特點：平滑區(qū)域表現(xiàn)很好，邊緣可能會模糊或出現(xiàn)振鈴（因為某些高頻信號丟失）

Modern Image Representation: 2D Wavelets

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

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

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

這也是JPEG2000壓縮標準的基礎：小波變換。

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

小波變換的圖像重建：

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

小波變換的重建：

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

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

壓縮去噪降維二、編碼測量

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

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

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

問題是測量矩陣應該怎么選擇呢？

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

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

?

測量公式如下：

三、稀疏重建算法

假設信號是K-sparse，測量矩陣是高斯隨機矩陣，現(xiàn)在通過采集獲得了M個測量值，我們?nèi)绾位謴统鑫覀兊男盘柲兀?/p>

測量過程：

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

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

下面的公式給出了一個估計值：

變換域重建：

舉例：