一種改進(jìn)的稀疏度自適應(yīng)壓縮采樣匹配追蹤算法*

倪加明，孫欽者，陸家明

（杭州電子科技大學(xué) 通信工程學(xué)院，浙江 杭州 310018）

一種改進(jìn)的稀疏度自適應(yīng)壓縮采樣匹配追蹤算法*

倪加明，孫欽者，陸家明

（杭州電子科技大學(xué) 通信工程學(xué)院，浙江 杭州 310018）

針對(duì)未知稀疏度信號(hào)的重建，提出了一種改進(jìn)的稀疏度自適應(yīng)壓縮采樣匹配追蹤（MACSMP）算法。該算法以壓縮采樣匹配追蹤（CoSaMP）算法為基礎(chǔ)，結(jié)合變步長(zhǎng)自適應(yīng)的思想，擺脫了對(duì)于信號(hào)稀疏度的依賴，并在迭代過(guò)程中引入正則化思想，從而提升了算法的重構(gòu)精度。仿真結(jié)果表明，文中提出的MACSMP算法在重構(gòu)性能與運(yùn)行效率兩方面都要優(yōu)于SAMP、OMP、CoSaMP這幾種算法，且其計(jì)算量較低，運(yùn)行時(shí)間較短。

壓縮感知；重構(gòu)算法；稀疏度自適應(yīng)；正則化

0　引 言

傳統(tǒng)采樣定理中要求采樣頻率需大于信號(hào)帶寬的兩倍，以保證恢復(fù)出來(lái)的信號(hào)不失真，因而我們?cè)谟盟幚韺掝l段類信號(hào)時(shí)就存在很多困難。壓縮感知（Compressed Sensing，CS）[1]理論的提出成功解決了這一難題，其能夠以遠(yuǎn)低于Nyquist率的采樣頻率對(duì)信號(hào)采樣，且可以使用相關(guān)重構(gòu)算法來(lái)恢復(fù)信號(hào)。

重構(gòu)算法是壓縮感知領(lǐng)域一個(gè)重要的研究方向，為此相關(guān)學(xué)者在這一方面做了很多功課，先后提出了許多性能比較優(yōu)異的算法。在這些算法中，貪婪算法由于自身結(jié)構(gòu)較為簡(jiǎn)單且運(yùn)算量相對(duì)較少，故而得到了廣泛應(yīng)用。典型的有正交匹配追蹤算法（Orthogonal Matching Pursuit，OMP）[2]、正則化正交匹配追蹤算法（Regularization Orthogonal Matching Pursuit，ROMP）[3]、壓縮采樣匹配追蹤算法（Compressive Sampling Matching Pursuit，CoSaMP）以及稀疏度自適應(yīng)匹配追蹤算法（Sparsity Adaptive Matching Pursuit，SAMP）[4]。本文在研究上述幾種典型重建算法的基礎(chǔ)上，將CoSaMP算法結(jié)合自適應(yīng)的思想以及正則化的方法并加以改進(jìn)，提出了一種改進(jìn)的自適應(yīng)壓縮采樣匹配追蹤（MACSMP）算法。

1　壓縮感知與重構(gòu)算法

壓縮感知理論表明，若信號(hào)是稀疏的或是可壓縮的，則可用測(cè)量矩陣對(duì)信號(hào)進(jìn)行觀測(cè)，以少量的觀測(cè)值來(lái)表示原信號(hào)，然后利用重建算法恢復(fù)原信號(hào)。

假設(shè)離散信號(hào)x(x∈RN)是N×1維列矢量，在經(jīng)過(guò)一組N×1維向量基等效表示后，其中非零值系數(shù)只有K( K?N)個(gè)，或者是大系數(shù)只有K個(gè)且其他系數(shù)均較小。那么，我們就可以將其在該變換域內(nèi)看作是稀疏的，用數(shù)學(xué)公式可表示為：

式中，α=[α1,…,αN]T是稀疏矢量，ψ=[ψ1,…,ψN]是稀疏字典，K是稀疏度。

信號(hào)在經(jīng)過(guò)上述變換后，我們可以設(shè)計(jì)出一個(gè)M×N(M<

式中Θ=Φ·ψ是一個(gè)M×N的矩陣，也被稱為恢復(fù)矩陣或重構(gòu)字典。

由于測(cè)量向量y的長(zhǎng)度相比原信號(hào)x的長(zhǎng)度要小好多，因此式（2）是一個(gè)欠定方程組，通常解不唯一，故無(wú)法直接通過(guò)求逆運(yùn)算恢復(fù)出信號(hào)。此時(shí)，可以利用求最小l0范數(shù)的辦法來(lái)解決上述問(wèn)題，即：

這樣就可以將它轉(zhuǎn)換成一個(gè)凸優(yōu)化問(wèn)題，從而可以使用凸松弛算法來(lái)解決這個(gè)問(wèn)題。其中，最為典型的是基追蹤（BP）算法[6]。該類算法在信號(hào)重建過(guò)程中往往需要尋求全局最優(yōu)解，因而信號(hào)重建效果比較好，但相應(yīng)所需的計(jì)算量也比較大，實(shí)時(shí)性較差。

常用的還有基于l0范數(shù)模型的貪婪算法，其由于結(jié)構(gòu)更為簡(jiǎn)單、速度更快，因而在壓縮感知中應(yīng)用的領(lǐng)域也更加廣泛，其中最典型是正交匹配追蹤（OMP）算法。此外，還包括引入了正則化的ROMP算法、分段運(yùn)算的StOMP算法、具有回溯功能的CoSaMP算法以及具有自適應(yīng)功能的SAMP算法等。

2　MACSMP算法

傳統(tǒng)CoSaMP重構(gòu)算法具有回溯的思想，在每次迭代前需計(jì)算出殘差r，再根據(jù)式（5）計(jì)算出殘差r和測(cè)量矩陣?yán)飳?duì)應(yīng)原子的相關(guān)系數(shù)u：

將u中前2K個(gè)最大值對(duì)應(yīng)的索引集S合并到支撐集F里，并依據(jù)F中的這些索引值取出測(cè)量矩陣中相應(yīng)的原子構(gòu)成ΦF，再使用最小二乘法重建信號(hào)，并只保留F中與信號(hào)最為匹配的K個(gè)原子的索引，其他元素置零，同時(shí)再次更新下ΦF重建信號(hào)更新殘差rnew：

CoSaMP算法在預(yù)選階段選出的原子數(shù)是2K個(gè)，這一點(diǎn)與其他算法不同。因而，在每次迭代中對(duì)信號(hào)進(jìn)行最小二乘估計(jì)時(shí)，所需的計(jì)算量也相對(duì)較大。為此，可以引入正則化的思想對(duì)原子進(jìn)行二次篩選，這樣既可以減少算法運(yùn)算量，同時(shí)還可以進(jìn)一步提升算法的精確度。

SAMP算法在使用時(shí)無(wú)需知曉原始信號(hào)的稀疏度，而是利用階段的累加來(lái)不斷擴(kuò)大支撐集大小，使之最終能夠達(dá)到信號(hào)實(shí)際稀疏度K，這也是其自適應(yīng)思想的精華所在。但SAMP算法也受固定步長(zhǎng)的限制，因?yàn)椴介L(zhǎng)取值過(guò)大會(huì)影響算法的重構(gòu)精度，故通常也只是取一個(gè)較小的值，這就使得該算法需要多次進(jìn)行原子匹配以及信號(hào)估計(jì)，導(dǎo)致算法重建效率較低。

為此，在利用自適應(yīng)思想解決CoSaMP算法須知曉原始信號(hào)稀疏度這一缺陷時(shí)，我們還應(yīng)考慮SAMP算法本身所存在的不足。這里，可以采用稀疏度預(yù)估計(jì)的辦法以及變步長(zhǎng)的思想來(lái)對(duì)其進(jìn)行改進(jìn)，以有效提升算法效率和算法精度。下面給出使用的稀疏度預(yù)估計(jì)方法。

文獻(xiàn)[7]證明了，在Φ以參數(shù)(K,δK)滿足RIP性質(zhì)前提下。若有K0≥K，則其中K是信號(hào)真實(shí)稀疏度，K0是稀疏度預(yù)估計(jì)值，F(xiàn)0為Φ中與殘差最匹配的K0個(gè)原子對(duì)應(yīng)的索引集。那么，其逆否命題也是真命題。

基于上述理論分析，本文提出了MACSMP算法。該算法首先通過(guò)稀疏度預(yù)估計(jì)的方法獲得一個(gè)粗略值K0，然后在此基礎(chǔ)上使用變步長(zhǎng)自適應(yīng)方式向原始信號(hào)真實(shí)稀疏度逼近，從而克服了CoSaMP以及SAMP算法中存在的不足。此外，MACSMP算法還增加了正則化方式來(lái)進(jìn)一步篩選原子，保證了其能夠更加精準(zhǔn)地重構(gòu)原始信號(hào)。下面我們給出MACSMP算法的步驟。

輸入：測(cè)量向量y，測(cè)量矩陣Φ，初始階段步長(zhǎng)step≠0

步驟1：初始稀疏度K0=1，支撐集F=?；

步驟2：利用式（5）計(jì)算相關(guān)系數(shù)u，并將K0個(gè)最大值對(duì)應(yīng)的索引存入支撐集F中；

步驟5：初始化：階段stage=1，迭代次數(shù)n=1，支撐集大小size=K0，索引集S＝?；

步驟6：利用式（5）計(jì)算相關(guān)系數(shù)u，并選出2size個(gè)最大值對(duì)其進(jìn)行正則化處理，然后將對(duì)應(yīng)索引存入S中；

步驟7：將S合并到支撐集F中，利用式（6）重建信號(hào)x?，并保留F中與x?最匹配的size個(gè)元素，其他元素置零，并更新ΦF；

步驟8：再次重建信號(hào)x?，同時(shí)根據(jù)式（7）得到新的殘差rnew；

步驟10：若滿足擴(kuò)大支撐集長(zhǎng)度條件||rnew||2≥||r||2，則轉(zhuǎn)步驟11；否則r=rnew，迭代次數(shù)n=n+1，并轉(zhuǎn)步驟6；

輸出：信號(hào)x的稀疏估計(jì)x?

其中，步驟1到步驟3完成稀疏度預(yù)估計(jì)的功能，步驟6到步驟8主要實(shí)現(xiàn)對(duì)原子進(jìn)行正則化篩選以及回溯思想處理，而步驟9到步驟11則是通過(guò)兩個(gè)閾值ε1、ε2來(lái)分別控制迭代停止與迭代步長(zhǎng)是否減半[8]。MACSMP算法中，逼近信號(hào)稀疏度部分的運(yùn)算量相對(duì)較小，主要計(jì)算量集中在利用最小二乘法來(lái)估計(jì)信號(hào)這一塊，但由于采用稀疏度預(yù)估計(jì)的方法得到了一個(gè)稀疏度粗略值，這樣也就間接減少了算法前期迭代中對(duì)信號(hào)估計(jì)的次數(shù)，故而能有效降低算法的運(yùn)算量。

3　仿真結(jié)果

為了檢驗(yàn)MACSMP算法性能，文中對(duì)其做了相關(guān)仿真。在本文實(shí)驗(yàn)中，原始信號(hào)采用長(zhǎng)度為N=256的一維正余弦稀疏信號(hào)，階段步長(zhǎng)的值為step=4，稀疏度預(yù)估計(jì)時(shí)參數(shù)δK=0.3。此外，稀疏字典ψ和測(cè)量矩陣Φ分別采用壓縮感知中比較常見(jiàn)的傅里葉變換矩陣和高斯隨機(jī)矩陣。

圖1為M=64時(shí)MACSMP算法的重構(gòu)效果仿真。圖中分別給出了原始信號(hào)、重構(gòu)信號(hào)以及這兩者間的誤差，可以發(fā)現(xiàn)其能夠完整地把信號(hào)恢復(fù)，并且誤差較小。

圖1　MACSMP算法的信號(hào)重構(gòu)

為了更進(jìn)一步說(shuō)明所提算法的準(zhǔn)確性與有效性，下面將其與典型的OMP、ROMP、CoSaMP、SAMP這幾種算法作性能對(duì)比分析。在M取不同值的情況下，分別用這幾種算法對(duì)同一信號(hào)進(jìn)行重構(gòu)，所有算法均運(yùn)行400次，然后計(jì)算其對(duì)信號(hào)的重建概率及其平均運(yùn)行時(shí)間。

圖2是不同M值下MACSMP與上述幾種算法對(duì)于同一信號(hào)的重建結(jié)果。可以發(fā)現(xiàn)，所有算法對(duì)于原始信號(hào)的重建概率均隨著M值的增大而提高，并且當(dāng)采樣點(diǎn)數(shù)M大于一定數(shù)量時(shí)，所有算法都可以把原始信號(hào)完全恢復(fù)出來(lái)。但在同一采樣點(diǎn)數(shù)下，本文所提出的MACSMP算法對(duì)于信號(hào)重構(gòu)的概率最高，相比而言，其重構(gòu)性能要優(yōu)于其他幾種算法。

圖2　不同M值下的重建概率

圖3所示為MACSMP與OMP、CoSaMP以及SAMP算法用于重建同一信號(hào)時(shí)的均方誤差對(duì)比。從中可以發(fā)現(xiàn)，隨著M值的增大，MACSMP算法的均方誤差最先趨于零，其次是SAMP算法，然后才是OMP和CoSaMP這兩種算法。這直接說(shuō)明了MACSMP算法僅需更少的采樣點(diǎn)就能穩(wěn)定把信號(hào)恢復(fù)出來(lái)。而圖4則是他們各自運(yùn)行400次的平均運(yùn)行時(shí)間。由圖4可知，圖中MACSMP算法的運(yùn)行時(shí)間要比其他三種短，說(shuō)明其重構(gòu)效率更優(yōu)。

圖3　不同M值下的重建均方誤差

圖4　各算法仿真所需時(shí)間

4　結(jié) 語(yǔ)

本文提出了一種改進(jìn)的稀疏度自適應(yīng)壓縮采樣匹配追蹤（MACSMP）算法。該算法首先通過(guò)稀疏度預(yù)估計(jì)的方法得到一個(gè)初始值，然后在此基礎(chǔ)上使用變步長(zhǎng)自適應(yīng)的方式向信號(hào)真實(shí)稀疏度逼近，克服了CoSaMP以及SAMP算法中存在的不足。除此之外，MACSMP算法還增加了正則化方式來(lái)進(jìn)一步篩選原子，保證了其能夠更加精準(zhǔn)地重構(gòu)原始信號(hào)。仿真結(jié)果顯示，在同等條件下，本文所提MACSMP算法要比OMP、CoSaMP、SAMP算法用于重建信號(hào)時(shí)效果更佳，并且其計(jì)算量較低，運(yùn)行時(shí)間較短。

[1] Donoho D.Compressed Sensing[J].IEEE Trans on Information Theory,2006,52(04):1289-1306.

[2] Tropp J A,Gilbert A C.Signal Recovery from Random Measurements via Orthogonal Matching Pursuit[J].IEEE Trans on Information Theory,2007,53(12):4655-4666．

[3] Needell D,Vershynin R.Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit[J].Foundations of Computational Mathematics,2009,9(03):317-334．

[4] Do T T,Lu Gan,Nguyen N,et al.Sparsity Adaptive Matching Pursuit Algorithm for Practical Compressed Sensing[C].California:Asilomar Conference on Signals,Systems and Computers，2008:581-587.

[5] Candes E J,Romberg J K,Tao T.Stable Signal Recovery from Incomplete and Inaccurate Measurements[J].Communications on Pure and Applied Mathemati cs,2006,59(08):1207-1223.

[6] Chen S,Donoho D,Saunders M.Atomic Decomposition by Basis Pursuit[J].SIAM Journal on Scientific Computing,1998,20(01):33-61.

[7] 楊成,馮巍,馮輝等.一種壓縮采樣中的稀疏度自適應(yīng)子空間追蹤算法[J].電子學(xué)報(bào),2010,8(01):1914-1917. YANG Cheng,FENG Wei,FENG Hui,et al.An Adaptive Subspace Tracking Algorithm for Sparse Degree in Compressed Sampling[J].Journal of Electroni cs,2010,8(01):1914-1917.

[8] 朱延萬(wàn),趙擁軍,孫兵.一種改進(jìn)的稀疏度自適應(yīng)匹配追蹤算法[J].信號(hào)處理,2012,28(01):80-86. ZHU Yan-wan,ZHAO Yong-jun,SUN Bing.A Modified Sparsity Adaptive Matching Pursuit Algorithm[J].Signal Processing,2012,28(01):80-86.

倪加明（1992—），男，碩士研究生，主要研究方向?yàn)樾盘?hào)處理；

孫欽者（1992—），男，碩士研究生，主要研究方向?yàn)檐浖o(wú)線電；

陸家明（1990—），男，碩士研究生，主要研究方向?yàn)闊o(wú)線通信技術(shù)。

A Modified Adaptive Compressive Sampling Matching Pursuit Algorithm

NI Jia-ming, SUN Qin-zhe, LU Jia-ming
（College of Communication Engineering, Hangzhou Dianzi University, Hangzhou Zhejiang 310018, China）

For the reconstruction of signals with unknown sparsity , a modified sparsity adaptive compressive sampling matching pursuit (MACSMP) algorithm is proposed. Based on the compressive sampling matching pursuit (CoSaMP) algorithm, the proposed algorithm adds the thought of regularizaton to iterative process,thus to improve the accuracy of the algorithm, and in combination with variable step adaptive idea, to solve the dependence on signal sparsity. Simulation results indicate that the proposed MACSMP algorithm is better than SAMP algorithm, OMP algorithm, CoSaMP algorithm in the reconstruction performance and operation efficiency, and in addition the calculation is lower and the running time shorter.

compressed sensing; reconstruction algorithm; sparsity adaptation; regularization

TN911.7

A

1002-0802(2016)-08-0992-05

10.3969/j.issn.1002-0802.2016.08.007

2016-04-18;

2016-07-25

date:2016-04-18;Revised date:2016-07-25