壓縮感知理論及應(yīng)用課件

壓縮感知理論及應(yīng)用匯報(bào)人：###1背景與現(xiàn)狀

1.1問題背景

1.2研究現(xiàn)狀2壓縮感知理論

2.1理論框架概述

2.2信號(hào)稀疏表示

2.3觀測(cè)矩陣設(shè)計(jì)

2.4信號(hào)重構(gòu)算法3應(yīng)用與展望

3.1應(yīng)用舉例

3.2總結(jié)展望壓縮感知理論及應(yīng)用

1背景與現(xiàn)狀

1.1問題背景

隨著信息技術(shù)的飛速發(fā)展，人們對(duì)信息的需求量日益增加，所需攜帶信息的信號(hào)帶寬越來越寬，故在信息獲取中對(duì)采樣速率和處理速度等提出更高的要求。而在傳統(tǒng)信息獲取中存在以下問題：在奈奎斯特采樣定理為基礎(chǔ)的傳統(tǒng)信號(hào)處理框架中，若從采樣的離散信號(hào)中無失真的恢復(fù)模擬信號(hào)，采樣速率必須至少是信號(hào)帶寬的兩倍。隨著模擬信號(hào)帶寬越來越寬，采樣速率更高，對(duì)信號(hào)處理的軟硬件設(shè)計(jì)更困難。實(shí)際應(yīng)用中，為了降低存儲(chǔ)，處理和傳輸?shù)某杀?，常采用壓縮的方式以較少的比特?cái)?shù)表示信號(hào)，大量的非重要的數(shù)據(jù)被拋棄，這帶來大量的資源浪費(fèi)。

1.2研究現(xiàn)狀壓縮感知理論首先由Candès、Romberg、Tao和Donoho等人在2004年提出，文獻(xiàn)直到2006年才發(fā)表。這三篇文章基本奠定了壓縮感知的理論基礎(chǔ)。[1]ECandes,JRomberg,TTao.Robustuncertaintyprinciples:exactsignalreconstructionfromhighlyincompletefrequencyinformation[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.[2]DLDonoho.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.[3]EJCandes,TTao.Near-optimalsignalrecoveryfromrandomprojections:Universalencodingstrategies[J].IEEETransactionsonInformationTheory,2006,52(12):5406-5425.CS理論一經(jīng)提出,就在信息論、醫(yī)療成像、光學(xué)/遙感成像、無線通信、模式識(shí)別、生物傳感、雷達(dá)探測(cè)、地質(zhì)勘探、天文、集成電路分析、超譜圖像處理、圖像壓縮、圖像超分辨重建等領(lǐng)域受到高度關(guān)注,并被美國(guó)科技評(píng)論評(píng)為”2007年度十大科技進(jìn)展”,DDonoho因此還獲得了“2008年IEEEIT學(xué)會(huì)最佳論文獎(jiǎng)”。目前，CS理論與應(yīng)用研究在不斷進(jìn)行：在美國(guó)、歐洲等許多國(guó)家的知名大學(xué)如麻省理工學(xué)院、萊斯大學(xué)、斯坦福大學(xué)、杜克大學(xué)等成立了專門課題組對(duì)CS進(jìn)行研究;如萊斯大學(xué)建立的專門的CompressiveSensing網(wǎng)站

，里面有關(guān)于該理論大量資源和該方向的最新研究成果。

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

2.1理論框架概述考慮一個(gè)實(shí)值的有限長(zhǎng)一維離散信號(hào),可以看作一個(gè)空間維的列向量，元素為

空間的任何信號(hào)

都可以用維的基向量的線性組合表示。為簡(jiǎn)化問題，假

定這些基是規(guī)范正交的。把向量作為列向量形成的基矩陣,于是任意信號(hào)都可表示

：

這里

由構(gòu)成為

維的列向量，是信號(hào)在

域內(nèi)的等價(jià)表示形式。若用

表示

中非零元素的個(gè)數(shù),則當(dāng)時(shí)就稱向量

是稀疏的。對(duì)應(yīng)于公式(1)而言，若是一個(gè)稀疏向量，則稱信號(hào)

可以在

域進(jìn)行稀疏表示或是可壓縮的。[1]RBaraniuk.Alectureoncomperessivesensing[J].IEEESignalProcessingMagazine,2007,24(4):118-121.壓縮感知理論指出，設(shè)長(zhǎng)度為N的信號(hào)

在某組正交基或緊框架上的變換系數(shù)是稀疏的。如果我們用一個(gè)與變換基不相關(guān)的觀測(cè)基:

M×N(M<<N)對(duì)信號(hào)x進(jìn)行線性變換，并得到觀測(cè)集合Y：M×1．那么就可以利用優(yōu)化求解方法。從觀測(cè)集合中精確或高概率地重構(gòu)信號(hào)。

圖2壓縮感知理論框圖(2)2.2信號(hào)稀疏表示[2]DonohoDL.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.[3]CandesEJ,WakinMB.Anintroductiontocompressivesampling[J].IEEESignalProcessingMagazine,2008,25(2):21-30.[4]EJCandès,TTao.Nearoptimalsignalrecoveryfromrandomprojections:Universal

encodingstrategies.IEEE.Trans.Info.Theory,2006,52(12):5406-5425.在研究信號(hào)的稀疏表示時(shí)，可以通過變換系數(shù)衰減速度來衡量變換基的稀疏表示能力。Candès和Tao[4]研究表明，滿足具有冪次速度衰減的信號(hào)，可利用壓縮感知理論得到恢復(fù)，并且給出了滿足的重構(gòu)誤差。

如果非零系數(shù)位置已知的K-

稀疏的（k<<N

）向量時(shí)，則上述問題就可能求得唯一解。Candes等人通過理論分析得出了滿足公式6所示使問題存在確定解的充分必要條件，即在壓縮觀測(cè)時(shí)所選取的觀測(cè)矩陣需滿足有限等距性質(zhì)（RestrictedIsometryProperty,RIP）[5]。然而，判定給定的觀測(cè)矩陣是否具有RIP性質(zhì)是一個(gè)組合復(fù)雜度的問題，所以為降低復(fù)雜度，我們可以另一種等價(jià)條件是測(cè)量矩陣與變換基不相關(guān)，則A在很大概率滿足RIP性質(zhì)。[5]ECandès.Therestrictedisometrypropertyanditsimplicationsforcompressedsensing.Acadèmiedessciences,2006,34(6):588-592.兩矩陣之間越不相關(guān)，相關(guān)度就越小，互相表示時(shí)所需要的表示系數(shù)個(gè)數(shù)就越多，反之，相關(guān)性則越強(qiáng)。設(shè)計(jì)時(shí)要滿足測(cè)量矩陣與稀疏矩陣盡可能地不相關(guān)。[6]E.CandesandJ.Romberg,“Sparsityandincoherenceincompressivesampling,”InverseProblems,vol.23,no.3,pp.969-985,2007.幾種常見的測(cè)量矩陣隨機(jī)高斯矩陣：可高概率保證不相關(guān)性和RIP性質(zhì)。例如對(duì)一個(gè)M×N的隨機(jī)高斯矩陣，可以證明當(dāng),感知矩陣A很大概率滿足RIP性質(zhì)，因此可以從M個(gè)觀測(cè)值中很大概率恢復(fù)長(zhǎng)度為N的K項(xiàng)稀疏

信號(hào)?？傊?，隨機(jī)高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān)。伯努利測(cè)量矩陣:滿足一定條件下，能準(zhǔn)確重構(gòu)信號(hào)概率很大且重構(gòu)速度

很大。其他矩陣：部分傅里葉矩陣，非相關(guān)測(cè)量矩陣，Toiplitz和循環(huán)矩陣。2.4信號(hào)重構(gòu)算法壓縮感知中信號(hào)重構(gòu)過程就是從M個(gè)觀測(cè)值對(duì)原始長(zhǎng)度為N的信號(hào)x進(jìn)行

估計(jì)的過程。我們通過獲得M個(gè)觀測(cè)值。重構(gòu)過程中，通過

求解出稀疏向量

。

由于觀測(cè)數(shù)量M遠(yuǎn)小于信號(hào)長(zhǎng)度N，因此不得不面對(duì)求解欠定方程組問題。表面上看，求解欠定方程組似乎是無望的，如果信號(hào)x是稀疏的或可壓縮的，便使得問題可解，觀測(cè)矩陣具有RIP性質(zhì)也為從M個(gè)觀測(cè)值中精確恢復(fù)信號(hào)提供了理論保證。

D.Donoho等人已證明，當(dāng)測(cè)量矩陣滿足RIP條件時(shí)，上述組合優(yōu)化問題可轉(zhuǎn)化為l1范數(shù)約束的凸優(yōu)化問題，那么對(duì)于公式8的求解問題就可以轉(zhuǎn)換求解范數(shù)問題。問題就轉(zhuǎn)化一個(gè)凸優(yōu)化問題，可簡(jiǎn)化為線性規(guī)劃問題。

當(dāng)觀測(cè)值y中帶有噪聲時(shí)，公式9中的等式

不能滿足，因此公式9所示的優(yōu)化問題應(yīng)該相應(yīng)地修改為：是一個(gè)根據(jù)噪聲水平設(shè)定的正常數(shù)。目前出現(xiàn)的重構(gòu)算法可歸納一下三類：凸松弛法：這類方法通過將非凸問題轉(zhuǎn)化為凸問題求解找到信號(hào)的逼近，如BP算法，內(nèi)點(diǎn)法，梯度投影方法和迭代閾值法。該類算法的優(yōu)點(diǎn)是僅需較少的觀測(cè)值即可近似重構(gòu)出原始稀疏信號(hào)，其缺點(diǎn)是計(jì)算復(fù)雜度較高。貪婪追蹤算法：這類方法是通過每次迭代時(shí)選擇一個(gè)局部最優(yōu)解來逐步逼近原始信號(hào)。這些算法包括MP算法，OMP算法，分段OMP算法(STOMP)和正則化OMP(ROMP)算法。該類算法的優(yōu)勢(shì)是計(jì)算時(shí)間相對(duì)于凸優(yōu)化算法更短且算法易于實(shí)現(xiàn)，其不足之處是無法保證獲得全局最優(yōu)解。組合算法：這類方法要求信號(hào)的采樣支持通過分組測(cè)試快速重建，如傅立葉采樣，鏈?zhǔn)阶粉櫤虷HS(HeavgHittersOilSteroids)追蹤等。該類算法的優(yōu)點(diǎn)是計(jì)算時(shí)間非常短，其缺點(diǎn)是需要的觀測(cè)值較多且不易獲取。信道估計(jì)描述了物理信道對(duì)輸入信號(hào)的影響，是對(duì)信道響應(yīng)的一種數(shù)學(xué)近似。具體來說，就是接收機(jī)根據(jù)接收到的信號(hào)對(duì)信道的時(shí)域／頻域的傳輸特性進(jìn)行估計(jì)，在滿足某些準(zhǔn)則的前提下，盡可能使估計(jì)結(jié)果接近實(shí)際的信道傳輸特性。目前的信道估計(jì)方法主要分為兩類：基于導(dǎo)頻的估計(jì)方法和盲估計(jì)方法。信道模型可表示為3應(yīng)用與展望

3.1應(yīng)用舉例上式可表示為矩陣形式稀疏信道模型信道的傳輸模型可以表示為：實(shí)際的無線信道通常具有稀疏的結(jié)構(gòu)，也就是說h(l)中僅有K(K<<N)個(gè)抽頭的系數(shù)非零，假設(shè)它們隨機(jī)均勻地分布在長(zhǎng)度為N的信道上。由于無線多徑信道的沖激響應(yīng)h具有稀疏性，滿足壓縮感知的前提條件，于是對(duì)稀疏信道的估計(jì)就可以轉(zhuǎn)化到壓縮感知的理論框架中進(jìn)行求解。忽略噪聲的影響，可寫成：這里我們只研究基于導(dǎo)頻的稀疏信道估計(jì)。假設(shè)發(fā)送端發(fā)送的導(dǎo)頻為信道的沖激響應(yīng)為那么接收端相應(yīng)的接收信號(hào)即為當(dāng)系統(tǒng)輸入信號(hào)時(shí)，若信號(hào)與訓(xùn)練序列之間沒有保護(hù)間隔，即訓(xùn)練序列的后面緊隨信號(hào)序列。這種情況下，X矩陣中的零元素部分被輸入信號(hào)代替，那么卷積過后與這部分對(duì)應(yīng)的輸出是混疊的無用信號(hào)。為了能更好地估計(jì)，等式變?yōu)椋壕仃嘪是由導(dǎo)頻x構(gòu)成的具有Toeplitz結(jié)構(gòu)的MxN維矩陣，它使原來的高維稀疏信號(hào)h變成了一個(gè)低維信號(hào)Y。3.2總結(jié)展望壓縮感知理論利用了信號(hào)的稀疏特性，將原來基于奈奎斯特采樣定理的信號(hào)采樣過程轉(zhuǎn)化為基于優(yōu)化計(jì)算恢復(fù)信號(hào)的觀測(cè)過程。在重構(gòu)軟件代價(jià)的基礎(chǔ)上，避免了高速采樣和