壓縮感知理論基本概述目錄TOC\o"1-3"\h\u10955壓縮感知理論基本概述 1197981.1信號的稀疏表示 1156321.2觀測矩陣的設(shè)計 2218211.3信號重構(gòu)算法 3壓縮感知理論的內(nèi)容是從稀疏表示、觀測矩陣和重建算法三個方面論述的。首要的就是信號稀疏的表示，過程中將信號進(jìn)行投影，最終正交化。信號變換后，其系數(shù)很小，從而得到變化后的向量表示，讓向量能夠達(dá)到稀疏的狀態(tài)，這樣做的目的是方便所得信號進(jìn)行后續(xù)的計算，這是CS理論的一個先驗性條件，即通過變換使信號達(dá)到稀疏狀態(tài)?？傊脡嚎s感知理論進(jìn)行信號重建需要考慮三點：(1)信號是能被壓縮的或者在特定域內(nèi)是稀疏的；(2)通過某一矩陣（即觀測矩陣）能將信號降維；(3)設(shè)計能夠快速、高概率重構(gòu)出信號的重構(gòu)算法。壓縮感知可以同時實現(xiàn)采樣和壓縮，過程如圖1.1所示。接下來對信號的稀疏表示、觀測矩陣的設(shè)計以及信號重構(gòu)算法展開討論。圖1.1壓縮感知基本過程1.1信號的稀疏表示假設(shè)信號是復(fù)數(shù)空間的一個維離散列向量，用表示其元素，。該列向量可以由維的標(biāo)準(zhǔn)正交基向量的線性組合表示，即信號可以表示為其中為的滿秩基矩陣；為的變換系數(shù)列向量，其中。由此可見，是在域的表示。若中非零元素的個數(shù)遠(yuǎn)小于信號的長度，即，那么信號在域是可壓縮的或是稀疏的，的稀疏度為。因此，稀疏信號是指在某一正交基下，系數(shù)中非零元素的個數(shù)遠(yuǎn)小于其維數(shù)或者系數(shù)的幅值呈指數(shù)衰減且少數(shù)項幅值較大其他項幅值近似為零的信號，稱前者為準(zhǔn)確稀疏信號，后者為近似稀疏信號，要對信號進(jìn)行稀疏或近似稀疏的表示，首先要找到合適的基矩陣，離散傅里葉變換基、離散余弦變換基等均為常用的基矩陣。例如：在OFDM系統(tǒng)中,需要對信號進(jìn)行時頻轉(zhuǎn)換，把看成有限長的離散時域信號，基矩陣為離散傅里葉變換(DFT)矩陣，則為帶寬有限的頻域信號。1.2觀測矩陣的設(shè)計壓縮感知理論指出，若長度為的信號在某一基矩陣下是稀疏的，稀疏度為，則可以通過合適的觀測矩陣從中選取個樣本構(gòu)成觀測合通過這個觀測合集能夠以很大的概率恢復(fù)原始信號，滿足條件 （1.1） （1.2）其中，為一個很小的常數(shù)。設(shè)計觀測矩陣的目的是找到個樣本構(gòu)成觀測合集，保證能夠從這個觀測合集中恢復(fù)出信號或基矩陣下的系數(shù)。由于，從而實現(xiàn)了數(shù)據(jù)壓縮。通常用一個維且與基矩陣?yán)锊幌嚓P(guān)的觀測矩陣對進(jìn)行線性變換，得到個樣本，可以表示成 （1.3）其中，為由個樣本組成的維觀測向量，為維觀測矩陣，為維測量矩陣。對于給定的觀測向量，由于，未知數(shù)個數(shù)遠(yuǎn)大于方程個數(shù)，此類欠定問題通常沒有確定的解，所以很難從式中直接求出。但是，如果信號是稀疏的且，即稀疏度小于樣本數(shù)，那么可以將求解的問題轉(zhuǎn)化為求解的問題，這樣就有可能求出確定的解。由于中的個非零元素對應(yīng)于測量矩陣的個列向量，而是這個列向量的線性組合，所以，一旦已知的非零元素的位置，問題就變成了求解維方程組，就能得出元素的值。尤其是當(dāng)矩陣滿足有限等距性質(zhì)(RestrictedIsometryProperty，RIP)時，上述問題才存在確定解。RIP的定義為：對于任意稀疏度為的稀疏信號若存在常數(shù)，滿足 （1.4）其中，，為中由索引集所指示的列向量組成的維子矩陣，則稱矩陣滿足RIP，然而在實際應(yīng)用中，判斷矩陣是否滿足有限等距性質(zhì)是一個非確定性多項式困難問題(Non-deterministicPolynomialhard，NP-hard)，要解決這一問題較為復(fù)雜，因此Baraniuk指出，如果能夠保證觀測矩陣與基矩陣互不相關(guān)，則測量矩陣很大概率能夠滿足RIP條件。研究得出，高斯隨機(jī)矩陣與大多數(shù)正交基矩陣是互不相關(guān)的，因此高斯隨機(jī)矩陣很大程度上可以作為觀測矩陣因為它是滿足RIP的，Donoho指出，大部分分布一致的隨機(jī)矩陣都能被當(dāng)做觀測矩陣使用。由此可得，伯努利分布矩陣、部分阿達(dá)馬矩陣等均可以作為觀測矩陣。1.3信號重構(gòu)算法信號重構(gòu)算法的好壞直接影響到信號恢復(fù)的程度，信號重構(gòu)的目的就是從維觀測合集中恢復(fù)出維原始稀疏信號，上一小節(jié)提到，由于，未知數(shù)個數(shù)遠(yuǎn)大于方程個數(shù)，此類欠定問題通常沒有確定的解，當(dāng)測量矩陣滿足RIP時，可以將求解轉(zhuǎn)化為求解，上述問題才存在確定解。2006年Candes等人證明了對于模型，可以通過求解最小范數(shù)ADDINEN.CITE<EndNote><Cite><Author>Chen</Author><Year>2001</Year><RecNum>40</RecNum><DisplayText><styleface="superscript">[28]</style></DisplayText><record><rec-number>40</rec-number><foreign-keys><keyapp="EN"db-id="wwpfwz9wts25tae9txkpwpfzpffzzefzzwwd"timestamp="1619496257">40</key></foreign-keys><ref-typename="JournalArticle">17</ref-type><contributors><authors><author>ScottShaobingChen</author><author>DavidL.Donoho</author><author>MichaelA.Saunders</author></authors></contributors><titles><title>AtomicDecompositionbyBasisPursuit</title><secondary-title>SIAMReview</secondary-title></titles><periodical><full-title>SIAMReview</full-title></periodical><volume>43</volume><number>1</number><keywords><keyword>OvercompleteSignalRepresentation</keyword><keyword>Denoising</keyword><keyword>Time-FrequencyAnalysis</keyword><keyword>Time-ScaleAnalysis</keyword><keyword>?1NormOptimization</keyword><keyword>MatchingPursuit</keyword><keyword>Wavelets</keyword><keyword>WaveletPackets</keyword><keyword>CosinePackets</keyword><keyword>Interior-PointMethodsforLinearProgramming</keyword><keyword>TotalVariationDenoising</keyword><keyword>MultiscaleEdges</keyword><keyword>MATLABCode</keyword><keyword>94A12</keyword><keyword>65K05</keyword><keyword>65D15</keyword><keyword>41A45</keyword><keyword>S003614450037906X</keyword></keywords><dates><year>2001</year></dates><isbn>0036-1445</isbn><urls></urls><remote-database-provider>Cnki</remote-database-provider></record></Cite></EndNote>[28]重構(gòu)出稀疏信號： （1.5）其中，是待重構(gòu)信號；是的范數(shù)，表示中非零元素的個數(shù)，最小化范數(shù)問題在實際應(yīng)用中是NP難問題，需要列出所有非零元素可能的組合，計算復(fù)雜度過高，當(dāng)觀測矩陣與基矩陣不相關(guān)時，最小化范數(shù)問題和最小化范數(shù)問題是等價的，求解范數(shù)是凸優(yōu)化問題，可以轉(zhuǎn)化成求解線性規(guī)劃問題： （1.6）考慮重構(gòu)誤差，上式可以寫成 （1.7）信號重構(gòu)算法可以歸納為三類：(1)貪婪算法。這類算法主要解決最小化范數(shù)問題，每一次選代時會在一定的范圍內(nèi)選出與信號最匹配的解，用這個解與原始信號進(jìn)行比較并計算得出信號的殘差，然后從殘差中再選出最適合的解，一直迭代下去。貪婪算法求解速度較快，要注意的是，該方法得出的不是適合全局的解而是用了近似的全局最優(yōu)解，比較著名的算法有匹配追蹤(MP)，正交匹配