壓縮感知中貪婪重構(gòu)算法研究

馮俊杰　季立貴

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

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

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

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

4 總結(jié)

本文基于壓縮感知基本原理，分析了在噪聲環(huán)境中三種常見(jiàn)的貪婪迭代稀疏信號(hào)重構(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域的語(yǔ)音信號(hào)壓縮感知[J].電子與信息學(xué)報(bào)，2009，31（12） ： 2948-2952.

[7] 梁瑞宇，鄒采榮，趙力，等.語(yǔ)音壓縮感知及其重構(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.