壓縮感知理論及應用

1、壓縮感知理論及應用壓縮感知理論及應用 匯報人：# 1 背景與現(xiàn)狀 1.1 問題背景 1.2 研究現(xiàn)狀 2 壓縮感知理論 2.1 理論框架概述 2.2 信號稀疏表示 2.3 觀測矩陣設計 2.4 信號重構(gòu)算法 3 應用與展望 3.1 應用舉例 3.2 總結(jié)展望 壓縮感知理論及應用壓縮感知理論及應用 1 背景與現(xiàn)狀 1.1 問題背景 隨著信息技術的飛速發(fā)展，人們對信息的需求量日益增加，所需 攜帶信息的信號帶寬越來越寬，故在信息獲取中對采樣速率和處 理速度等提出更高的要求。而在傳統(tǒng)信息獲取中存在以下問題： l 在奈奎斯特采樣定理為基礎的傳統(tǒng)信號處理框架中，若從采樣 的離散信號中無失真的恢復模擬信號，

2、采樣速率必須至少是信號 帶寬的兩倍。隨著模擬信號帶寬越來越寬，采樣速率更高，對信 號處理的軟硬件設計更困難。 l 實際應用中，為了降低存儲，處理和傳輸?shù)某杀荆２捎脡嚎s 的方式以較少的比特數(shù)表示信號，大量的非重要的數(shù)據(jù)被拋棄， 這帶來大量的資源浪費。 于是可提出問題： 存不存在新的數(shù)據(jù)采集和處理的方法，使得在保證信 息不損失的況下，遠低于奈奎斯特采樣定理要求的速率采樣信號，獲取 少量的數(shù)據(jù)就可以重構(gòu)信號？ 近些年出現(xiàn)的一種新的理論壓縮感知（Compressed Sensing,CS） 表明這種實現(xiàn)是可能的。 壓縮感知理論指出：如果信號是可壓縮的或在某個變換域是稀疏的， 那么就可以用一個與變換基

3、不相關的觀測矩陣將變換所得高維信號投 影到一個低維空間上，然后通過求解一個優(yōu)化問題就可以從這些少量 的投影中以高概率重構(gòu)出原信號。 1.2 研究現(xiàn)狀 壓縮感知理論首先由Cands、Romberg、Tao和Donoho等人在2004年提 出，文獻直到2006年才發(fā)表。這三篇文章基本奠定了壓縮感知的理論 基礎。 1 E Candes,J Romberg,T Tao.Robust uncertainty principles:exact signal reconstruction from highly incomplete frequency informationJ.IEEE Transacti

4、ons on Information Theory,2006,52(2):489 -509. 2 D L Donoho.Compressed sensingJ.IEEE Transactions on Information Theory,2006,52(4):1289 -1306. 3E J Candes,T Tao.Near-optimal signal recovery from random projections :Universal encoding strategiesJ.IEEE Transactions on Information Theory,2006,52(12):54

5、06 -5425. CS理論一經(jīng)提出,就在信息論、醫(yī)療成像、光學/遙感成像、無線通信、模 式識別、生物傳感、雷達探測、地質(zhì)勘探、天文、集成電路分析、超譜圖 像處理、圖像壓縮、圖像超分辨重建等領域受到高度關注,并被美國科技評 論評為”2007年度十大科技進展”,D Donoho因此還獲得了“2008年IEEE IT學會 最佳論文獎”。 目前，CS理論與應用研究在不斷進行： l 在美國、歐洲等許多國家的知名大學如麻省理工學院、萊斯大學、斯坦 福大學、杜克大學等成立了專門課題組對CS進行研究;如萊斯大學建立的 專門的Compressive Sensing網(wǎng)站 /c

6、s ，里面有關于該 理論大量資源和該方向的最新研究成果。 l 2008年,貝爾實驗室,Intel，Google等知名公司也開始組織研究CS;2009 年,美國空軍實驗室和杜克大學聯(lián)合召開了CS研討會,美國國防先期研究計 劃署(DARPA)和國家地理空間情報局(NGA)等政府部門成員與數(shù)學、信號 處理、微波遙感等領域的專家共同探討了CS應用中的關鍵問題。 l 在國內(nèi),一些高校和科研機構(gòu)也開始對CS的研究,如清華大學、中科院電 子所、西安交通大學和西安電子科技大學等。 l 國家自然科學基金委也自2009年資助了多項壓縮感知方法的研究,涉及 認知無線電、雷達成像、信號稀疏表示、多媒體編碼、人臉識別等

7、領域。 2 壓縮感知理論 2.1 理論框架概述 考慮一個實值的有限長一維離散信號 , 可以看作一個 空間 維的列向量，元素為 空間的任何信號 都可以用 維的基向量 的線性組合表示。為簡化問題，假 定這些基是規(guī)范正交的。把向量 作為列向量形成 的基矩 陣 ,于是任意信號 都可表示 ： x 1N .,2,1,Nnnx N R 1 N i i N R 1N 1 N i i NN N , 21 x 1 ) 1 ( 1 xorx N i ii 這里 由 構(gòu)成為 維的列向量，是信號 在 域內(nèi)的等價表示形式。若用 表示 中非零元素的個數(shù),則當 時就稱向量 是稀疏的。對應于公式(1)而言，若 是一個稀疏向量，

8、則 稱信號 可以在 域進行稀疏表示或 是可壓縮的。 1N k Nk x xx T iii , x 1R Baraniuk.A lecture on comperessive sensingJ.IEEE Signal Processing Magazine ,2007,24(4):118-121. x 壓縮感知理論指出，設長度為N的信號 在某組正交基或緊框架 上的變換 系數(shù)是稀疏的。如果我們用一個與變換基 不相關的觀測基 : MN (MN) 對信號x進行線性變換，并得到觀測集合Y：M1那么就可以利 用優(yōu)化求解方法。從觀測集合中精確或高概率地重構(gòu)信號 。 yx 圖2 壓縮感知理論框圖 (2) x

9、x 根據(jù)以上分析可以將壓縮感知理論主要內(nèi)容總結(jié)為如下三點： l信號的稀疏表示，即尋找一個合適的基 使得信號x在 域內(nèi)能夠稀疏 表示。 l觀測矩陣的構(gòu)造，即設計出與基矩陣 不相關的MXN維觀測矩陣 ， 能夠使得信號中的重要信息在壓縮觀測中被保留。 l信號的重構(gòu)，即設計出能從觀測集合y中準確恢復出原始信號的算法。 這里稱為 感知矩陣也有稱為CS信息算子。A Ay 圖3 壓縮觀測過程的示意圖 2.2 信號稀疏表示 2 Donoho D L. Compressed sensing J. IEEE Transactions on Information Theory, 2006, 52(4):1289-

10、1306. 3 Candes E J, Wakin M B. An introduction to compressive sampling J. IEEE Signal Processing Magazine, 2008, 25(2):21-30. 4E J Cands, T Tao. Near optimal signal recovery from random projections:Universal encoding strategies. IEEE. Trans. Info. Theory, 2006,52(12):5406-5425. 在研究信號的稀疏表示時，可以通過變換系數(shù)衰

11、減速度來衡量變換基的稀疏 表示能力。Cands 和Tao4研究表明，滿足具有冪次速度衰減的信號，可利 用壓縮感知理論得到恢復，并且給出了滿足的重構(gòu)誤差。 10 , 2/1/1log/ 2 pprNKRCffE r p p n nRf /1 壓縮感知的一個重要前提和理論基礎就是信號的稀疏性或可壓縮性，只有選 擇合適的基表示信號才能保證信號的稀疏度，從而保證信號的恢復精度。在 以往的研究中已經(jīng)給出了能夠體現(xiàn)某些類型信號稀疏性或可壓縮性的變換基。 l針對光滑信號的傅里葉變換基、小波變換基，振蕩信號的Gabor變換及具 有不連續(xù)邊緣的圖像信號的Curvelet 變換基等。 l由正交基擴展到有多個正交基

12、構(gòu)成的正交基字典:即在某個正交基字典里， 自適應地尋找可以逼近某一種信號特征的最優(yōu)正交基，根據(jù)不同的信號尋找 最適合信號特性的一個正交基，對信號進行變換以得到最稀疏的信號表示。 l用超完備的冗余函數(shù)庫取代基函數(shù)，稱之為冗余字典：字典中的元素被稱 為原子字典的選擇應盡可能好地符合被逼近信號的結(jié)構(gòu)，其構(gòu)成可以沒有 任何限制從冗余字典中找到具有最佳線性組合的K項原子來表示一個信號， 稱作信號的稀疏逼近或高度非線性逼近。 00.0050.010.0150.020.0250.030.035 -2 -1 0 1 2 (a) signal in time domain time in second x(t)

13、=sin(1394t)+sin(3266t) 0200400600800100012001400160018002000 0 500 1000 1500 2000 (b) signal x in frequency domain frequency in Hertz 0500100015002000 0 50 100 150 200 250 300 (a) signal a 0500100015002000 -5000 0 5000 10000 15000 (b) DCT representation y 2.3 觀測矩陣設計 壓縮感知理論中，通過變換得到的信號的稀疏表示向量 ，需要設 計壓縮

14、采樣系統(tǒng)的觀測部分，既實現(xiàn)信號降維處理且使精確重構(gòu)信號 所需要測量點盡可能小，又要保證重要信息不被破壞。 圖4 壓縮觀測過程的示意圖 y x (4) 由于 MN，這使得公式4所示的等式中方程的數(shù)目比未知數(shù)的數(shù)目 要少，因此，已知 y來求解 x是一個欠定問題且沒有確定的解。 如果 非零系數(shù)位置已知的K- 稀疏的（kN ）向量時，則上述問題就可 能求得唯一解。Candes等人通過理論分析得出了滿足公式6所示使問題存 在確定解的充分必要條件，即在壓縮觀測時所選取的觀測矩陣 需滿足有限 等距性質(zhì)（Restricted Isometry Property, RIP）5。 然而，判定給定的觀測矩陣是否具有

15、RIP 性質(zhì)是一個組合復雜度的問題， 所以為降低復雜度，我們可以另一種等價條件是測量矩陣 與變換基 不相關，則A 在很大概率滿足RIP 性質(zhì)。 5 E Cands. The restricted isometry property and its implications for compressed sensing. Acadmie des sciences, 2006, 34(6): 588-592. 兩矩陣之間越不相關，相關度就越小，互相表示時所需要的表示系數(shù)個數(shù) 就越多，反之，相關性則越強。設計時要滿足測量矩陣與稀疏矩陣盡可能 地不相關。 6 E. Candes and J. Romb

16、erg, “Sparsity and incoherence in compressive sampling,” Inverse Problems, vol.23, no.3, pp.969-985, 2007. 幾種常見的測量矩陣 l隨機高斯矩陣：可高概率保證不相關性和RIP性質(zhì)。例如對一個MN的 隨機高斯矩陣 ，可以證明當 ,感知矩陣A很大概率 滿足RIP性質(zhì)，因此可以從M個觀測值中很大概率恢復長度為N的K項稀疏 信號。總之，隨機高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關。 l伯努利測量矩陣:滿足一定條件下，能準確重構(gòu)信號概率很大且重構(gòu)速度 很大。 l 其他矩陣：部分傅里葉矩陣，非相關測量

17、矩陣，Toiplitz 和循環(huán)矩陣。 )/log(KNcKM 2.4信號重構(gòu)算法 壓縮感知中信號重構(gòu)過程就是從M個觀測值對原始長度為N的信號x進行 估計的過程。我們通過 獲得M個觀測值。重構(gòu)過程中，通過 求解出稀疏向量 。 由于觀測數(shù)量M遠小于信號長度N，因此不得不面對求解欠定方程組問 題。表面上看，求解欠定方程組似乎是無望的，如果信號x是稀疏的或可 壓縮的，便使得問題可解，觀測矩陣具有RIP性質(zhì)也為從M個觀測值中精 確恢復信號提供了理論保證。 yx Ay D. Donoho 等人已證明，當測量矩陣滿足RIP 條件時，上述組合優(yōu)化問題 可轉(zhuǎn)化為l1范數(shù)約束的凸優(yōu)化問題，那么對于公式8的求解問題

18、就可以轉(zhuǎn)換 求解范數(shù)問題。問題就轉(zhuǎn)化一個凸優(yōu)化問題，可簡化為線性規(guī)劃問題。 1 min s.t. = y 當觀測值 y中帶有噪聲時，公式9中的等式 不能滿足，因此公式 9所示的優(yōu)化問題應該相應地修改為： y 2 12 min s.t. 10 y 是一個根據(jù)噪聲水平設定的正常數(shù)。 目前出現(xiàn)的重構(gòu)算法可歸納一下三類： l 凸松弛法：這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號的 逼近，如BP算法，內(nèi)點法，梯度投影方法和迭代閾值法。該類算法 的優(yōu)點是僅需較少的觀測值即可近似重構(gòu)出原始稀疏信號，其缺點 是計算復雜度較高。 l 貪婪追蹤算法：這類方法是通過每次迭代時選擇一個局部最優(yōu)解來 逐步逼近原始信

19、號。這些算法包括MP算法，OMP算法，分段OMP算 法(STOMP)和正則化OMP(ROMP)算法。該類算法的優(yōu)勢是計算時間 相對于凸優(yōu)化算法更短且算法易于實現(xiàn)，其不足之處是無法保證獲 得全局最優(yōu)解。 l 組合算法：這類方法要求信號的采樣支持通過分組測試快速重建， 如傅立葉采樣，鏈式追蹤和HHS(Heavg Hitters Oil Steroids)追蹤等。該 類算法的優(yōu)點是計算時間非常短，其缺點是需要的觀測值較多且不 易獲取。 0100200300400500600 -5 0 5 10 15 20 25 30 recovery x with L1 minimization recovery

20、x original x0 0100200300400500600 0 0.2 0.4 0.6 0.8 1 1.2 1.4 1.6 x 10 -7 Error between x with L1 minimization and x0 050100150200250 -3 -2 -1 0 1 2 3 Original x Recovery y 0100200300400500600700800 0 100 200 300 050100150200250300 0 0.5 1 1.5 x 10 -14 信道估計描述了物理信道對輸入信號的影響，是對信道響應的一種 數(shù)學近似。具體來說，就是接收機根據(jù)

21、接收到的信號對信道的時域頻 域的傳輸特性進行估計，在滿足某些準則的前提下，盡可能使估計結(jié)果 接近實際的信道傳輸特性。 目前的信道估計方法主要分為兩類：基于導頻的估計方法和盲估計 方法。 信道模型可表示為 3 應用與展望 3.1 應用舉例 上式可表示為 矩陣形式 越來越多的實驗和研究表明：實際的無線信道通常呈現(xiàn)稀疏性，例如 水聲信道，高清數(shù)字電視信道，超寬帶信道等。這些信道往往是由幾條重 要路徑組成的相對較小的聚類，尤其是在高速通信系統(tǒng)和寬帶通信系統(tǒng)中 ，信道的稀疏性表現(xiàn)得更為明顯。稀疏信道的沖激響應也與普通信道的沖 激響應不同，僅有少數(shù)攜帶重要能量的抽頭，這些抽頭的系數(shù)非零，剩余 大部分抽頭系數(shù)為零或者接近零。 如圖所示是一個典型的稀疏信道 沖激響應，該信道的長度為120 ，而非零抽頭的個數(shù)只有12。 稀疏信道模型 信道的傳輸模型可以表示為： 實際的無線信道通常具有稀疏的結(jié)構(gòu)，也就是說h(l)中僅 有K(KN)個抽頭的系數(shù)非零，假設它們隨機均勻地分布在 長度為N的信道上。 由于無線多徑信道的沖激響應h具有稀疏性，滿足壓縮感 知的前提條件，于是對稀疏信道的估計就可以轉(zhuǎn)化到壓縮感 知的理論框架中進行求解。 忽略噪聲的影響，可寫成： 這里我們只研究基于導頻的稀疏信道估計。 假設發(fā)送端發(fā)送的導頻為 信道的沖激響應為 那么接收端相應的接收信號 即為 當系統(tǒng)輸入信號時，若信號