郭永紅，楊毅彬

一種稀疏自適應(yīng)的正交互補(bǔ)匹配追蹤算法

郭永紅，楊毅彬

針對(duì)實(shí)際應(yīng)用中信號(hào)稀疏度未知的缺點(diǎn)，提出了一種稀疏度自適應(yīng)的正交互補(bǔ)匹配追蹤算法。算法先初始化稀疏度，再通過互補(bǔ)正交匹配追蹤重構(gòu)信號(hào)，找到一個(gè)支撐集；若支撐集不滿足條件，則按指定步長(zhǎng)增加稀疏度，再次運(yùn)用算法進(jìn)行重構(gòu)，直到支撐集滿足條件，得到最優(yōu)支撐集。實(shí)驗(yàn)結(jié)果表明，該算法可以準(zhǔn)確有效地重構(gòu)信號(hào)，并且在相同壓縮比下，其重構(gòu)質(zhì)量（PSNR）優(yōu)于其他幾種算法。

稀疏度；正交互補(bǔ)；指定步長(zhǎng)；支撐集

1 引言

Nyquist采樣理論在傳統(tǒng)的信號(hào)理論中起著關(guān)鍵作用，它要求采樣頻率須為信號(hào)帶寬的兩倍。壓縮感知理論（Compressed Sensing，CS）[1-2]表示如果信號(hào)在某個(gè)變換域上稀疏，則可將信號(hào)投影到一個(gè)低維空間，然后利用投影值通過求解范數(shù)最優(yōu)化問題，可高概率地精確重建原始信號(hào)。CS理論表明恢復(fù)信號(hào)所需要的采樣數(shù)據(jù)遠(yuǎn)低于Nyquist定理所定義的采樣量，因此該理論一經(jīng)出現(xiàn)就引起國(guó)內(nèi)外相關(guān)領(lǐng)域研究人員的密切關(guān)注。設(shè)信號(hào)x(x∈RN) 為N×1維列向量。若 x中僅有不超過k(k＜＜N)個(gè)非零元素，則x稱為k-稀疏信號(hào)。用一個(gè)M×N(M＜＜N)維的測(cè)量矩陣對(duì)信號(hào)進(jìn)行投影，即 y=Φx，則基于 y可對(duì)信號(hào)進(jìn)行重構(gòu)。

在已知 y和Φ的條件下對(duì)信號(hào)x進(jìn)行重構(gòu)是CS研究的一個(gè)重要方面。目前重建算法主要分為兩類：一類是基于l1范數(shù)最小化的凸優(yōu)化算法，主要包括基追蹤算法（Basis Pursuit，BP）[3]、梯度追蹤算法（Gradient Pursuit，GP）[4]、內(nèi)點(diǎn)迭代法等；另一類是基于l0范數(shù)最小化的貪婪算法，主要包括匹配追蹤（Matching pursuit，MP）[5]、正交匹配追蹤（Orthogonal Matching Pursuit，OMP）[6]、互補(bǔ)匹配追蹤（Complementary Matching Pursuit，CMP）[7]、正交互補(bǔ)匹配追蹤算法（Orthogonal Complementary Matching Pursuit，OCMP）[8]、正則化正交匹配追蹤算法（Regularized Orthogonal Matching Pursuit，ROMP）[9]等。貪婪算法由于結(jié)構(gòu)簡(jiǎn)單，運(yùn)算量小等特點(diǎn)得到應(yīng)用。但這幾種算法均要求信號(hào)稀疏度已知，這在很多實(shí)際應(yīng)用中很難滿足，如果對(duì)稀疏度的估計(jì)不準(zhǔn)確，信號(hào)將不能得到精確重建。針對(duì)實(shí)際信號(hào)中稀疏度未知的特點(diǎn)，本文結(jié)合文獻(xiàn)[10]提出的自適應(yīng)匹配追蹤算法（Sparsity Adaptive Matching Pursuit，SAMP），提出一種稀疏度自適應(yīng)的迭代算法，采用增加固定原子的方法來(lái)估計(jì)稀疏度。

2 正交互補(bǔ)匹配追蹤算法

文獻(xiàn)[7]互補(bǔ)匹配追蹤算法（CMP）類似于經(jīng)典匹配追蹤算法（MP），與其不同的是CMP算法是直接在原信號(hào)x的行空間上求解。每次迭代時(shí)，MP算法是從字典矩陣中選擇一個(gè)最匹配的原子；CMP則是剔除(N-1)不匹配的原子并保留剩下的一個(gè)最匹配的原子，這種方法使其具有比MP算法更好的重建效果。

文獻(xiàn)[8]提出的正交互補(bǔ)匹配追蹤算法（OCMP）是CMP的改進(jìn)算法。OCMP算法在選擇原子上與CMP一樣，稀疏估計(jì)時(shí)采用最小二乘法對(duì)信號(hào)進(jìn)行估計(jì)，算法步驟如下：

（1）初始化殘差r0=b，感知矩陣Φ=A+A，測(cè)量向量x2=A+b，對(duì)角矩陣Δ，其對(duì)角元素為：

其中A+=AT(AAT)-1為A的偽逆。

（2）計(jì)算相關(guān)性h，并尋找h中絕對(duì)值最大的元素：

（3）信號(hào)稀疏估計(jì)并更新殘差：

其中，I表示h中元素最大值的索引值構(gòu)成的集合；當(dāng)殘差r滿足停止條件時(shí)，迭代停止。

從上文可以看出，算法主要分為三個(gè)部分：計(jì)算相關(guān)性；更新索引集；更新殘差。算法在每次迭代時(shí)只找到信號(hào)的一個(gè)元素，對(duì)于稀疏度為k的信號(hào)，至少需要進(jìn)行k次迭代才能恢復(fù)出原信號(hào)。如果稀疏度的估計(jì)不夠準(zhǔn)確，那么估計(jì)信號(hào)的誤差將會(huì)很大。

3 改進(jìn)算法

在實(shí)際生活中信號(hào)稀疏度往往未知，針對(duì)于此，本文提出了一種自適應(yīng)迭代算法——稀疏自適應(yīng)正交互補(bǔ)匹配追蹤算法（Sparsity Adaptive Orthogonal Complementary Matching Pursuit，SAOCMP）。主要思想是先初始化稀疏度，其值隨指定步長(zhǎng)進(jìn)行增加，然后對(duì)算法進(jìn)行迭代，每次迭代都會(huì)找到信號(hào)的一個(gè)支撐集，再利用回溯思想更新上一次找到的支撐集，直至找到最終支撐集，從而達(dá)到重構(gòu)信號(hào)的目的。本文算法框圖如圖1。

圖1 算法框圖

根據(jù)框圖，下面對(duì)算法的步驟進(jìn)行具體闡述。

3.1 算法步驟

（1）算法輸入：字典矩陣A，測(cè)量向量s。初始化殘差值r0=s，迭代誤差δ，重構(gòu)向量re_x，感知矩陣Φ=A+A，測(cè)量向量x2=A+s，對(duì)角矩陣Δ，其對(duì)角元素為：

步長(zhǎng)step=1，信號(hào)支撐集Fk=[]。

（2）初始測(cè)試：計(jì)算第k次迭代的相關(guān)性，并找出前step個(gè)最大值S：

（3）候選支撐集C：

（4）最終測(cè)試：估計(jì)信號(hào)并求出前step個(gè)最大的元素Fk：

其中，ΦC為候選支撐集C對(duì)應(yīng)的感知矩陣Φ的列向量組成的矩陣。

（5）計(jì)算殘差rk：

（6）若norm(rk)≥norm(rk-1)，則i=i+1；step=i×stage，返回步驟（2），否則直接返回步驟（2）。其中stage為固定步長(zhǎng)。

（7）當(dāng)估計(jì)信號(hào)與原始信號(hào)的差值小于迭代誤差δ時(shí)，則迭代停止。輸出重構(gòu)向量re_x，滿足：

3.2 信號(hào)重建實(shí)驗(yàn)

本實(shí)驗(yàn)對(duì)CMP、OCMP、SAOCMP、CMP-OMP算法進(jìn)行一維仿真，比較各個(gè)算法的相對(duì)誤差和運(yùn)行時(shí)間。實(shí)驗(yàn)測(cè)試當(dāng)M=128，稀疏度k和采樣點(diǎn)數(shù)M取不同值時(shí)算法運(yùn)行的結(jié)果。SAOCMP中初始步長(zhǎng)step=1，終止條件為估計(jì)信號(hào)與原始信號(hào)殘差能量小于δ=e-12；算法在Pentium Dual-core E5400機(jī)器上運(yùn)行，軟件版本為Matlab R2008a。對(duì)于不同的值，算法運(yùn)行100次來(lái)計(jì)算平均重構(gòu)誤差和平均運(yùn)行時(shí)間。

圖2表示不同采樣點(diǎn)下信號(hào)準(zhǔn)確重構(gòu)率。從圖中可以看出本文算法在收斂速度是最快的，即在相同的準(zhǔn)確重構(gòu)率下，SAOCMP算法所需的采樣點(diǎn)數(shù)是最小的。對(duì)于重建誤差，當(dāng)各個(gè)算法取相同采樣點(diǎn)時(shí)，SAOCMP算法與CMP、OCMP、CMP-OMP算法相比，其誤差是最小的，如表1所示。

圖2 準(zhǔn)確重建率對(duì)比分析

表1 不同采樣點(diǎn)數(shù)下重建誤差比較

圖3是在稀疏度相同、采樣點(diǎn)數(shù)不同的情況下重建信號(hào)的平均運(yùn)行時(shí)間。從圖中可以看出，當(dāng)M大于30時(shí)，SAOCMP算法的運(yùn)行時(shí)間要小于OCMP。從重建誤差角度來(lái)分析，當(dāng)各個(gè)算法取相同稀疏度時(shí)，與OCMP、CMP、CMP-OMP算法相比，SAOCMP算法具有重建誤差最小的優(yōu)點(diǎn)，如表2所示。

圖3 運(yùn)行時(shí)間對(duì)比分析

表2 不同稀疏度下重建誤差比較

4 圖像實(shí)驗(yàn)

實(shí)驗(yàn)采用256×256像素的Lena圖像，采樣矩陣為隨機(jī)采樣矩陣，SAOCMP算法中步長(zhǎng)stage=2。實(shí)驗(yàn)比較了各個(gè)算法重建的運(yùn)算時(shí)間、均方誤差MSE和峰值信噪比PSNR。圖4給出了壓縮比M/N=0.5時(shí)CMP、OCMP、SAOCMP、CMP-OMP算法的重建效果。由圖可見在壓縮比相同的情況下，SAOCMP算法的圖像重建效果要比其他算法更好。表3給出了不同算法重建圖像的運(yùn)算時(shí)間、均方誤差MSE和峰值信噪比PSNR。從表中可以看出，當(dāng)各算法具有相同壓縮比時(shí)，SAOCMP的PSNR最大，MSE最小。從運(yùn)行時(shí)間角度分析，該算法犧牲了時(shí)間而獲得了更低的重構(gòu)誤差，因此如何在保持低誤差的情況下減少運(yùn)行時(shí)間是今后研究的方向。

表3 各算法重建時(shí)間與性能比較

圖4 各算法重建圖像對(duì)比（M/N=0.5）

5 結(jié)論

本文提出了一種新的壓縮感知信號(hào)重構(gòu)算法——稀疏自適應(yīng)正交互補(bǔ)匹配追蹤算法。通過初始化稀疏度，并且在每次迭代后隨指定步長(zhǎng)增加，利用回溯思想不斷估計(jì)和更新支撐集，直至滿足迭代停止條件為止。

實(shí)驗(yàn)結(jié)果表明，本文算法可以在稀疏度未知的先驗(yàn)條件下重建信號(hào)，并且能夠保證重建的準(zhǔn)確率，同時(shí)減少了運(yùn)行時(shí)間。經(jīng)實(shí)驗(yàn)證明，本文算法的重建質(zhì)量無(wú)論是一維信號(hào)還是二維圖像上都優(yōu)于現(xiàn)有同類算法，是一種重建效果較好的方法。

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

[2]Candes E J.Compressive sampling[C]//Proceedings of InternationalCongresson Mathematicians.Zurich Switzerland：European MathematicalSociety Publishing House，2006：1433-1452.

[3]Chen S B，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit[J].SIAM Journal on Scientific Computing，1998，20（1）：33-61.

[4]Blumensath T，Davies M E.Gradient pursuit[J].IEEE Trans on Signal Process，2008，56（6）：2370-2382.

[5]Mallat S，Zhang Z.Matching pursuits with time-frequency dictionaries[J].IEEE Trans Signal Process，1993，41（12）：3397-3415.

[6]Tropp J，Gilbert A.Signal recovery from random measurements viaorthogonal matching pursuit[J].IEEE Trans on Inform Theory，2008，53（12）：4655-4666.

[7]Rath G，Guillemot C.A complementary matching pursuit algorithm for sparse approximation[C]//Proceedings of European Signal Processing Conference，Aug 2008.

[8]Rath G，Guillemot C.Sparse approximation with an orthogonal complementary matching pursuitalgorithm[C]//Proceedings of IEEE International Conference on Aconstics，Speech and Signal Processing，2009，3：3325-3328.

[9]Needell D，Vershynin D.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of Computational Mathematics，2009（3）：317-334. [10]Do T T，Lu G，Nguyen N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]// Proc Asilomar Conference on Signals，Systems and Computers，Pacific Grove，California，2008，10：581-587.

GUO Yonghong,YANG Yibin

電子科技大學(xué) 電子科學(xué)技術(shù)研究院，成都 611731

Research Institute of Electronic Science and Technology,University of Electronic Science and Technology of China,Chengdu 611731,China

A novel sparsity adaptive orthogonal complementary matching pursuit algorithm is proposed when the sparsity is unknown.Signal is reconstructed by complementary orthogonal matching pursuit through initializing the sparsity,and a signal support can be determined.If the condition is not be reached,the sparsity is increased with specified steps,and the algorithm is re-used to reconstruct signal.The algorithm terminates when the condition is reached and the support is founded.Experimental results show that signal can be reconstructed accurately and effectively.Meanwhile,the proposed algorithm exhibits its superiority over other algorithms with the same compressed ratio.

sparsity;orthogonal complementary;specified steps;support

A

TN850.6；TP753

10.3778/j.issn.1002-8331.1108-0281

GUO Yonghong,YANG Yibin.Sparsity adaptive orthogonal complementary matching pursuit algorithm.Computer Engineering and Applications,2013,49（7）：144-146.

郭永紅（1987—），男，碩士研究生，主要研究方向?yàn)殡娮优c通信工程；楊毅彬（1982—），男，助理研究員，主要研究方向?yàn)殡姶艌?chǎng)理論及其應(yīng)用。E-mail：guoyonghong52400@163.com

2011-08-22

2011-10-17

1002-8331（2013）07-0144-03