壓縮感知原理

1、壓縮感知原理1壓縮感知引論傳統(tǒng)方式下的信號處理,是根據(jù)奈奎斯特采樣定理對信號進行采樣,得到大量的采樣數(shù)據(jù),需要先獲取整個信號再進行壓縮,其壓縮過程如圖2.1可壓縮信號tWj速米樣變換壓縮重構(gòu)信號圖2.1傳統(tǒng)的信號壓縮過程在此過程中,大局部采樣數(shù)據(jù)將會被拋棄,即高速采樣后再壓縮的過程浪費了大量的采樣資源,這就極大地增加了存儲和傳輸?shù)拇鷥r.由于帶寬的限制,許多信號只包含少量的重要頻率的信息.所以大局部信號是稀疏的或是可壓縮的,對于這種類型的信號,既然傳統(tǒng)方法采樣的多數(shù)數(shù)據(jù)會被拋棄,那么,為什么還要獲取全部數(shù)據(jù)而不直接獲取需要保存的數(shù)據(jù)呢？Candes和Donoho等人于2004年提出了壓縮感知理論

2、.該理論可以理解為將模擬數(shù)據(jù)節(jié)約地轉(zhuǎn)換成壓縮數(shù)字形式,防止了資源的浪費.即,在采樣信號的同時就對數(shù)據(jù)進行適當(dāng)?shù)膲嚎s,相當(dāng)于在采樣過程中尋找最少的系數(shù)來表示信號,并能用適當(dāng)?shù)闹貥?gòu)算法從壓縮數(shù)據(jù)中恢復(fù)出原始信號.壓縮感知的主要目標是從少量的非適應(yīng)線性測量中精確有效地重構(gòu)信號.核心概念在于試圖從原理上降低對一個信號進行測量的成本.壓縮感知包含了許多重要的數(shù)學(xué)理論,具有廣泛的應(yīng)用前景,最近幾年引起廣泛的關(guān)注,得到了蓬勃的開展.2壓縮感知原理壓縮感知,也被稱為壓縮傳感或壓縮采樣,是一種利用稀疏的或可壓縮的信號進行信號重構(gòu)的技術(shù).或者可以說是信號在采樣的同時被壓縮,從而在很大程度上降低了采樣率.壓縮感知跳

3、過了采集N個樣本這一步驟,直接獲得壓縮的信號的表示.CS理論利用到了許多自然信號在特定的基上具有緊湊的表示.即這些信號是“稀疏的或“可壓縮的.由于這一特性,壓縮感知理論的信號編解碼框架和傳統(tǒng)的壓縮過程大不一樣,主要包括信號的稀疏表示、編碼測量和重構(gòu)算法等三個方面.對于一個實值的有限長一維離散時間信號X,可以看作為一個RN空間NX1的維的列向量,元素為n,n,=1,2,N.RN空間的任何信號都可以用Nxi維N的基向量i-的線性組合表示.為簡化問題,假定這些基是標準正交的.把向量Ni-作為列向量形成NN的基矩陣：=1,2,?,N,于是任意信號X都可以表示為：X(2.1)其中是投影系數(shù)=i(X,)構(gòu)

4、成的NX1的列向量.顯然,X和是同一個信號的等價表示,X是信號在時域的表示,那么是信號在域的表示.如果的非零個數(shù)比N小很多,那么說明該信號是可壓縮的.一般而言,可壓縮信號是指可以用K個大系數(shù)很好地逼近的信號,即它在某個正交基下的展開的系數(shù)按一定量級呈現(xiàn)指數(shù)衰減,具有非常少的大系數(shù)和許多小系數(shù).這種通過變換實現(xiàn)壓縮的方法稱為變換編碼.在數(shù)據(jù)采樣系統(tǒng)中,采樣速率高但信號是可壓縮的,采樣得到N點采樣信號X;通過TX變換后計算出完整的變換系數(shù)集合i;確定K個大系數(shù)的位置,然后扔掉NK個小系數(shù)；對K個大系數(shù)的值和位置進行編碼,從而到達壓縮的目的.由CandesRomberg、Tao和Donoho等人在2

5、004年提出的壓縮感知理論說明,可以在不喪失逼近原信號所需信息的情況下,用最少的觀測次數(shù)來采樣信號,實現(xiàn)信號的降維處理,即直接對信號進行較少采樣得到信號的壓縮表示,且不經(jīng)過進行N次采樣的中間階段,從而在節(jié)約采樣和傳輸本錢的情況下,到達了在采樣的同時進行壓縮的目的.CandeSE明了只要信號在某一個正交空間具有稀疏性,就能以較低的頻率MN采樣信號,而且可以以高概率重構(gòu)該信號.即,設(shè)定設(shè)長度為N的信號X在某正交基或框架上的變換系數(shù)是稀疏的,如果我們可以用一個與變換基不相關(guān)的觀測基：MNMN對系數(shù)向量進行線性變換,并得到觀測集合Y:M1.那么就可以利用優(yōu)化求解方法從觀測集合中精確或高概率地重構(gòu)原始信

6、號X.圖2.2是基于壓縮感知理論的信號重構(gòu)過程框圖.圖2.2基于壓縮感知理論的信號重構(gòu)過程基于壓縮感知的信號重構(gòu)主要包含了信號的稀疏表示、編碼測量和重構(gòu)算法三個步驟.第一步,如果信號XRN在某個正交基或緊框架上是可壓縮的,求出變換系數(shù)TX,是的等價或逼近的稀疏表示；第二步,設(shè)計一個平穩(wěn)的、與變換基不相關(guān)的MN維的觀測矩陣,對進行觀測得到觀測集合YTX,該過程也可以表示為信號X通過矩陣ACS進行非自適應(yīng)觀測：YACS(其中ACST),ACS稱為CSJ息算子；第三步,利用0-范數(shù)意義下的優(yōu)化問題求解X的精確或近似逼近父：minTX|s.t.ACSXTXY(2.2)求得的向量X在基上的表小最稀疏.針

7、對上述的三個步驟,下面將一一解決其中的三個問題.2.1 信號的稀疏表示壓縮感知的第一步即,對于信號Xern,如何找到某個正交基或緊框架,使其在上的表示是稀疏的,即信號的稀疏表示問題.所謂的稀疏,就是指信號X在正交基下的變換系數(shù)向量為tx,假設(shè)對于0p2和R0,這些系數(shù)滿足：i/pIIIpJR(2.3)那么說明系數(shù)向量在某種意義下是稀疏的.如何找到信號最正確的稀疏域？這是壓縮感知理論應(yīng)用的根底和前提,只有選擇適宜的基表示信號才能保證信號的稀疏度,從而保證信號的恢復(fù)精度.在研究信號的稀疏表示時,可以通過變換系數(shù)衰減速度來衡量變換基的稀疏表示水平.CandesF口TaoW究說明,滿足具有幕次速度衰減

8、的信號,可利用壓縮感知理論得到恢復(fù),并且重構(gòu)誤差滿足：Cr(K/logN)6r(2.4)其中r=1/p-1/2,0<p<1.文獻8指出光滑信號的Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號的Gabo添數(shù)及具有不連續(xù)邊緣的圖像信號的Curvelet系數(shù)等都具有足夠的稀疏性,可以通過壓縮感知理論恢復(fù)信號.如何找到或構(gòu)造適合一類信號的正交基,以求得信號的最稀疏表示,這是一個有待進一步研究的問題.Peyre把變換基是正交基的條件擴展到了由多個正交基構(gòu)成的正交基字典.即在某個正交基字典里,自適應(yīng)地尋找可以逼近某一種信號特征的最優(yōu)正交基,根據(jù)不同的信號尋找最適合信號特性的一

9、個正交基,對信號進行變換以得到最稀疏的信號表示.對稀疏表示研究的另一個熱點是信號在冗余字典下的稀疏分解.這是一種全新的信號表示理論：用超完備的冗余函數(shù)庫取代基函數(shù),稱之為冗余字典,字典中的元素被稱為原子.字典的選擇應(yīng)盡可能好地符合被逼近信號的結(jié)構(gòu),其構(gòu)成可以沒有任何限制.從冗余字典中找到具有最正確線性組合的K項原子來表示一個信號,稱作信號的稀疏逼近或高度非線性逼近.從非線性逼近角度來講,信號的稀疏逼近包含兩個層面：一是根據(jù)目標函數(shù)從一個給定的基庫中挑選好的或最好的基；二是從這個好的基中挑選最正確的儂組合.因此,目前信號在冗余字典下的稀疏表示的研究集中在兩個方面：(1)如何構(gòu)造一個適合某一類信號

10、的冗余字典；(2)如何設(shè)計快速有效的稀疏分解算法.在構(gòu)造冗余字典方面,文獻16中提出使用局部Cosine8來刻畫聲音信號的局部頻域特性；利用bandleit來刻畫圖像中的幾何邊緣；還可以把其它的具有不同形狀的基函數(shù)歸入字典,如適合刻畫紋理的Gabor基、適合刻畫輪廓的Curvelet2t等等.在稀疏分解算法的設(shè)計方面,基于貪婪迭代思想的MP(MatchingPursuit)算法表現(xiàn)出極大的優(yōu)越性,但不是全局最優(yōu)解.Donoho等人之后提出了基追蹤(basispursuit,BP)算法.BP算法具有全局最優(yōu)的優(yōu)點,但計算復(fù)雜度極高.之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改良算法,如正交匹配追蹤

11、算法(OMP),分段匹配追蹤(StOMP)算法等.2.2 測量矩陣的選取如何設(shè)計一個平穩(wěn)的、與變換基不相關(guān)的MN維的觀測矩陣,保證稀疏向量從N維降到M維時重要信息不遭破壞,是第二步要解決的問題,也就是信號低速采樣問題.壓縮感知理論中,通過變換得到信號的稀疏系數(shù)向量TX后,需要設(shè)計壓縮采樣系統(tǒng)的觀測局部,它圍繞觀測矩陣展開.觀測器的設(shè)計目的是如何采樣得到M個觀測值,并保證從中能重構(gòu)出長度為N的信號X或者基下等價的稀疏系數(shù)向量.顯然,如果觀測過程破壞了X中的信息,重構(gòu)是不可能的.觀測過程實際就是利用MN觀測矩陣的M個行向量jM對稀疏系數(shù)向量進行投影,即計jji算和各個觀測向量M之間的內(nèi)積,得到M個

12、觀測值jjiYj,jj1,2,M,記觀測向量Y(yi,y2,Ym),即YTXACSX(2.5)這里,采樣過程是非自適應(yīng)的,也就是說,無須根據(jù)信號X而變化,觀測的不再是信號的點采樣而是信號的更一般的K線性泛函.對于給定的Y從式(2.5)中求出是一個線性規(guī)劃問題,但由于MN,即方程的個數(shù)少于未知數(shù)的個數(shù),這是一個欠定問題,一般來講無確定解.然而,如果具有K-項稀疏性(KM),那么該問題有望求出確定解.此時,只要設(shè)法確定出中的K個非零系數(shù)i的適宜位置,由于觀測向量Y是這些非零系數(shù)i對應(yīng)的K個列向量的線性組合,從而可以形成一個MK的線性方程組來求解這些非零項的具體值.對此,有限等距性質(zhì)給出了存在確定解

13、的充要條件.這個充要條件和CandesTa常人提出的稀疏信號在觀測矩陣作用下必須保持的幾何性質(zhì)相一致.即,要想使信號完全重構(gòu),必須保證觀測矩陣不會把兩個不同的K-項稀疏信號映射到同一個采樣集合中,這就要求從觀測矩陣中抽取的每M個列向量構(gòu)成的矩陣是非奇異的.從中可以看出,問題的關(guān)鍵是如何確定非零系數(shù)的位置來構(gòu)造出一個可解的MK線性方程組.然而,判斷給定的ACS是否具有RIP性質(zhì)是一個組合復(fù)雜度問題.為了降低問題的復(fù)雜度,能否找到一種易于實現(xiàn)RIP條件的替代方法成為構(gòu)造觀測矩陣的關(guān)鍵.文獻10指出如果保證觀測矩陣和稀疏基不相干,那么ACS在很大概率上滿足RIP性質(zhì).不相干是指向量j不能用i稀疏表示

14、.不相干性越強,互相表示時所需的系數(shù)越多；反之,相關(guān)性那么越強.通過選擇高斯隨機矩陣作為即可高概率保證不相干性和RIP性質(zhì).例如,可以生成多個零均值、方差為1/N的隨機高斯函數(shù),將它們作為觀測矩陣的元素>使得ACS以很高的概率具有RIP性質(zhì).隨機高斯矩陣具有一個有用的性質(zhì)：對于一個MN的隨機高斯矩陣,可以證實當(dāng)M?cKlog(N/K)時TACS在很大概率下具有RIP性質(zhì)(其中久一個很小的常數(shù)).因此可以從M個觀測值Y(yi,y2,yM)中以很高的概率去恢復(fù)長度為N的K-項稀疏信號.總之,隨機高斯矩陣與大多數(shù)固定正交基構(gòu)成的矩陣不相關(guān),這一特性決定了選它作為觀測矩陣,其它正交基作為稀疏變換

15、基時,ACS滿足RIP性質(zhì).為進一步簡化觀測矩陣,在某些條件下,以隨機1為元素構(gòu)成的Rademache矩陣也可以證實具有RIP性質(zhì)和普適性.對觀測矩陣的研究是壓縮感知理論的一個重要方面.Donoho給出了觀測矩陣所必需具備的三個條件,并指出大局部一致分布的隨機矩陣都具備這三個條件,均可作為觀測矩陣,如：局部Fourier集、局部Hadamar狄、一致分布的隨機投影(uniformRandomProjection課等,這與對RIP性質(zhì)進行研究得出的結(jié)論相一致.但是,使用上述各種觀測矩陣進行觀測后,都僅僅能保證以很高的概率去恢復(fù)信號,而不能保證百分之百地精確重構(gòu)信號.對于任何穩(wěn)定的重構(gòu)算法是否存在

16、一個真實確實定性的觀測矩陣仍是一個有待研究的問題.2.3 信號重構(gòu)如何設(shè)計快速重構(gòu)算法,從線性觀測YACSX中恢復(fù)信號,是第三步要將解決的問題,即信號的重構(gòu)問題.在壓縮感知理論中,由于觀測數(shù)量M遠小于信號長度N,因此不得不面對求解欠定方程組YACSX的問題.外表上看,求解欠定方程組似乎是無望的,但是,文獻8和4均指出由于信號X是稀疏的或可壓縮的,這個前提從根本上改變了問題,使得問題可解,而觀測矩陣具有RIP性質(zhì)也為從M個觀測值中精確恢復(fù)信號提供了理論保證.為更清楚地描述壓縮感知理論的信號重構(gòu)問題,首先定義向量Xx,x2,xn的p范數(shù)為:NL兇.xp2.6當(dāng)p0時得到0范數(shù),它實際上表示X中非零

17、項的個數(shù).于是,在信號X稀疏或可壓縮的前提下,求解欠定方程組YACSX的問題轉(zhuǎn)化為最小0范數(shù)問題：min|TX|Os.t.ACSXTXY2.7但是,它需要列出M中所有非零項位置的CK備種可能的線性組合,才能得到最優(yōu)解.因此,求解式2.7的數(shù)值計算極不穩(wěn)定而且是NF®問題.注意,這和稀疏分解問題從數(shù)學(xué)意義上講是同樣的問題.于是稀疏分解的已有算法可以應(yīng)用到CS重構(gòu)中.Chen,Donoho和SaunderS旨出,求解一個更加簡單的I1優(yōu)化問題會產(chǎn)生同等的解要求和不相關(guān)：min|TX1s.t.ACSXTXY2.8稍微的差異使得問題變成了一個凸優(yōu)化問題,于是可以方便地化簡為線性規(guī)劃問題,典型

18、算法代表：BFW法.盡管BFW法可行,但在實際應(yīng)用中存在兩個問題：第一,即使是常見的圖像尺寸,算法的計算復(fù)雜度也難以忍受,在采樣點個數(shù)滿足McK,c10g2N/K1時,重構(gòu)計算復(fù)雜度的量級在ON3;第二,由于1范數(shù)無法區(qū)分稀疏系數(shù)尺度的位置,所以盡管整體上重構(gòu)信號在歐氏距離上逼近原信號,但存在低尺度能量搬移到了高尺度的現(xiàn)象,從而容易出現(xiàn)一些人工效應(yīng),如一維信號會在高頻出現(xiàn)振蕩.基于上述問題,2005年1月CandeSf口Romberg提出了不同的信號恢復(fù)方法,該方法要求對原信號具有少量的先驗知識,同時也可以對所求結(jié)果施加適當(dāng)?shù)钠谕匦?以約束重構(gòu)信號的特性.通過在凸集上交替投影的方法,可以快速

19、求解線性規(guī)劃問題.Tropp和Gilbert提出利用匹配追蹤MP和正交匹配追蹤OMP算法來求解優(yōu)化問題重構(gòu)信號,大大提升了計算的速度,且易于實現(xiàn).樹形匹配追蹤TMP肝法是2005年La和NDo提出的.該方法針對BP、MP和OMP方法沒有考慮信號的多尺度分解時稀疏信號在各子帶位置的關(guān)系,將稀疏系數(shù)的樹型結(jié)構(gòu)加以利用,進一步提升了重構(gòu)信號的精度和求解的速度.匹配追蹤類算法都是基于貪婪迭代算法,以多于BPU法需要的采樣數(shù)目換取計算復(fù)雜度的降低.例如OMP算法,需要McK,c2ln(N)個采樣點數(shù)才能以較高的概率恢復(fù)信號,信號重構(gòu)的計算復(fù)雜度為O(NK2).2006年Donoho等人提出了分段正交匹配追蹤(STOMP,stagewiseOMP)算法.它將OMP進行一定程度的簡化,以逼近精度為代價進一步提升了計算速度(計算復(fù)雜度為O(N),