壓縮感知中貪婪重構算法研究

馮俊杰　季立貴

摘要：壓縮感知理論是利用信號的稀疏性，通過少量的觀測值就可以實現對該信號的精確重構。貪婪類算法是壓縮感知重構步驟中廣泛應用的一類算法。該文主要對該類算法中典型的三種算法在存在噪聲環境中進行了綜合分析比較。首先從理論方面分析了三種算法，給出了實現過程；然后在不同稀疏度情況下，對三種貪婪算法重構性能進行綜合比較。根據理論分析結果和仿真結果，得出相應的結論。

關鍵詞：壓縮感知；稀疏度；貪婪算法；信號重構

中圖分類號：TN911.72 文獻標識碼：A 文章編號：1009-3044（2014）31-7351-03

Abstract：Compressive sensing is a novel signal sampling theory under the condition that the signals are sparse.In this case，the small amount of signal values can be reconstructed accurately. Greedy algorithm is one class of the algorithms used most widely in CS signal reconstruction.In this paper， the three classic greedy algorithms are analyzed and compared theoretically in noise condition with different sparsity level，by the analysis and simulation result，the conclusion is obtained.

Key words：compressive sensing； sparsity； greedy algorithm； signal reconstruction

與奈奎斯特采樣定理不同，壓縮感知理論（Compressive sensing，CS）[1-3]利用信號的稀疏性，將采樣與壓縮同時進行，通過求解一個優化問題就可從少量的測量值中以高概率重構出原信號。CS理論改變了傳統的采樣方式，極大的降低了采樣率，降低了數據獲取、傳輸及處理的壓力，在圖像信號處理[4-5]、語音信號處理[6-7]等方面得到廣泛的應用。壓縮感知主要包括三個方面即：信號的稀疏表示，線性測量，重構算法。其中稀疏信號重構算法是該理論的至關重要的環節，貪婪迭代算法具有計算復雜度較低等優點，應用范圍相對較廣。該類算法的基本思想是在每次迭代時通過局部最優化，尋找各非零系數的位置，選擇一個局部最優解來逐步逼近原始信號。貪婪迭代算法主要包括正交匹配追蹤算法（OMP）[[8]]、正則正交匹配追蹤算法（ROMP）[[9]]、稀疏度自適應匹配追蹤法算法（SAMP）[[10]]等。該文將主要研究和分析上述三類貪婪迭代算法在存在噪聲情況下的重構特性， 通過仿真實驗比較各個算法的性能特點。……