《壓縮感知理論分析綜述》4800字

壓縮感知理論分析綜述目錄TOC\o"1-3"\h\u51壓縮感知理論分析綜述 159951.1壓縮感知概述 1303611.1.1壓縮感知簡介 1156791.1.2信號的稀疏度表示 311941.1.3測量矩陣的設計 5175401.1.4壓縮感知重構算法 6189661.2壓縮感知貪婪重構算法 750431.2.1SAMP算法 8273431.2.2OMP算法 91.1壓縮感知概述2004年，Donoho、Candes以及Romberg等人正式提出了壓縮感知理論，該理論認為，如果信號具有稀疏特性，那么就可以通過較少的采樣值高概率地恢復出原始信號。這一理論的提出彌補了奈奎斯特（Nyquist）采樣定理對采樣速率要求過高的不足，為信號處理研究提供了新的方向。大量的物理實驗表明，實際的無線多徑信道普遍呈現出稀疏結構，即信道的多條傳播路徑中的能量往往集中在幾條路徑上。伴隨著稀疏信道概念的普及與壓縮感知理論的逐漸成熟，基于壓縮感知的信道估計技術被運用在越來越多的無線通信系統中。1.1.1壓縮感知簡介壓縮感知(CS)，又稱壓縮感知、壓縮采樣和稀疏采樣，是一種為欠定線性系統提供稀疏解的技術。在工程中，CS是利用先驗信息的稀疏性或可壓縮性來獲取和重構信號的過程。壓縮感知理論是在數據采樣的同時完成壓縮過程，其數學形式是將一個高維信號通過特定的矩陣投射到低維空間。重構時，采用線性或非線性重構算法對原始信號進行重構。壓縮感知理論框架主要由信號的稀疏表示、編碼測量以及重構算法的設計這三個部分組成。其中，信號的編碼測量和重構是基于信號的可稀疏性。編碼時，測量矩陣的選取應滿足有限等距準則(RestrictedIsometryProperty,RIP),即觀測矩陣的選取應滿足與稀疏基不相關的原則。壓縮感知采樣原理如1.1所示。圖1.1壓縮感知采樣原理框圖假如某信號x是長度為N的一維可壓縮的信號，其稀疏形式可以表示為式(22)。x=Ψθ其中，中是標準的正交基，θ是K(K<<N)稀疏表示系數。通過測量矩陣Φ∈Ry=ΦθA=ΦΨy=Aθ上式中,A∈R整個壓縮感知理論的線性測量過程可以用圖1.2表示。圖1.2壓縮感知線性測量過程對于信號重構問題，就是通過優化算法獲得一個最稀疏的解θ，然后通過反演稀疏解獲得原始信號的估計值x，其重構示意圖如圖1.3所示。圖1.3壓縮感知信號重構過程1.1.2信號的稀疏度表示如果信號只有很少的非零元素，那么這個信號就是稀疏的。通常，時域下的自然信號都是明顯非稀疏的，不能直接進行壓縮感知處理信號，但是將信號投影到某些變換域(如空間頻域)時就是稀疏的，經稀疏變換后的信號即可應用壓縮感知處理。信號的稀疏性還可以理解為:變換系數中有K個較大值系數，其他N-K個系數等于或接近于零,則可以認為該信號是K系數信號。如一副自然場景圖像,它的像素幾乎都不為零,經過小波變換后,頻域大部分系數趨近于零,因此，直接處理有限個非零系數就可以重構整個圖像的信息。假設信號x∈RN×1,則可以用一組基向量x=i=1其中，Θ∈RN×1是標準正交基下信號的稀疏表示。當信號x在正交基Ψ下稀疏系數θ只有K(K<<N)非零元素，那么我們就說稀疏向量θ可以從測量值y中重構出來,也就是求解一個有正則約束的線性方程問題。相關理論表明該線性方程可以通過求解式(30)最優l0θ=argmin其中，θ0表示零范數，即向量中非0元素的數量。如果直接求解上式則是一個NP-hard問題且求解的數值不穩定。后來有人證明當測量矩陣滿足RIP條件時，可以將求解最小l0范數問題可以轉化為求解最小θ=argmin對于含噪聲的信號y=Aθ+εθ=argmin這類算法稱為LP(線性規劃)重構算法。對于任意參數λ,之前的約束優化求解將轉化為無約束優化問題，其等價形式如式(33)。min1根據稀疏基Ψ=ψ1.1.3測量矩陣的設計測量矩陣(也稱觀測矩陣)是用來對N維的稀疏信號進行觀測得到M(M<<N)維的觀測向量y,而目標信號x可以利用凸優化等方法從該觀測值y中重構出來。因此，理想的測量矩陣是能夠實現采樣得到M個觀測值，并確保能從這M個值中重構出長度為N的信號x(或是等價的稀疏系數向量值)。為了保證壓縮感知算法中測量矩陣能夠較準確重構信號，其需要滿足如下一些的條件:(1)約束等距性原則(RestrictedIsometryProperty,RIP)，該原則定義如下:對于任意信號x假設其稀疏度為K,若存在常數δk1?δ則矩陣Φ滿足K階RIP原則。觀測基矩陣Φ與稀疏基矩陣Ψ的乘積矩陣A稱之為測量矩陣(傳感矩陣)，該矩陣同樣需要滿足RIP原則，即存在常數δk1?δ但在實際應用中，測量矩陣是很難滿足這個條件的,因為通常情況下稀疏正交基Ψ是固定的,這樣只能改變測量矩陣Φ，,由于向量θ∈k，因此驗證矩陣的RIP原則非常困難。后來有研究提出了一個與RIP原則等價的條件即:測量矩陣Φ與正交基(2)不相關原則，該原則在實際應用中驗證相對較易，測量矩陣φ與正交基之間的相關系數定義如下:μΦ其中，?i∈1,2,...,M和ψj∈1,2,...,N分別表示矩陣測量矩陣的形式也有很多，經過學者們的大量研究與總結，目前常用的測量矩陣主要分為以下兩大類。(1)隨機測量矩陣:主要有隨機高斯矩陣，隨機伯努利矩陣等，這類矩陣雖然重構能力和適應性較好，但是計算復雜，大儲存量，硬件難以實現，而且重構效果相對不穩定。經發現隨機高斯測量矩陣適用于大部分信號的壓縮重構，因此，在研究重構算法實驗中一般用隨機高斯矩陣作為測量矩陣。(2)確定性測量矩陣:主要有循環測量矩陣、托普利茨測量矩陣、多項式測量矩陣等。這類測量矩陣計算復雜度相對較低，硬件易于實現而且信號重構效果較穩定，但是大部分確定性測量矩陣重構精度比較低，適應性還比較弱。目前，很多科研人員綜合分析這兩種矩陣的優劣勢，提出了一系列偽隨機確定性測量矩陣的構造方法，如多項式構造的測量矩陣，代數曲線構造的測量矩陣，混沌序列構造的測量矩陣等。1.1.4壓縮感知重構算法信號經過編碼測量后，要想重構原始信號必須要進一步重構,該步驟就需用到重構算法，也是壓縮感知理論最核心的一步。目前，常用的壓縮感知重構算法類型可以分為凸優化算法、貪婪算法和組合算法。凸優化算法是將非凸問題轉化為凸問題來求解的，如基追蹤算法（BP）算法、梯度投影法、內點法和迭代閾值法。凸優化算法可以保證解的唯一性，但凸優化算法比貪婪算法要求更高的計算復雜度。信號組合算法支持群測試和快速重建，如傅里葉采樣和鏈跟蹤等，但應用較少。貪婪算法在每一次迭代中求解一個局部最優解，逐步逼近原始信號。與其他兩種方法相比，貪婪算法因其運行速度快、重構效果好、復雜度低而得到了廣泛的應用，如匹配追蹤算法（MP）、正交匹配追蹤算法（OMP）、壓縮采樣匹配追蹤算法（CoSaMP)、稀疏度自適應匹配追蹤算法（SAMP）等。圖1.4重用重構算法分類最早提出的貪婪算法是正交匹配追蹤(OMP)。OMP只選擇最匹配的原子重構信號，計算復雜度較低。正則化正交匹配追蹤算法(ROMP)改變了基于OMP的原子選擇機制，增加了正則化過程。子空間追蹤算法(SP)引入了基于OMP和ROMP的回溯來實現原子刪除選擇功能。上述算法都要求以稀疏度K作為優先級，這在實際應用中可能是不可用的。為了克服這一缺點，提出了稀疏性自適應匹配追蹤(SAMP)算法，該算法在不知道稀疏性的情況下，將恢復過程分為固定步長的幾個階段進行信號重建。但是，固定的步長會導致重建時間長或恢復不準確。1.2壓縮感知貪婪重構算法壓縮感知貪婪算法是通過選擇合適的原子并經過一系列的逐步遞增的方法實現信號矢量的逼近來重構出信號的。利用貪婪算法重構信號時，先對各項參數進行初始化設置，然后添加原子到支撐集，然后從支撐集中刪除部分原子，更新殘差，若達到迭代停止條件，則產生重構信號；若未達到迭代停止條件，則繼續添加原子，并重復之后步驟。一般貪婪算法框架如圖1.5所示。圖1.5一般貪婪算法框架1.2.1SAMP算法壓縮感知是近年來出現的一種新的信號處理技術，其出現具有跨時代的意義。而重構算法是壓縮感知的核心理論。重構算法能夠在低維樣本數的情況下準確地恢復原始信號，這對信號采樣理論具有重要意義，這意味著它可以突破傳統Nyquist采樣律的局限性。SAMP算法是ThongT.Do在2008年提出的，它不需要稀疏性作為重建的先驗信息，這使得它在許多實際應用中很有用，特別是當信號的非零值的數目未知時。稀疏自適應匹配跟蹤(SAMP)算法是一種自底向上和自頂向下相結合的方法。顧名思義，SAMP算法無需已知目標信號的稀疏度信息，通過自適應的思想調整迭代步長來逐漸逼近待重構信號稀疏度,這是該算法最大的優勢也是與其它貪婪迭代算法的不同之處。SAMP算法在迭代過程分為多個階段，在每個階段可能有多次迭代，該階段中信號的支撐集大小保持不變,過度到下一個階段時支撐集的大小會因步長的增加而改變。SAMP算法每個階段選取支撐集方法跟壓縮采樣匹配追蹤算法類似，也是通過選取傳感矩陣和殘差的相關系數模中最大的一-些值對應的索引值構成候選集，然后經過迭代從該候選集中選出指定數目原子作為支撐集。SAMP算法具體流程如下：輸入:矩陣Φ,信號為b,步長為S,終止算法閾值ε.輸出:重構信號x*初始化:r0=b，Λ0=(1)初步選擇.u=absΦ擴充支撐集和支撐集對應矩陣.令Λn=Λn?1∪求最小二乘解.令Xn=argmin(4)對Xn的絕對值進行降序處理，選擇前L個最大的對應列記為本步迭代的支撐集Λn,對應支撐集原子矩陣為(5)更新殘差.r(6)如果殘差rn2<ε1.2.2OMP算法OMP算法是經典的貪婪迭代算法，為了克服匹配追蹤(MatchingPursuit，MP)算法收斂過慢的缺點，同時保證重建結果具有較高的精確度，在迭代過程中正交化處理已選原子，期望能有效減少迭代次數，達到快速收斂的目的。該算法詳細步驟如下:輸入:矩陣中Φ∈RM×輸出:重構信號x*.初始化:r0=b,(1)找到索引λn.λn(2)擴充支撐集和支撐集對應矩陣，令Λn=(3)求最小二乘解、令Xn=argmin(4)更新殘差r(5)n=n+1,當n≤k,返回(1)重新迭代.反之結束算法.上述算法先進行初始化，然后計算恢復矩陣和當前殘差的內積，從中選出最大的元素所對應的索引，即相關性最大的原子，將其放入索引集;