壓縮感知原理

1、精選優(yōu)質文檔-傾情為你奉上  壓縮感知原理1壓縮感知引論傳統(tǒng)方式下的信號處理，是按照奈奎斯特采樣定理對信號進行采樣，得到大量的采樣數(shù)據(jù)，需要先獲取整個信號再進行壓縮，其壓縮過程如圖2.1?？蓧嚎s信號高速采樣壓縮重構信號變換圖2.1 傳統(tǒng)的信號壓縮過程在此過程中，大部分采樣數(shù)據(jù)將會被拋棄，即高速采樣后再壓縮的過程浪費了大量的采樣資源，這就極大地增加了存儲和傳輸?shù)拇鷥r。由于帶寬的限制，許多信號只包含少量的重要頻率的信息。所以大部分信號是稀疏的或是可壓縮的，對于這種類型的信號，既然傳統(tǒng)方法采樣的多數(shù)數(shù)據(jù)會被拋棄，那么，為什么還要獲取全部數(shù)據(jù)而不直接獲取需要保留的數(shù)據(jù)呢？Cande

2、s和Donoho等人于2004年提出了壓縮感知理論。該理論可以理解為將模擬數(shù)據(jù)節(jié)約地轉換成壓縮數(shù)字形式，避免了資源的浪費。即，在采樣信號的同時就對數(shù)據(jù)進行適當?shù)膲嚎s，相當于在采樣過程中尋找最少的系數(shù)來表示信號，并能用適當?shù)闹貥嬎惴◤膲嚎s數(shù)據(jù)中恢復出原始信號。壓縮感知的主要目標是從少量的非適應線性測量中精確有效地重構信號。核心概念在于試圖從原理上降低對一個信號進行測量的成本。壓縮感知包含了許多重要的數(shù)學理論，具有廣泛的應用前景，最近幾年引起廣泛的關注，得到了蓬勃的發(fā)展。2壓縮感知原理壓縮感知，也被稱為壓縮傳感或壓縮采樣，是一種利用稀疏的或可壓縮的信號進行信號重構的技術?；蛘呖梢哉f是信號在采樣的同

3、時被壓縮，從而在很大程度上降低了采樣率。壓縮感知跳過了采集個樣本這一步驟，直接獲得壓縮的信號的表示。CS理論利用到了許多自然信號在特定的基上具有緊湊的表示。即這些信號是“稀疏”的或“可壓縮”的。由于這一特性，壓縮感知理論的信號編解碼框架和傳統(tǒng)的壓縮過程大不一樣，主要包括信號的稀疏表示、編碼測量和重構算法等三個方面。對于一個實值的有限長一維離散時間信號，可以看作為一個空間×1的維的列向量，元素為，,=1，2，?？臻g的任何信號都可以用×1維的基向量的線性組合表示。為簡化問題，假定這些基是規(guī)范正交的。把向量作為列向量形成的基矩陣：= ,，于是任意信號都可以表示為： (2.1)其中

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

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

6、的信號重構過程框圖?？蓧嚎s信號稀疏變換觀測得到的維向量重構信號滿足圖2.2 基于壓縮感知理論的信號重構過程基于壓縮感知的信號重構主要包含了信號的稀疏表示、編碼測量和重構算法三個步驟。第一步，如果信號在某個正交基或緊框架上是可壓縮的，求出變換系數(shù)，是的等價或逼近的稀疏表示；第二步，設計一個平穩(wěn)的、與變換基不相關的維的觀測矩陣，對進行觀測得到觀測集合，該過程也可以表示為信號通過矩陣進行非自適應觀測： (其中)，稱為CS信息算子；第三步，利用0-范數(shù)意義下的優(yōu)化問題求解的精確或近似逼近： s.t. (2.2)求得的向量在基上的表示最稀疏。針對上述的三個步驟，下面將一一解決其中的三個問題。2.1 信號

7、的稀疏表示壓縮感知的第一步即，對于信號，如何找到某個正交基或緊框架，使其在上的表示是稀疏的，即信號的稀疏表示問題。所謂的稀疏，就是指信號在正交基下的變換系數(shù)向量為，假如對于和，這些系數(shù)滿足： (2.3)則說明系數(shù)向量在某種意義下是稀疏的。如何找到信號最佳的稀疏域？這是壓縮感知理論應用的基礎和前提，只有選擇合適的基表示信號才能保證信號的稀疏度，從而保證信號的恢復精度。在研究信號的稀疏表示時，可以通過變換系數(shù)衰減速度來衡量變換基的稀疏表示能力。Candes和Tao研究表明，滿足具有冪次速度衰減的信號，可利用壓縮感知理論得到恢復，并且重構誤差滿足： (2.4)其中r=1/p 1/2，0<p&l

8、t;1.文獻8指出光滑信號的Fourier系數(shù)、小波系數(shù)、有界變差函數(shù)的全變差范數(shù)、振蕩信號的Gabor系數(shù)及具有不連續(xù)邊緣的圖像信號的Curvelet系數(shù)等都具有足夠的稀疏性，可以通過壓縮感知理論恢復信號。如何找到或構造適合一類信號的正交基，以求得信號的最稀疏表示，這是一個有待進一步研究的問題。Peyre把變換基是正交基的條件擴展到了由多個正交基構成的正交基字典。即在某個正交基字典里，自適應地尋找可以逼近某一種信號特征的最優(yōu)正交基，根據(jù)不同的信號尋找最適合信號特性的一個正交基，對信號進行變換以得到最稀疏的信號表示。對稀疏表示研究的另一個熱點是信號在冗余字典下的稀疏分解。這是一種全新的信號表示

9、理論：用超完備的冗余函數(shù)庫取代基函數(shù)，稱之為冗余字典，字典中的元素被稱為原子。字典的選擇應盡可能好地符合被逼近信號的結構，其構成可以沒有任何限制。從冗余字典中找到具有最佳線性組合的項原子來表示一個信號，稱作信號的稀疏逼近或高度非線性逼近。從非線性逼近角度來講，信號的稀疏逼近包含兩個層面：一是根據(jù)目標函數(shù)從一個給定的基庫中挑選好的或最好的基；二是從這個好的基中挑選最佳的K項組合。因此，目前信號在冗余字典下的稀疏表示的研究集中在兩個方面：(1)如何構造一個適合某一類信號的冗余字典；(2)如何設計快速有效的稀疏分解算法。在構造冗余字典方面，文獻16中提出使用局部Cosine基來刻畫聲音信號的局部頻域

10、特性；利用bandlet基來刻畫圖像中的幾何邊緣；還可以把其它的具有不同形狀的基函數(shù)歸入字典，如適合刻畫紋理的Gabor基、適合刻畫輪廓的Curvelet基等等。在稀疏分解算法的設計方面，基于貪婪迭代思想的MP(Matching Pursuit)算法表現(xiàn)出極大的優(yōu)越性，但不是全局最優(yōu)解。Donoho等人之后提出了基追蹤(basis pursuit，BP)算法。BP算法具有全局最優(yōu)的優(yōu)點，但計算復雜度極高。之后又出現(xiàn)了一系列同樣基于貪婪迭代思想的改進算法，如正交匹配追蹤算法(OMP)，分段匹配追蹤(StOMP)算法等。2.2 測量矩陣的選取如何設計一個平穩(wěn)的、與變換基不相關的維的觀測矩陣，保證稀

11、疏向量從維降到維時重要信息不遭破壞，是第二步要解決的問題，也就是信號低速采樣問題。壓縮感知理論中，通過變換得到信號的稀疏系數(shù)向量后，需要設計壓縮采樣系統(tǒng)的觀測部分，它圍繞觀測矩陣展開觀測器的設計目的是如何采樣得到個觀測值，并保證從中能重構出長度為的信號或者基下等價的稀疏系數(shù)向量。顯然，如果觀測過程破壞了中的信息，重構是不可能的。觀測過程實際就是利用觀測矩陣的個行向量對稀疏系數(shù)向量進行投影，即計算和各個觀測向量之間的內積，得到個觀測值，記觀測向量，即 (2.5)這里，采樣過程是非自適應的，也就是說，無須根據(jù)信號而變化，觀測的不再是信號的點采樣而是信號的更一般的線性泛函。對于給定的從式(2.5)中

12、求出是一個線性規(guī)劃問題，但由于，即方程的個數(shù)少于未知數(shù)的個數(shù)，這是一個欠定問題，一般來講無確定解。然而，如果具有- 項稀疏性()，則該問題有望求出確定解。此時，只要設法確定出中的個非零系數(shù)的合適位置，由于觀測向量是這些非零系數(shù)對應 的個列向量的線性組合，從而可以形成一個的線性方程組來求解這些非零項的具體值。對此，有限等距性質給出了存在確定解的充要條件。這個充要條件和Candes、Tao等人提出的稀疏信號在觀測矩陣作用下必須保持的幾何性質相一致。即，要想使信號完全重構，必須保證觀測矩陣不會把兩個不同的-項稀疏信號映射到同一個采樣集合中，這就要求從觀測矩陣中抽取的每個列向量構成的矩陣是非奇異的。從

13、中可以看出，問題的關鍵是如何確定非零系數(shù)的位置來構造出一個可解的線性方程組。然而，判斷給定的是否具有RIP性質是一個組合復雜度問題。為了降低問題的復雜度，能否找到一種易于實現(xiàn)RIP條件的替代方法成為構造觀測矩陣的關鍵。文獻10指出如果保證觀測矩陣和稀疏基不相干，則在很大概率上滿足RIP性質。不相干是指向量不能用稀疏表示。不相干性越強，互相表示時所需的系數(shù)越多；反之，相關性則越強通過選擇高斯隨機矩陣作為即可高概率保證不相干性和RIP性質。例如，可以生成多個零均值、方差為1/的隨機高斯函數(shù)，將它們作為觀測矩陣的元素，使得以很高的概率具有RIP性質。隨機高斯矩陣具有一個有用的性質：對于一個的隨機高斯

14、矩陣，可以證明當McKlog(NK)時 在很大概率下具有RIP性質(其中c是一個很小的常數(shù))。因此可以從個觀測值中以很高的概率去恢復長度為的- 項稀疏信號?？傊S機高斯矩陣與大多數(shù)固定正交基構成的矩陣不相關，這一特性決定了選它作為觀測矩陣，其它正交基作為稀疏變換基時，滿足RIP性質。為進一步簡化觀測矩陣，在某些條件下，以隨機為元素構成的Rademacher矩陣也可以證明具有RIP性質和普適性。對觀測矩陣的研究是壓縮感知理論的一個重要方面。Donoho給出了觀測矩陣所必需具備的三個條件，并指出大部分一致分布的隨機矩陣都具備這三個條件，均可作為觀測矩陣，如：部分Fourier集、部分Hadama

15、rd集、一致分布的隨機投影(uniform Random Projection)集等，這與對RIP性質進行研究得出的結論相一致。但是，使用上述各種觀測矩陣進行觀測后，都僅僅能保證以很高的概率去恢復信號，而不能保證百分之百地精確重構信號。對于任何穩(wěn)定的重構算法是否存在一個真實的確定性的觀測矩陣仍是一個有待研究的問題。2.3 信號重構如何設計快速重構算法，從線性觀測中恢復信號，是第三步要將解決的問題，即信號的重構問題。在壓縮感知理論中，由于觀測數(shù)量遠小于信號長度，因此不得不面對求解欠定方程組的問題。表面上看，求解欠定方程組似乎是無望的，但是，文獻8和4均指出由于信號是稀疏的或可壓縮的，這個前提從根

16、本上改變了問題，使得問題可解，而觀測矩陣具有RIP性質也為從個觀測值中精確恢復信號提供了理論保證。為更清晰地描述壓縮感知理論的信號重構問題，首先定義向量的范數(shù)為： (2.6)當時得到范數(shù)，它實際上表示中非零項的個數(shù)。于是，在信號稀疏或可壓縮的前提下，求解欠定方程組的問題轉化為最小范數(shù)問題： s.t. (2.7)但是，它需要列出中所有非零項位置的備種可能的線性組合，才能得到最優(yōu)解。因此，求解式(2.7)的數(shù)值計算極不穩(wěn)定而且是NP難問題。注意，這和稀疏分解問題從數(shù)學意義上講是同樣的問題。于是稀疏分解的已有算法可以應用到CS重構中。Chen，Donoho和Saunders指出，求解一個更加簡單的優(yōu)

17、化問題會產生同等的解(要求和不相關)： s.t. (2.8)稍微的差別使得問題變成了一個凸優(yōu)化問題，于是可以方便地化簡為線性規(guī)劃問題，典型算法代表：BP算法盡管BP算法可行，但在實際應用中存在兩個問題：第一，即使是常見的圖像尺寸，算法的計算復雜度也難以忍受，在采樣點個數(shù)滿足，時，重構計算復雜度的量級在；第二，由于范數(shù)無法區(qū)分稀疏系數(shù)尺度的位置，所以盡管整體上重構信號在歐氏距離上逼近原信號，但存在低尺度能量搬移到了高尺度的現(xiàn)象，從而容易出現(xiàn)一些人工效應，如一維信號會在高頻出現(xiàn)振蕩?；谏鲜鰡栴}，2005年1月Candes和Romberg提出了不同的信號恢復方法，該方法要求對原信號具有少量的先驗知

18、識，同時也可以對所求結果施加適當?shù)钠谕匦?，以約束重構信號的特性。通過在凸集上交替投影的方法，可以快速求解線性規(guī)劃問題。Tropp和Gilbert提出利用匹配追蹤(MP)和正交匹配追蹤(OMP)算法來求解優(yōu)化問題重構信號，大大提高了計算的速度，且易于實現(xiàn)。樹形匹配追蹤(TMP)算法是2005年La和NDo提出的。該方法針對BP、MP和OMP方法沒有考慮信號的多尺度分解時稀疏信號在各子帶位置的關系，將稀疏系數(shù)的樹型結構加以利用，進一步提升了重構信號的精度和求解的速度。匹配追蹤類算法都是基于貪婪迭代算法，以多于BP算法需要的采樣數(shù)目換取計算復雜度的降低。例如OMP算法，需要，個采樣點數(shù)才能以較高的概率恢復信號，信號重構的計算復雜度為。2006年Donoho等人提出了分段正交匹配追蹤(STOMP，stagewise OMP)算法。它將OMP進行一定程度的簡化，以逼近精度為代價進一步提高了計算速度(計算復雜度為O(N)，更加適合于求解大規(guī)模問題。匹配追蹤類方法為其近似求解提供了有力工具，且該類方法用于