馮俊杰　季立貴

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

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

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

由圖1、圖2、圖3可以看出，ROMP算法耗時最短。隨著信號稀疏度的增加，信號重構的概率逐漸減小，均方誤差逐漸增多，當稀疏度低于20時，三種算法都可100%的重構原信號，隨著稀疏度的增加，ROMP算法和OMP算法重構性能快速下降，當稀疏度為40時，SAMP算法仍以較高概率重構出原始信號。SAMP算法由于迭代次數(shù)增加導致運算量大，其重構時間也較長。

4 總結(jié)

本文基于壓縮感知基本原理，分析了在噪聲環(huán)境中三種常見的貪婪迭代稀疏信號重構算法的性能。比較了隨著稀疏度的改變，三種重構算法重構時間、重構概率和均方誤差的變化情況。仿真實驗結(jié)果表明，在相同實驗條件下，ROMP的運行時間最短，SAMP的重構性能優(yōu)于ROMP和OMP算法，在實際應用中，可以綜合考慮三種算法的重構性能進行選擇。

參考文獻：

[1] Donoho D L.Compressed Sensing[J].IEEE Trans on Information Theory，2006，52（4）： 1289-1306.

[2] Goyal V K，F(xiàn)letcher A K，Rangan S.Compressive Sampling and Lossy Compression[J].IEEE Signal Processing Magazine，2008， 25（2）： 48-56.

[3] 楊海蓉，張成，丁大為，等.壓縮傳感理論與重構算法[J].電子學報， 2011， 39（1）： 142-148.

[4] 解成俊，張鐵山.基于壓縮感知理論的圖像重構算法研究[J].計算機應用與軟件，2012，29（4）：49-52.

[5] 方紅，章權兵，韋穗.基于亞高斯隨機投影的圖像重建方法[J].計算機研究與發(fā)展，2008，45（ 8） ： 1402-1407.

[6] 郭海燕，楊震.基于近似KLT域的語音信號壓縮感知[J].電子與信息學報，2009，31（12） ： 2948-2952.

[7] 梁瑞宇，鄒采榮，趙力，等.語音壓縮感知及其重構算法[J].東南大學學報：自然科學版，2011，41（1）：1-5.

[8] Tropp J， Gilber t A.Signal recovery from random measurements via orthogonal matching pursuit[J].Transactions on Information Theory， 2007， 53（12）：4655-4666.

[9] Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of Computational Mathematics， 2009，9（3） ：317-334.

[10] Thong T D，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing [C].Asilomar Conference on Signals，Systems，and Computers，Pacific Grove，California，2008，10： 581-587.