馮俊杰　季立貴

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

關(guān)鍵詞：壓縮感知；稀疏度；貪婪算法；信號重構(gòu)

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

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

4 總結(jié)

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

參考文獻(xiàn)：

[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] 楊海蓉，張成，丁大為，等.壓縮傳感理論與重構(gòu)算法[J].電子學(xué)報(bào)， 2011， 39（1）： 142-148.

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

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

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

[7] 梁瑞宇，鄒采榮，趙力，等.語音壓縮感知及其重構(gòu)算法[J].東南大學(xué)學(xué)報(bào)：自然科學(xué)版，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.