基于压缩感知的重构算法研究

庞影影

摘要：由于传统的信号处理技术对信号频率的限制，越来越不能满足日益增长的信号需求，因而一种新的信号处理技术—压缩感知技术被提出。压缩感知技术由于其打破了奈奎斯特采样定理对信号采样频率的限制因而被广泛应用于信号处理方面，而压缩感知技术的关键部分就是重构算法的运用，本文主要介绍基于压缩感知的几种重构算法，并且比较各个算法的优缺点，从而为今后的运用提供有利的指导。

关键词：压缩感知；MP算法；OMP算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2016）23-0153-02

1引言

压缩感知（Compressive Sensing）[1，2]技术是信号处理领域提出的一种新的信号处理技术，由D. Donoho（美国科学院院士）、E. Candes及华裔科学家陶哲轩等人提出。奈奎斯特采样定理在进行A/D信号的转换过程表明：当采样信号的频率大于信号2倍带宽时，经过采样后的数字信号才能保留了原始信号中的完整信息。由于压缩感知表明：如果信号在某一个正交空间是稀疏性的，就可以以较低的频率即远低于2倍带宽的频率来采样该信号，并有很大可能来精确的重构该信号，从而打破了奈奎斯特采样定理，因此在现代信号处理领域展现出突出的优势和广阔的前景。

2压缩感知与恢复算法

2.1 压缩感知理论

压缩感知理论一般分为三部分：

2.1.1信号的稀疏表示

信号的稀疏性可以表示为进行采样和重构的信号本身能是被压缩的，或者在某些稀疏变换基下是稀疏的，实际中大部分信号均具有这种特性，因此信号的稀疏表示就是将信号转变为它们的稀疏形式。比较常见的稀疏转换基有快速傅里叶变换基（FFT）、离散余弦变换基（DCT）、Curvelet基、Gabor基以及冗余字典[3]等。

2.1.2观测矩阵的设计

假定有一稀疏信号X，理论上可以用X的M个线性测量精确重构X，其中，通常情况下方程具有无穷解，因此提出了唯一解的充要条件就是：观测矩阵[4，5]要满足有限等距准则（Restricted Isometry Property， RIP）即等效求解为

[x=arg minx0 s.t. y=Θx] （1）

由于上式是NP问题，计算求解复杂度高，因此提出了恢复算法即重构算法。

2.1.3重构算法的选择

对重构算法的比较主要从算法精确重构的概率，重构算法的运行时间，以及重构信号与原始信号的相对误差这几方面。而一般重构算法可分为三大类：贪婪算法、凸优化算法以及综合算法，其中贪婪算法计算复杂度低，所需采样点少，运算速度快，适用于小规模信号重构，在本文中将着重比较贪婪算法中的几种重构算法。

2.2 贪婪迭代重构算法的比较

2.2.1 MP算法（匹配追踪算法）

MP算法：MP算法是一种贪心算法，就是从每次迭代的测量矩阵中选择一个与信号X最匹配的原子，构建成稀疏逼近，从而求出信号残差，继续选择与求得的信号残差最匹配的原子，经过多次迭代，信号X就可以由这些原子的线性和以及最后的残差值来表示出来。而且如果残差值在较小的范围内可忽略，信号X就可以由这些原子的线性组合来表示，但如果残差值在已选择的原子上进行垂直投影结果是非正交性的，这样就会导致迭代结果不是最优的，算法的迭代次数不是最少的，因而使得收敛需要更多次的迭代，使得算法的重构效率变低，在此基础上我们提出了OMP算法。

2.2.2 OMP算法（正交匹配追踪算法）

OMP算法相比较MP算法优势在于：在分解过程中，每一步都将选择的原子正交化，从而保证选择原子的最优，减少了算法的迭代次数，使得算法的收敛速度更快。

其中MP算法与OMP算法原子的选择并没有变化，都是在每次迭代过程中，找到与残差最相关的一个原子放入原子集合中，但是当测量矩阵为高斯随机矩阵时，对一个信号X，它的信号长度为n，稀疏度为k，OMP算法精确重构原始信号的概率很大，而且运算的时间复杂度很低，由于OMP算法对测量信号满足的要求较高，重构时精度较低，使得对于选择的测量矩阵的要求也比较高。OMP算法的运算步骤如下：

输入：观测向量，观测矩阵，原始信号的稀疏度K

输出：重构信号

1）初始化残差 ，索引集为空集，迭代次数t=1。

2）找出残差r和传感矩阵的列积中最大值所对应的脚标。

3）更新索引矩阵与原子集{}，记录找到的传感矩阵中的 重建原子集合。

4）由最小二乘法得到。

5）更新残差，t=t+1。

6）判断迭代停止条件，若满足，则停止迭代，若不满足，则重复步骤2。

在OMP算法的基础上，又提出了StOMP算法。

2.2.3 StOMP算法（分段正交匹配追踪算法）

StOMP算法是OMP算法的改进算法，它是将迭代过程划分为几个阶段进行。在每次迭代时选择的是一组原子，因此运算速度比OMP快。而且运算时并不需要输入原始信号的稀疏度K，因而相比OMP有独到的优势。

3总结

近年来，随着信息领域的不断发展，对于信号的精密程度的要求也越来越高，然而传统的信号处理技术越来越不能满足人们的需要，因此压缩感知理论应运而生，在本文中主要介绍了压缩感知理论的几种重构算法，为今后实际运用提供借鉴，由于压缩感知现阶段只是理论部分，实际应用并不广泛，因此对于压缩感知的实际应用还有很长的道路探索。

参考文献：

[1] 李树涛，魏丹.压缩感知综述[J].自动化学报，2009.

[2] 陈明生，王时文，马韬，吴先良.基于压缩感知的目标频空电磁散射特性快速分析[J].物理学报，2014.

[3] 张春梅，尹忠科，肖明霞.基于冗余字典的信号超完备表示和稀疏分解[J].科学通报，2006.

[4] 付强，李琼.压缩感知中测量矩阵的研究[J].应用技术与研究，2011.

[5] 李小波.基于压缩感知的测量矩阵研究[D].北京：北京交通大学硕士学论文，2010.