一种稀疏自适应的正交互补匹配追踪算法

郭永红，杨毅彬

一种稀疏自适应的正交互补匹配追踪算法

郭永红，杨毅彬

针对实际应用中信号稀疏度未知的缺点，提出了一种稀疏度自适应的正交互补匹配追踪算法。算法先初始化稀疏度，再通过互补正交匹配追踪重构信号，找到一个支撑集；若支撑集不满足条件，则按指定步长增加稀疏度，再次运用算法进行重构，直到支撑集满足条件，得到最优支撑集。实验结果表明，该算法可以准确有效地重构信号，并且在相同压缩比下，其重构质量（PSNR）优于其他几种算法。

稀疏度；正交互补；指定步长；支撑集

1 引言

Nyquist采样理论在传统的信号理论中起着关键作用，它要求采样频率须为信号带宽的两倍。压缩感知理论（Compressed Sensing，CS）[1-2]表示如果信号在某个变换域上稀疏，则可将信号投影到一个低维空间，然后利用投影值通过求解范数最优化问题，可高概率地精确重建原始信号。CS理论表明恢复信号所需要的采样数据远低于Nyquist定理所定义的采样量，因此该理论一经出现就引起国内外相关领域研究人员的密切关注。设信号x(x∈RN) 为N×1维列向量。若 x中仅有不超过k(k＜＜N)个非零元素，则x称为k-稀疏信号。用一个M×N(M＜＜N)维的测量矩阵对信号进行投影，即 y=Φx，则基于 y可对信号进行重构。

在已知 y和Φ的条件下对信号x进行重构是CS研究的一个重要方面。目前重建算法主要分为两类：一类是基于l1范数最小化的凸优化算法，主要包括基追踪算法（Basis Pursuit，BP）[3]、梯度追踪算法（Gradient Pursuit，GP）[4]、内点迭代法等；另一类是基于l0范数最小化的贪婪算法，主要包括匹配追踪（Matching pursuit，MP）[5]、正交匹配追踪（Orthogonal Matching Pursuit，OMP）[6]、互补匹配追踪（Complementary Matching Pursuit，CMP）[7]、正交互补匹配追踪算法（Orthogonal Complementary Matching Pursuit，OCMP）[8]、正则化正交匹配追踪算法（Regularized Orthogonal Matching Pursuit，ROMP）[9]等。贪婪算法由于结构简单，运算量小等特点得到应用。但这几种算法均要求信号稀疏度已知，这在很多实际应用中很难满足，如果对稀疏度的估计不准确，信号将不能得到精确重建。针对实际信号中稀疏度未知的特点，本文结合文献[10]提出的自适应匹配追踪算法（Sparsity Adaptive Matching Pursuit，SAMP），提出一种稀疏度自适应的迭代算法，采用增加固定原子的方法来估计稀疏度。

2 正交互补匹配追踪算法

文献[7]互补匹配追踪算法（CMP）类似于经典匹配追踪算法（MP），与其不同的是CMP算法是直接在原信号x的行空间上求解。每次迭代时，MP算法是从字典矩阵中选择一个最匹配的原子；CMP则是剔除(N-1)不匹配的原子并保留剩下的一个最匹配的原子，这种方法使其具有比MP算法更好的重建效果。

文献[8]提出的正交互补匹配追踪算法（OCMP）是CMP的改进算法。OCMP算法在选择原子上与CMP一样，稀疏估计时采用最小二乘法对信号进行估计，算法步骤如下：

（1）初始化残差r0=b，感知矩阵Φ=A+A，测量向量x2=A+b，对角矩阵Δ，其对角元素为：

其中A+=AT(AAT)-1为A的伪逆。

（2）计算相关性h，并寻找h中绝对值最大的元素：

（3）信号稀疏估计并更新残差：

其中，I表示h中元素最大值的索引值构成的集合；当残差r满足停止条件时，迭代停止。

从上文可以看出，算法主要分为三个部分：计算相关性；更新索引集；更新残差。算法在每次迭代时只找到信号的一个元素，对于稀疏度为k的信号，至少需要进行k次迭代才能恢复出原信号。如果稀疏度的估计不够准确，那么估计信号的误差将会很大。

3 改进算法

在实际生活中信号稀疏度往往未知，针对于此，本文提出了一种自适应迭代算法——稀疏自适应正交互补匹配追踪算法（Sparsity Adaptive Orthogonal Complementary Matching Pursuit，SAOCMP）。主要思想是先初始化稀疏度，其值随指定步长进行增加，然后对算法进行迭代，每次迭代都会找到信号的一个支撑集，再利用回溯思想更新上一次找到的支撑集，直至找到最终支撑集，从而达到重构信号的目的。本文算法框图如图1。

图1 算法框图

根据框图，下面对算法的步骤进行具体阐述。

3.1 算法步骤

（1）算法输入：字典矩阵A，测量向量s。初始化残差值r0=s，迭代误差δ，重构向量re_x，感知矩阵Φ=A+A，测量向量x2=A+s，对角矩阵Δ，其对角元素为：

步长step=1，信号支撑集Fk=[]。

（2）初始测试：计算第k次迭代的相关性，并找出前step个最大值S：

（3）候选支撑集C：

（4）最终测试：估计信号并求出前step个最大的元素Fk：

其中，ΦC为候选支撑集C对应的感知矩阵Φ的列向量组成的矩阵。

（5）计算残差rk：

（6）若norm(rk)≥norm(rk-1)，则i=i+1；step=i×stage，返回步骤（2），否则直接返回步骤（2）。其中stage为固定步长。

（7）当估计信号与原始信号的差值小于迭代误差δ时，则迭代停止。输出重构向量re_x，满足：

3.2 信号重建实验

本实验对CMP、OCMP、SAOCMP、CMP-OMP算法进行一维仿真，比较各个算法的相对误差和运行时间。实验测试当M=128，稀疏度k和采样点数M取不同值时算法运行的结果。SAOCMP中初始步长step=1，终止条件为估计信号与原始信号残差能量小于δ=e-12；算法在Pentium Dual-core E5400机器上运行，软件版本为Matlab R2008a。对于不同的值，算法运行100次来计算平均重构误差和平均运行时间。

图2表示不同采样点下信号准确重构率。从图中可以看出本文算法在收敛速度是最快的，即在相同的准确重构率下，SAOCMP算法所需的采样点数是最小的。对于重建误差，当各个算法取相同采样点时，SAOCMP算法与CMP、OCMP、CMP-OMP算法相比，其误差是最小的，如表1所示。

图2 准确重建率对比分析

表1 不同采样点数下重建误差比较

图3是在稀疏度相同、采样点数不同的情况下重建信号的平均运行时间。从图中可以看出，当M大于30时，SAOCMP算法的运行时间要小于OCMP。从重建误差角度来分析，当各个算法取相同稀疏度时，与OCMP、CMP、CMP-OMP算法相比，SAOCMP算法具有重建误差最小的优点，如表2所示。

图3 运行时间对比分析

表2 不同稀疏度下重建误差比较

4 图像实验

实验采用256×256像素的Lena图像，采样矩阵为随机采样矩阵，SAOCMP算法中步长stage=2。实验比较了各个算法重建的运算时间、均方误差MSE和峰值信噪比PSNR。图4给出了压缩比M/N=0.5时CMP、OCMP、SAOCMP、CMP-OMP算法的重建效果。由图可见在压缩比相同的情况下，SAOCMP算法的图像重建效果要比其他算法更好。表3给出了不同算法重建图像的运算时间、均方误差MSE和峰值信噪比PSNR。从表中可以看出，当各算法具有相同压缩比时，SAOCMP的PSNR最大，MSE最小。从运行时间角度分析，该算法牺牲了时间而获得了更低的重构误差，因此如何在保持低误差的情况下减少运行时间是今后研究的方向。

表3 各算法重建时间与性能比较

图4 各算法重建图像对比（M/N=0.5）

5 结论

本文提出了一种新的压缩感知信号重构算法——稀疏自适应正交互补匹配追踪算法。通过初始化稀疏度，并且在每次迭代后随指定步长增加，利用回溯思想不断估计和更新支撑集，直至满足迭代停止条件为止。

实验结果表明，本文算法可以在稀疏度未知的先验条件下重建信号，并且能够保证重建的准确率，同时减少了运行时间。经实验证明，本文算法的重建质量无论是一维信号还是二维图像上都优于现有同类算法，是一种重建效果较好的方法。

[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

电子科技大学 电子科学技术研究院，成都 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—），男，硕士研究生，主要研究方向为电子与通信工程；杨毅彬（1982—），男，助理研究员，主要研究方向为电磁场理论及其应用。E-mail：guoyonghong52400@163.com

2011-08-22

2011-10-17

1002-8331（2013）07-0144-03