來源 | 網絡

智庫 | 云腦智庫(CloudBrain-TT)

云圈 | 進“云腦智庫微信群”,請加微信:15881101905,備注您的研究方向

 壓縮感知（壓縮傳感，Compressive Sensing）理論是近年來信號處理領域誕生的一種新的信號處理理論，由D. Donoho(美國科學院院士)、E. Candes(Ridgelet, Curvelet創始人)及華裔科學家T. Tao(2006年菲爾茲獎獲得者)等人提出，自誕生之日起便極大地吸引了相關研究人員的關注。網站http://dsp.rice.edu/cs上可以獲取大量相關的論文。

那什么叫壓縮感知？為什么它的出現吸引了那么多的目光？

還記得我們在信號與信息處理有關課程里面必講的一個知識嗎？它可謂是現代數字信號處理系統理論建立的一個功臣之一。沒錯，就是能將物理世界和數字世界建立連接的采樣定理：奈奎斯特采樣定理（Shannon-Nyquist采樣定理）。其要求：在進行模擬/數字信號的轉換過程中，當采樣頻率fs.max大于信號中最高頻率fmax的2倍時，采樣之后的數字信號完整地保留了原始信號中的信息。

而壓縮感知的出現，告訴我們：如果信號在某一個正交空間具有稀疏性（即可壓縮性），就能以較低的頻率（遠低于奈奎斯特采樣頻率）采樣該信號，并可能以高概率精確的重建該信號。

在上面所說的一篇科普文章中提到：所謂壓縮感知，最核心的概念在于試圖從原理上降低對一個信號進行測量的成本。比如說，一個信號包含一千個數據，那么按照傳統的信號處理理論，至少需要做一千次測量才能完整的復原這個信號。這就相當于是說，需要有一千個方程才能精確地解出一千個未知數來。但是壓縮感知的想法是假定信號具有某種特點（比如文中所描述得在小波域上系數稀疏的特點），那么就可以只做三百次測量就完整地復原這個信號（這就相當于只通過三百個方程解出一千個未知數）。

在cvchina里面有一篇很熱的文章《稀疏表達：向量、矩陣與張量》，呵呵，有點深，我看不懂，但里面開篇的幾張圖像吸引了我：

首先是圖像恢復，由左側圖像恢復出右側結果：

然后是類似的圖像inpainting

然后是圖像去模糊，左上為輸入模糊圖像，右下為輸出清晰圖像及估計的相機運動（其實是PSF），中間均為迭代過程:

再然后是物體檢測（自行車），左側輸入圖像，中間為位置概率圖，右側為檢測結果

當然我個人還推薦Yi Ma的sparse face，這個在對抗噪聲的效果上很棒，比如下圖中左側的那張噪聲圖像（你能辨認是哪位不？這方法可以！）

       上面的結果都很amazing，但是怎么實現的我就不知道了。原博主既然擺在那，就表明了它是稀疏表達的功勞了。

  簡單地說，壓縮感知理論指出：只要信號是可壓縮的或在某個變換域是稀疏的，那么就可以用一個與變換基不相關的觀測矩陣將變換所得高維信號投影到一個低維空間上，然后通過求解一個優化問題就可以從這些少量的投影中以高概率重構出原信號，可以證明這樣的投影包含了重構信號的足夠信息。

       在該理論框架下，采樣速率不再取決于信號的帶寬，而在很大程度上取決于兩個基本準則：稀疏性和非相關性，或者稀疏性和等距約束性。

壓縮感知理論主要包括三部分：

（1）信號的稀疏表示；

（2）設計測量矩陣，要在降低維數的同時保證原始信號x的信息損失最小；

（3）設計信號恢復算法，利用M個觀測值無失真地恢復出長度為N的原始信號。

理論依據：

（1）設長度為N的信號X在某個正交基Ψ上是K-稀疏的（即含有k個非零值）；

（2）如果能找到一個與Ψ不相關（不相干）的觀測基Φ；

（3）用觀測基Φ觀測原信號得到長度M的一維測量值M個觀測值Y，K<M<<N；

（4）那么就可以利用最優化方法從觀測值Y中高概率恢復X。

數學表達：

       設x為長度N的一維信號，稀疏度為k（即含有k個非零值），A為M×N的二維矩陣（M<N），y=Φx為長度M的一維測量值。壓縮感知問題就是已知測量值y和測量矩陣Φ的基礎上，求解欠定方程組y=Φx得到原信號x。Φ的每一行可以看作是一個傳感器（Sensor），它與信號相乘，拾?。ˋcquisition）了信號的一部分信息。而這一部分信息足以代表原信號，并能找到一個算法來高概率恢復原信號。

        一般的自然信號x本身并不是稀疏的，需要在某種稀疏基上進行稀疏表示，x=Ψs，Ψ為稀疏基矩陣，s為稀疏系數（s只有K個是非零值（K<<N）。

      壓縮感知方程為y=Φx=ΦΨs=Θs。

       將原來的測量矩陣Φ變換為Θ=ΦΨ（稱之為傳感矩陣），解出s的逼近值s’，則原信號x’ = Ψs’。

1、信號的稀疏表示

信號的稀疏性簡單理解為信號中非0元素數目較少，或者說大多數系數為0（或者絕對值較?。?/span>

自然界存在的真實信號一般不是絕對稀疏的，而是在某個變換域下近似稀疏，即為可壓縮信號。或者說從理論上講任何信號都具有可壓縮性，只要能找到其相應的稀疏表示空間，就可以有效地進行壓縮采樣。信號的稀疏性或可壓縮性是壓縮感知的重要前提和理論基礎。

稀疏表示的意義：只有信號是K稀疏的（且K<M<<N），才有可能在觀測M個觀測值時，從K個較大的系數重建原始長度為N的信號。也就是當信號有稀疏展開時，可以丟掉小系數而不會失真。

我們知道，長度為N的信號X可以用一組基Ψ^T=[Ψ₁,…, Ψ_M]的線性組合來表示：

x=Ψs，Ψ為稀疏基NxN矩陣，s為稀疏系數（N維向量），當信號X在某個基Ψ上僅有 K<<N個非零系數或遠大于零的系數s時，稱Ψ為信號X的稀疏基。我們需要做的就是合理地選擇稀疏基，使得信號的稀疏系數個數盡可能少。

再啰嗦點的話：如果長度為N的信號X，在變換域Φ中只有K個系數不為零（或者明顯大于其他系數），且K<<N，那么可以認為信號X在Φ域中是稀疏的并可稱為K-稀疏（不是嚴格的定義）。那么在該域下，我們如果只保留這M個大系數，丟棄其他的系數，則可以減小儲存該信號需要的空間，達到了壓縮（有損壓縮）的目的。同時，以這M個系數可以重構原始信號X，不過一般而言得到的是X的一個逼近。

我們應該熟悉JPEG跟JPEG2000的區別吧，JPEG的核心算法是DCT，而后者是DWT，本質上，這兩種處理方法都是將信號從一個域變換到另外一個域（把坐標系進行旋轉，將信號投影到不同的基上），從而獲得信號的稀疏表示，即用最少的系數來表示信號，不過DWT比DCT更加稀疏而已。信號不同，對應最稀疏表達的基也會不同，比如，對于一維信號可能小波基是最稀疏的，而對于圖像而言，可能那些Curvelet和contourlet是最優的，對于有些信號，也有可能需要將幾種基結合起來才是最優的。稀疏分解是找到信號的最稀疏最有效的表達。

信號在某種表示方式下的稀疏性，是壓縮感知應用的理論基礎，經典的稀疏化的方法有離散余弦變換（DCT）、傅里葉變換（FFT）、離散小波變換（DWT）等。

最近幾年，對稀疏表示研究的另一個熱點是信號在冗余字典下的稀疏分解。這是一種全新的信號表示理論：用超完備的冗余函數庫取代基函數，稱之為冗余字典，字典中的元素被稱為原子。目前信號在冗余字典下的稀疏表示的研究集中在兩個方面：一是如何構造一個適合某一類信號的冗余字典，二是如何設計快速有效的稀疏分解算法。目前常用的稀疏分解算法大致可分為匹配追蹤（Matching Pursuit）和基追蹤（Basis Pursuit）兩大類。

2、信號的觀測矩陣

觀測矩陣（也稱測量矩陣）MxN（M<<N）是用來對N維的原信號進行觀測得到M維的觀測向量Y，然后可以利用最優化方法從觀測值Y中高概率重構X。也就是說原信號X投影到這個觀測矩陣（觀測基）上得到新的信號表示Y。

觀測矩陣的設計目的是如何采樣得到M個觀測值，并保證從中能重構出長度為N的信號X或者稀疏基Ψ下等價的稀疏系數向量。

為了保證能夠從觀測值準確重構信號，其需要滿足一定的限制：觀測基矩陣與稀疏基矩陣的乘積滿足RIP性質（有限等距性質）。這個性質保證了觀測矩陣不會把兩個不同的K稀疏信號映射到同一個集合中（保證原空間到稀疏空間的一一映射關系），這就要求從觀測矩陣中抽取的每M個列向量構成的矩陣是非奇異的。

在CS編碼測量模型中并不是直接測量稀疏信號X本身， 而是將信號投影到一組測量矩陣Φ上而得到測量值y。即，用一個與變換矩陣不相關的MxN（M<<N）測量矩陣Φ對信號x進行線性投影，得到線性測量值y：y=Φx ;

測量值y是一個M維向量，這樣使測量對象從N維降為M維。測量矩陣的設計要求信號從x轉換為y的過程中，所測量到的K個測量值不會破壞原始信號的信息，以保證信號可以精確重構。

由于信號x是是可稀疏表示的: x=Ψs，上式可以表示為下式：

y=Φx=ΦΨs=Θs

其中Φ是一個MxN矩陣。上式中，方程的個數遠小于未知數的個數，方程無確定解，無法重構信號。但是，由于信號是K稀疏，若上式中的Φ滿足有限等距性質(Restricted Isometry Property，簡稱RIP)，則K個系數就能夠從M個測量值準確重構（得到一個最優解）。RIP性質的等價條件是測量矩陣Φ和稀疏基Ψ不相關。

如果稀疏基和觀測基不相關，則很大程度上保證了RIP性。CandeS和Tao等證明:獨立同分布的高斯隨機測量矩陣可以成為普適的壓縮感知測量矩陣。則一般用隨機高斯矩陣作為觀測矩陣。目前常用的測量矩陣還有隨機貝努利矩陣、部分正交矩陣、托普利茲和循環矩陣和稀疏隨機矩陣等，這里不一一列舉了。

3、信號的重構算法

當矩陣Φ滿足RIP準則時。壓縮感知理論能夠通過對上式的逆問題先求解稀疏系數s，然后將稀疏度為K的信號x從M維的測量投影值y中正確地恢復出來。解碼的最直接方法是通過l₀范數（0-范數，也就是向量y?中非零元素的個數）下求解的最優化問題：

從而得到稀疏系數s的估計s’。則原信號x’ = Ψs’。由于上式的求解是個NP難問題（在多項式時間內難以求解，甚至無法驗證解的可靠性）。L₁最小范數下在一定條件下和L₀最小范數具有等價性，可得到相同的解。那么上式轉化為L₁最小范數下的最優化問題：

L1范數最小化是通過用L1范數來近似0范數，取1而不取1/2,2/3或者其他值，是因為1范數最小化是凸優化問題，可以將求解過程轉化成有一個線性規劃問題。L₁最小范數下最優化問題又稱為基追蹤(BP)，其常用實現算法有：內點法和梯度投影法。內點法速度慢，但得到的結果十分準確：而梯度投影法速度快，但沒有內點法得到的結果準確 。

目前，壓縮感知的重構算法主要分為兩大類：

（1）貪婪算法，它是通過選擇合適的原子并經過一系列的逐步遞增的方法實現信號矢量的逼近，此類算法主要包括匹配跟蹤算法、正交匹配追蹤算法、補空間匹配追蹤算法等。

（2）凸優化算法，它是把0范數放寬到1范數通過線性規劃求解的，此類算法主要包括梯度投影法、基追蹤法、最小角度回歸法等。

凸優化算法比貪婪算法所求的解更加精確，但是需要更高的計算復雜度。

－ The End －

聲明：歡迎轉發本號原創內容，轉載和摘編需經本號授權并標注原作者和信息來源為云腦智庫。本公眾號目前所載內容為本公眾號原創、網絡轉載或根據非密公開性信息資料編輯整理，相關內容僅供參考及學習交流使用。由于部分文字、圖片等來源于互聯網，無法核實真實出處，如涉及相關爭議，請跟我們聯系。我們致力于保護作者知識產權或作品版權，本公眾號所載內容的知識產權或作品版權歸原作者所有。本公眾號擁有對此聲明的最終解釋權。

投稿/招聘/推廣/合作/入群/贊助 請加微信：15881101905，備注關鍵詞

微群關鍵詞：天線、射頻微波、雷達通信電子戰、芯片半導體、信號處理、軟件無線電、測試制造、相控陣、EDA仿真、通導遙、學術前沿、知識服務、合作投資.

“閱讀是一種習慣，分享是一種美德，我們是一群專業、有態度的知識傳播者.”