压缩感知中贪婪重构算法研究

冯俊杰　季立贵

摘要：压缩感知理论是利用信号的稀疏性，通过少量的观测值就可以实现对该信号的精确重构。贪婪类算法是压缩感知重构步骤中广泛应用的一类算法。该文主要对该类算法中典型的三种算法在存在噪声环境中进行了综合分析比较。首先从理论方面分析了三种算法，给出了实现过程；然后在不同稀疏度情况下，对三种贪婪算法重构性能进行综合比较。根据理论分析结果和仿真结果，得出相应的结论。

关键词：压缩感知；稀疏度；贪婪算法；信号重构

中图分类号：TN911.72 文献标识码：A 文章编号：1009-3044（2014）31-7351-03

Abstract：Compressive sensing is a novel signal sampling theory under the condition that the signals are sparse.In this case，the small amount of signal values can be reconstructed accurately. Greedy algorithm is one class of the algorithms used most widely in CS signal reconstruction.In this paper， the three classic greedy algorithms are analyzed and compared theoretically in noise condition with different sparsity level，by the analysis and simulation result，the conclusion is obtained.

Key words：compressive sensing； sparsity； greedy algorithm； signal reconstruction

与奈奎斯特采样定理不同，压缩感知理论（Compressive sensing，CS）[1-3]利用信号的稀疏性，将采样与压缩同时进行，通过求解一个优化问题就可从少量的测量值中以高概率重构出原信号。CS理论改变了传统的采样方式，极大的降低了采样率，降低了数据获取、传输及处理的压力，在图像信号处理[4-5]、语音信号处理[6-7]等方面得到广泛的应用。压缩感知主要包括三个方面即：信号的稀疏表示，线性测量，重构算法。其中稀疏信号重构算法是该理论的至关重要的环节，贪婪迭代算法具有计算复杂度较低等优点，应用范围相对较广。该类算法的基本思想是在每次迭代时通过局部最优化，寻找各非零系数的位置，选择一个局部最优解来逐步逼近原始信号。贪婪迭代算法主要包括正交匹配追踪算法（OMP）[[8]]、正则正交匹配追踪算法（ROMP）[[9]]、稀疏度自适应匹配追踪法算法（SAMP）[[10]]等。该文将主要研究和分析上述三类贪婪迭代算法在存在噪声情况下的重构特性， 通过仿真实验比较各个算法的性能特点。

由图1、图2、图3可以看出，ROMP算法耗时最短。随着信号稀疏度的增加，信号重构的概率逐渐减小，均方误差逐渐增多，当稀疏度低于20时，三种算法都可100%的重构原信号，随着稀疏度的增加，ROMP算法和OMP算法重构性能快速下降，当稀疏度为40时，SAMP算法仍以较高概率重构出原始信号。SAMP算法由于迭代次数增加导致运算量大，其重构时间也较长。

4 总结

本文基于压缩感知基本原理，分析了在噪声环境中三种常见的贪婪迭代稀疏信号重构算法的性能。比较了随着稀疏度的改变，三种重构算法重构时间、重构概率和均方误差的变化情况。仿真实验结果表明，在相同实验条件下，ROMP的运行时间最短，SAMP的重构性能优于ROMP和OMP算法，在实际应用中，可以综合考虑三种算法的重构性能进行选择。

参考文献：

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

[2] Goyal V K，Fletcher A K，Rangan S.Compressive Sampling and Lossy Compression[J].IEEE Signal Processing Magazine，2008， 25（2）： 48-56.

[3] 杨海蓉，张成，丁大为，等.压缩传感理论与重构算法[J].电子学报， 2011， 39（1）： 142-148.

[4] 解成俊，张铁山.基于压缩感知理论的图像重构算法研究[J].计算机应用与软件，2012，29（4）：49-52.

[5] 方红，章权兵，韦穗.基于亚高斯随机投影的图像重建方法[J].计算机研究与发展，2008，45（ 8） ： 1402-1407.

[6] 郭海燕，杨震.基于近似KLT域的语音信号压缩感知[J].电子与信息学报，2009，31（12） ： 2948-2952.

[7] 梁瑞宇，邹采荣，赵力，等.语音压缩感知及其重构算法[J].东南大学学报：自然科学版，2011，41（1）：1-5.

[8] Tropp J， Gilber t A.Signal recovery from random measurements via orthogonal matching pursuit[J].Transactions on Information Theory， 2007， 53（12）：4655-4666.

[9] Needell D，Vershynin R.Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of Computational Mathematics， 2009，9（3） ：317-334.

[10] Thong T D，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing [C].Asilomar Conference on Signals，Systems，and Computers，Pacific Grove，California，2008，10： 581-587.