稀疏度自适应分段正交匹配追踪算法改进

李雪晴 丁佳静 武雪姣

摘  要：在基于压缩感知的信号重构问题中，有一类常见情况——未知信号稀疏度。针对此类情况，提出稀疏度自适应分段正交匹配追踪（Sparsity Adaptive Stagewise Orthogonal Matching Pursuit，SAStOMP）算法，该算法将自适应思想、变步长迭代思想与分段正交思想相结合，在未知信号稀疏度的情况下，自适应地选择支撑集原子的个数，最终实现信号的精确重构。仿真结果表明，针对长度为256位的原始信号，该算法重建效果优于正交匹配追踪算法、正则化正交匹配追踪算法和分段正交匹配追踪算法等。

关键词：压缩感知;信号重建算法;稀疏度自适应;分段正交匹配追踪

中图分类号：TP391     文献标识码：A

Abstract：Aiming at the reconstruction of unknown signal sparsity in compressed sensing，this paper proposes a new compression sensing signal reconstruction algorithm of SAStOMP （Sparsity Adaptive Stagewise Orthogonal Matching Pursuit）.The algorithm combines the ideas of self-adaptation，variable step size iteration and piecewise orthogonal design，in the case of unknown signal sparsity，selects adaptively the number of atoms of the support set ，finally realizes the accurate reconstruction of signals.Simulation results show that the proposed algorithm is superior to OMP，ROMP and StOMP for the original signals of 256 digits.

Keywords：compressed sensing;signal reconstruction algorithm;sparsity adaptive;stagewise orthogonal matching pursuit

1   引言（Introduction）

压缩感知（Compressed Sensing，CS）技术之所以能够利用较低维度的观测值去重构较高维度的信号，在于充分利用了信号的稀疏性和可压缩性[1]。研究CS理论，主要侧重于三方面：信号的稀疏表示、观测矩阵的设计，以及信号的重建算法。其中，信号重建算法是决定信號是否可以准确重构的关键步骤，其目的在于利用观测值去高精度地重构真实值，当然观测值的维度远远小于真实值。信号重构算法主要包括以下三类：组合优化类、凸优化类和贪婪迭代类[2]。贪婪迭代类算法往往运行速度较快，算法流程清晰。现有的贪婪迭代算法有匹配追踪（Matching Pursuit，MP）[3]、正交匹配追踪（Orthogonal Matching Pursuit，OMP）[4]、分段正交匹配追踪（Stagewise Orthogonal Matching Pursuit，StOMP）[5]、正则化正交匹配追踪（Regularized Orthogonal Matching Pursuit，ROMP）[6]、压缩采样匹配追踪（Compressive Sampling Matching Pursuit，CoSaMP）[7]和子空间追踪（Subspace Pursuit，SP）[8]。但是，贪婪迭代算法对待重构信号都有一个要求——稀疏度确定且已知，但事实上，真正的实际应用中，稀疏度通常不是先验知识[9]。针对以上问题，本文在StOMP框架下，结合SAMP中稀疏度自适应的特点[10]，提出稀疏度自适应分段正交匹配追踪算法（SAStOMP），该算法主要用于稀疏度未知情况下的信号重构。

2   压缩感知理论（Compressed sensing）

在对信号进行重建时，能否运用压缩感知理论在于确定该信号是否具有稀疏性，我们知道，每个一维信号，都可以用N×1维基向量线性表示。为了简化问题，假设基向量为规范正交向量，使用N×N的基矩阵，信号x可以被表示为：

在该式中：S是投影系数构成的N×1维列向量。X是在时域或空间域的表示，Ψ为N×N维变换基，S是在Ψ域的表示。当信号可以仅被K个基向量线性表示时，则称信号x为K-稀疏。作为压缩感知理论的前提，稀疏性是实际很多信号不具有的，不能运用压缩感知理论进行压缩采样，这会限制压缩感知的发展。为了让信号都具有这一性质，先对信号进行某种变换，使其具有稀疏性，之后就可对信号进行采样压缩和信号重构。设计一个与变换基不相关的观测矩阵Φ，注意该矩阵的维度为M×N（M

上式中的Θ是恢复矩阵，维度为M×N。观测矩阵Φ为已知矩阵，本文中分别取高斯随机矩阵、伯努利矩阵、部分傅里叶矩阵为参考进行实验分析。

3 稀疏度自适应分段正交匹配追踪算法（Algorithm for sparsity adaptive stagewise orthogonal matching pursuit）

正交匹配追踪算法是压缩感知理论中较为经典的算法，算法简单，重构效果尚可，但是这种算法每次只从观测矩阵中选取1个最佳原子，即选取残差最小的原子加入集合，这种算法重构准确度的增加是以牺牲迭代次数为代价的，当信号量激增时，整个重构的效率显然会大大降低。接下来介绍StOMP算法，与OMP算法不同，StOMP算法在每次迭代中会选出多个原子，选取原子的个数是由提前设定的阈值决定的，之后在每次迭代中更新原子集合，最终找到最优解。显然，StOMP算法的重构效率要比OMP算法高得多，下面介绍StOMP算法的流程与步骤[11]：

（1）初始残差，计数器s=1。

（2）计算内积 。?

（3）可以通过设定软阈值来产生相应集合，其中：为噪声水平，为;θ为阈值参数，取值范围为[2，3]。

（4）更新支撑集：，并利用最小二乘法计算支撑集上的逼近系数向量，。

（5）更新残差（余量）。

（6）检查终止条件：若s>10或者，（其中为误差容限），算法终止并将作为最终输出。否则，执行并转到步骤（2） 。

StOMP算法每次迭代选取多个原子，大大提高了重构的效率，但该算法也存在以下不足之处：

（1）因为StOMP算法在每次迭代过程中，选择的是根据阈值划分出的原子集合，而不是最优原子，所以与OMP算法相比较，准确度大大降低。

（2）在上文中已经提到，选取原子的个数是由提前设定的阈值决定的，在实际应用中，阈值往往不太容易确定。

（3）无论是OMP算法还是StOMP算法，都需要确定待重构信号的稀疏性，但在实际的应用中，不同来源的信号的稀疏度往往是未知的且很难确定。

考虑到OMP算法和StOMP算法的优缺点，本文结合SAMP算法[12]的自适应思想，提出一种改进的稀疏度自适应的压缩感知算法。改进的算法无须明确待重构信号的稀疏度，而是在迭代过程中一步步去逼近真实的稀疏度K，最终实现信号重构。算法流程如下[12，13]：

输入：M×N的传感矩阵A=ΦΨ;N×1维观测向量y;迭代次数S，默认为10;门限参数ts，默认为2.5;步长ST。

输出：信号稀疏表示系数估计;残差。

（1）初始化：，，，，。

（2）计算（即计算，1≤j≤N），选择u中L个最大值，将这些值对应A的列序号j构成集合（列序号集合），选择u中大于门限的值，将这些值对应A的列序号j构成集合（列序号集合）。

（3）令，;若（即无新列被选中），则停止迭代进入第（8）步。

（4）求的最小二乘解：。

（5）从中选出绝对值最大的L项记为，对应的的L列记为，对应的A的列序号记为，记集合。

（6）更新上一步骤所得残差，使得。

（7）如果则停止迭代进入第（8）步;如果，则更新步长L=L+ST，返回第（2）步继续进行迭代;否则，如果t≤S停止迭代进入第（8）步，否则返回第（2）步继续迭代。

（8）重构所得在处有非零项，其值分别为最后一次迭代所得。

综上，SAStOMP算法将分阶段正交化思想，以及自适应思想相结合，在提高重构效率的同时保证了信号重构的准确度。

4 实验结果及分析（Experimental results and analysis）

为了檢验本文算法的正确性和有效性，将本文改进的算法与OMP算法、ROMP算法，以及StOMP算法进行比较。本文涉及的实验在华硕Y481C笔记本（4GB DDR3内存，i7-3573）上，通过MATLAB R2014a仿真完成。当观测矩阵为高斯随机矩阵、伯努利矩阵和部分傅立叶矩阵时，信号准确重建概率分别如图1、图2、图3所示。

从图1可以看出，当信号长度为256位，观测值集合为128位，观测矩阵为高斯矩阵时，改进的SAStOMP算法明显优于OMP算法、ROMP算法、StOMP算法。当稀疏度接近45时，OMP算法和StOMP算法信号准确重构的概率急剧下降，改进的SAStOMP算法仍能100%精确重构信号。当稀疏度接近55时，OMP算法和StOMP算法几乎不能重构信号，而改进的SAStOMP算法性能良好，准确重构信号的概率接近65%。

从图2可以看出，当信号长度为256位，观测值集合为128位，观测矩阵为伯努利矩阵时，改进的SAStOMP算法依然明显优于OMP算法、ROMP算法、StOMP算法。随着稀疏度不断增加，信号精确重构概率基本趋势与观测矩阵为高斯矩阵的情况相同。

从图3可以看出，当信号长度为256位，观测值集合为128位，观测矩阵为傅立叶矩阵时，改进的SAStOMP算法仅次于经典的OMP算法，明显优于ROMP算法和StOMP算法。

经过仿真实验和上述实验结果分析，综合来说，本文提出的算法不需要信号稀疏度作为先验知识，表现出的性能整体优于经典的OMP算法、ROMP算法和StOMP算法，具有良好的实用价值。

5   结论（Conclusion）

本文提出了SAStOMP算法，该算法不需要稀疏度K作为先验知识，弥补了贪婪迭代类算法的最大不足。MATLAB实验仿真结果表明，改进的SAStOMP算法优于OMP、ROMP和StOMP算法，提高了信号稀疏度较大时重构信号的准确度。

参考文献（References）

[1] Zhou C，Gu Y，Zhang Y D，et al.Compressive sensing-based coprime array direction-of-arrival estimation[J].Iet Communications，2017，11（11）：1719-1724.

[2] 唐朝伟，王雪锋，杜永光.一种稀疏度自适应分段正交匹配追踪算法[J].中南大学学报（自然科学版），2016，47（3）：784-792.

[3] Chen C H，Tsai C R，Liu Y H，et al.Compressive Sensing （CS） Assisted Low-Complexity Beamspace Hybrid Precoding for Millimeter-Wave MIMO Systems[J].IEEE Transactions on Signal Processing，2017，65（6）：1412-1424.

[4] Nouasria H，Et-Tolba M.Sensing matrix based on Kasami codes for compressive sensing[J].IET Signal Processing，2018，12（8）：1064-1072.

[5] Donoho D L，Tsaig Y，Drori I，et al.Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit[J].IEEE Transactions on Information Theory，2012，58（2）：1094-1121.

[6] Needell D，Vershynin R.Signal Recovery From Incomplete and Inaccurate Measurements Via Regularized Orthogonal Matching Pursuit[J].IEEE Journal of Selected Topics in Signal Processing，2010，4（2）：310-316.

[7] Needell D，Tropp J A.Tropp，J.A.：CoSaMP：iterative signal recovery from incomplete and inaccurate samples[J].Applied & Computational Harmonic Analysis，2008，26（3）：301-321.

[8] Dai W，Milenkovic O.Subspace Pursuit for Compressive Sensing Signal Reconstruction[J].IEEE Transactions on Information Theory，2009，55（5）：2230-2249.

[9] 吴迪，王奎民，赵玉新，等.分段正则化正交匹配追踪算法[J].光学精密工程，2014，22（5）：1395-1402.

[10] sfs DO T T，GAN L，NGUYEN N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C].Proceedings of the Asilomar Conference on Signals，Systems and Computers.Pacific Grove，CA：IEEE Computer Society，2008：581-587.

[11] onoho D L，Tsaig Y，DroriI，Starck J L.Sparsesolution of underdetermined linear equations by stagewise orthogonal matchingpursuit[J].IEEE Transactions on InformationTheory，2012，58（2）：1094-1121.

[12] Thong T.Do，Lu Gan，NamNguyen，et al.Sparsityadaptive matching pursuit algorithm for practical compressed sensing[C].AsilomarConference on Signals，Systems，andComputers，Pacific Grove，California，2008，10：581-587.

[13] 楊成，冯巍，冯辉，等.一种压缩采样中的稀疏度自适应子空间追踪算法[J].电子学报，2010，38（8）：1914-1917.