一種改進的稀疏度自適應壓縮采樣匹配追蹤算法*

倪加明，孫欽者，陸家明

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

一種改進的稀疏度自適應壓縮采樣匹配追蹤算法*

倪加明，孫欽者，陸家明

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

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

壓縮感知；重構算法；稀疏度自適應；正則化

0　引 言

傳統(tǒng)采樣定理中要求采樣頻率需大于信號帶寬的兩倍，以保證恢復出來的信號不失真，因而我們在用它處理寬頻段類信號時就存在很多困難。壓縮感知（Compressed Sensing，CS）[1]理論的提出成功解決了這一難題，其能夠以遠低于Nyquist率的采樣頻率對信號采樣，且可以使用相關重構算法來恢復信號。

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

1　壓縮感知與重構算法

壓縮感知理論表明，若信號是稀疏的或是可壓縮的，則可用測量矩陣對信號進行觀測，以少量的觀測值來表示原信號，然后利用重建算法恢復原信號。

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

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

信號在經(jīng)過上述變換后，我們可以設計出一個M×N(M<

式中Θ=Φ·ψ是一個M×N的矩陣，也被稱為恢復矩陣或重構字典。

由于測量向量y的長度相比原信號x的長度要小好多，因此式（2）是一個欠定方程組，通常解不唯一，故無法直接通過求逆運算恢復出信號。此時，可以利用求最小l0范數(shù)的辦法來解決上述問題，即：

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

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

2　MACSMP算法

傳統(tǒng)CoSaMP重構算法具有回溯的思想，在每次迭代前需計算出殘差r，再根據(jù)式（5）計算出殘差r和測量矩陣里對應原子的相關系數(shù)u：

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

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

SAMP算法在使用時無需知曉原始信號的稀疏度，而是利用階段的累加來不斷擴大支撐集大小，使之最終能夠達到信號實際稀疏度K，這也是其自適應思想的精華所在。但SAMP算法也受固定步長的限制，因為步長取值過大會影響算法的重構精度，故通常也只是取一個較小的值，這就使得該算法需要多次進行原子匹配以及信號估計，導致算法重建效率較低。

為此，在利用自適應思想解決CoSaMP算法須知曉原始信號稀疏度這一缺陷時，我們還應考慮SAMP算法本身所存在的不足。這里，可以采用稀疏度預估計的辦法以及變步長的思想來對其進行改進，以有效提升算法效率和算法精度。下面給出使用的稀疏度預估計方法。

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

基于上述理論分析，本文提出了MACSMP算法。該算法首先通過稀疏度預估計的方法獲得一個粗略值K0，然后在此基礎上使用變步長自適應方式向原始信號真實稀疏度逼近，從而克服了CoSaMP以及SAMP算法中存在的不足。此外，MACSMP算法還增加了正則化方式來進一步篩選原子，保證了其能夠更加精準地重構原始信號。下面我們給出MACSMP算法的步驟。

輸入：測量向量y，測量矩陣Φ，初始階段步長step≠0

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

步驟2：利用式（5）計算相關系數(shù)u，并將K0個最大值對應的索引存入支撐集F中；

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

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

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

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

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

輸出：信號x的稀疏估計x?

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

3　仿真結果

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

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

圖1　MACSMP算法的信號重構

為了更進一步說明所提算法的準確性與有效性，下面將其與典型的OMP、ROMP、CoSaMP、SAMP這幾種算法作性能對比分析。在M取不同值的情況下，分別用這幾種算法對同一信號進行重構，所有算法均運行400次，然后計算其對信號的重建概率及其平均運行時間。

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

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

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

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

圖4　各算法仿真所需時間

4　結 語

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

[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] 楊成,馮巍,馮輝等.一種壓縮采樣中的稀疏度自適應子空間追蹤算法[J].電子學報,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] 朱延萬,趙擁軍,孫兵.一種改進的稀疏度自適應匹配追蹤算法[J].信號處理,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—），男，碩士研究生，主要研究方向為信號處理；

孫欽者（1992—），男，碩士研究生，主要研究方向為軟件無線電；

陸家明（1990—），男，碩士研究生，主要研究方向為無線通信技術。

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