压缩感知重构匹配类算法分析

端木春江 肖艳丽

摘要： 压缩感知理论是一种利用信号的稀疏性或可压缩性而把采样与压缩融为一体的新理论体系，它成功地克服了传统理论中采样数据量大、资源浪费严重等问题。该理论的研究方向主要包括信号的稀疏表示、测量矩阵的设计和信号的重构算法。其中信号的重构算法是该理论中的关键部分，也是近年来研究的热点。本文主要对匹配追踪类重构算法作了详细介绍，并通过仿真实验结果对这些算法进行了对比和分析。

关键词： 压缩感知； 稀疏信号； 重构算法； 匹配追踪类压缩感知算法

中图分类号：TN919.81文献标志码：A 文章编号：1006-8228（2012）04-15-03

A survey of reconstruction algorithms based on matching in compressive sensing

Duanmu Chunjiang, Xiao Yanli

（Zhejiang Normal University， School of Mathematics， Physics， and Information Engineering, Jinhua， Zhejiang 321004， China）

Abstract：The compressive sensing theory is a recent proposed theory, which can utilize the sparse and compressive characteristics of signals to combine the sampling and compression processes into only one procedure. It overcomes the shortcomings of large sampling data and significant waste of resource in traditional theories. The research areas in compressive sensing mainly include the sparse representation of signals, the design of measurement matrix, and signal reconstruction algorithms. The reconstruction algorithm is the key component of this new theory and is the focus of recent research. In this paper, the reconstruction algorithms, which use matching and tracking techniques, are described in details. Simulations of these algorithm are also conducted to compare and analyze these algorithms.

Key words： compressive sensing, sparse signal, reconstruction algorithm, compress sensing algorithms based on matching

1 CS（压缩感知）背景知识

压缩感知理论[1-4]是一种能够在采样的同时实现压缩目的的新理论，其基本思想是：只要信号本身或者信号在某个变换域上是稀疏的或可压缩的，那么就可以用一个与变换域不相关的测量矩阵将变换域的高维信号投影到一个低维空间上，然后通过求解一个优化问题就能够从少量的投影系数中以较高的概率成功或近似地重构出原信号。在该理论框架下，采样速率不依赖于信号带宽，而取决于信号本身的结构和内容。该理论的基本框架如图1所示。

图1压缩感知理论框架

信号的可稀疏性是压缩感知理论的基础和前提。只有选择合适的基来表示信号，才能保证信号的稀疏度，从而保证信号的精确重构。假设给定一组基（设为标准正交基ψ），如果一个长度为N的信号x可以用ψ中K个基向量线性表示，那么有：

（1.1）

则称x为K阶稀疏信号。其中系数，由此可以看出，x和s是对同一信号的两种等价描述形式，x为信号时域形式，s为信号在ψ域的变换形式。

当我们用一个已知的测量矩阵来采样未知的稀疏信号x时，则可得到M维的线性测量值y=RM。

（1.2）

其中，是M×N维的矩阵，称作传感矩阵。对于测量值y，可以看成是s关于传感矩阵的测量值。当传感矩阵满足RIP（约束等距条件）[5]时，可以通过求解问题(1.2)的逆问题先求出稀疏系数s，然后由式(1.1)解出x，从而将x从M维的观测向量y中正确地恢复出来。信号稀疏重构问题的最直接有效方法是通过一个类似l0范数的最优化问题来重构原始信号x，即：

s.t.φx=y（1.3）

其中是重构出的信号。

通过上述分析可知，压缩传感理论的研究主要包括三个方面：信号的稀疏表示、测量矩阵的设计和信号的重构算法。信号的重构算法是压缩传感理论当中相当关键的一部分，其算法主要有两类：一类是匹配追踪类重构算法，主要是求解l0范数的最小化问题，主要包括正交匹配追踪(OMP)算法[6]、正则化正交匹配追踪（ROMP）算法[7]、子空间追踪（SP）算法[8]、压缩抽样匹配追踪（CoSaMP）算法[9]；另一类是凸松弛类算法，它是把l0范数最小化直接转化为l1范数最小化，并通过凸优化方法求解，主要包括基追踪算法[10]、梯度追踪算法[11]、迭代硬阈值算法[12]等。下面主要对匹配追踪类重构算法进行具体的介绍和比较分析。

2 CS匹配追踪类重构算法

匹配追踪类重构算法主要是运用贪婪算法思想来解决l1范数问题。其基本思想是在每一次的迭代过程中，从过完备原字库里（即测量矩阵φ）选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子，并把它们放在不断更新的原子支撑集φ∧中，依次类推，经过数次迭代，该信号便可以用这些原子进行线性表示。

在允许一定重构误差存在的情况下，l0范数最小化求解模型为式(2.1)。

s.t. (2.1)

其中：s为信号x的稀疏变换域形式，ε是一个较小的常数。

在匹配追踪类算法中，对于相关系数u的计算，是通过余量r与测量矩阵φ（）中各个原子之间内积的绝对值来求解的，如式(2.2)：

(2.2)

然后采用最小二乘法进行求解信号逼近值以及余量的更新值rnew：

(2.3)

(2.4)

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

OMP算法是对MP(匹配追踪)算法的一种改进。该算法仍然沿用了MP算法中的原子选择准则，即从原子集合φ中选择和观测信号或迭代余量最为匹配的原子。除此之外，OMP算法需要将已选择的原子运用Gram-Schmidt正交化方法进行处理，然后再将信号投影在这些正交原子构成的空间上，从而得到信号在各个已选原子上的分量和迭代余量。基于这种正交性处理，OMP算法不会重复地选择原子，因此经过有限次（K次）迭代后就能够收敛到稀疏解，从而大大降低了迭代次数。正是由于这种原子正交化处理的加入，加大了OMP算法的计算量，使得信号重构时间远远长于匹配追踪算法，所以对于一些大规模信号，OMP算法可能无法使用。

另外，OMP的重构算法是在迭代次数已知的条件下重构的，这种使迭代过程强制停止的方法使得OMP算法需要大量的线性测量来保证其重构精度。OMP算法以贪婪迭代的方法选择出列，使得在每次迭代中选择的列与当前的冗余向量最大程度地相关，然后从测量向量中减去相关部分并反复迭代，直至迭代次数达到稀疏度K后强制停止。

其具体步骤如下：

① 初始余量r0=y，迭代次数n=1，信号稀疏度为K，索引值集合；

② 用式(2.2)计算相关系数u，并找出u中最大值对应的索引值m，存入索引集合中，即；

③ 更新原子支撑集φ∧；

④ 应用式(2.3)得到，同时用式(2.4)对余量r进行更新；

⑤ 若，令r=rnew，n=n+1，转步骤②，否则，停止迭代。

2.2 正则化正交匹配追踪（ROMP）算法

ROMP算法解决了OMP算法对感知矩阵要求比较严格这一问题。文献中所提出的ROMP算法对所有满足RIP条件的矩阵和所有能够准确估计出稀疏度的信号都可以精确重构，并且重建速度较快。

对于K-稀疏的信号重构问题，ROMP算法和OMP算法的不同之处主要是在于进行了两次原子的选择。首先它和OMP算法一样采用相关性原则进行原子的一次筛选，然后通过求余量r与测量矩阵φ中各个原子内积的绝对值，来计算相关系数u，并按照此方法将筛选出的K个原子的索引值存到候选索引集J中以进行原子的二次筛选。对于原子的二次筛选，ROMP算法主要是采用了正则化过程，因此它被叫做正则化正交匹配追踪算法。其方法是根据式(2.5)将J中索引值所对应原子的相关系数分成若干组：

i,j∈J (2.5）

然后选择能量最大的一组相关系数所对应的原子索引值存入g0中，同时将其原子存入更新支撑集φ∧中。该正则化过程可以使得ROMP算法最多经过K次迭代便可以得到一个原子数小于2K的支撑集φ∧用于精确重构信号，对于没有选入支撑集的原子，此正则化过程则能够保证它们的能量一定远小于被选入原子的能量，从而提高了信号的重构可靠性。经过一定的迭代次数得到用于信号重构的支撑集φ∧后，再采用最小二乘法进行信号逼近及余量更新。

其算法的基本步骤是：

① 设初始余量r0=y，迭代次数n=1，信号稀疏度为K，索引值集合；

② 用式(2.2)计算相关系数u，并找出u中最大值对应的索引值m，存入索引集合中，即；

③ 对J中索引值所对应原子的相关系数进行正则化，并将结果存入集合g0中，同时保证该集合中原子的相关系数必须满足式(2.5)；

④ 更新原子支撑集φ∧；

⑤ 应用式(2.3)得到，同时用式(2.4)对余量进行更新；

⑥ 若候选集的原子个数不小于2k个，则停止迭代，否则，令r=rnew，n=n+1，转步骤②。

2.3 子空间追踪（SP）算法

SP算法是一种存在或不存在噪声干扰的情况下都可以用于稀疏信号重构的方法。这一算法与OMP类算法相比具有更低的计算复杂度。分析显示，在无噪声情况下，对于由带有一个常量参数的受限等距矩阵所提供的任意稀疏信号，SP算法都可以精确恢复原信号；存在噪声或信号不是严格稀疏时，SP算法可以通过加倍测量数和信号干扰能量常量的方法，来确定重构均方差的上界。

SP算法的基本思想是在贪婪算法的基础上借用回溯的思想，在每一次迭代过程中混合一个简单的方法来重新估计所有候选者的可信赖性，这主要体现在原子的选择方式上。该算法与OMP算法不同的是从原子库中选择多个较相关的原子后再剔除部分原子，保证每次迭代时支撑集φ∧中有K个原子，因而候选集合中最多不会超过2K个原子，每次剔除的数目最多也不会超过K个。该算法的具体步骤如下：

① 设初始余量r0=y，迭代次数n=1，信号稀疏度为K，索引值集合；

② 用式（2.2）计算相关系数u，并找出u中K最大值对应的索引值m0,m1…mk，将其存入索引集合中，即；

③ 更新原子支撑集φ∧；

④ 应用式(2.3)得到，同时用式(2.4)对余量进行更新；

⑤ 若候选集中的原子个数大于2k个，则停止迭代，否则，令r=rnew，n=n+1，转步骤②。

2.4 压缩抽样匹配追踪（CoSaMP）算法

Needell等人提出的CoSaMP算法也可以很好地进行信号重构。它和SP算法一样也是在贪婪算法的基础上结合了组合算法中的回溯思想，在每一次迭代过程中，重新评估所有候选项的可能性。不同的是，该算法是在每次迭代后支撑集中就有2K个原子，因而保证了候选集合中最多不会超过3K个原子，同时剔除的原子数目最多不会超过K个。这种从原字库中选择多个较相关的原子同时再剔除部分原子的方法，提高了该算法的效率。

CoSaMP算法的具体步骤：

① 设初始余量r0=y，迭代次数n=1，信号稀疏度为K，索引值集合；

② 用式(2.2）计算相关系数u，并找出u中2K最大值对应的索引值m0，m1…m2k-1，m2k，将其存入索引集中，即；

③ 更新原子支撑集φ∧；

④ 应用式(2.3)得到，同时用式(2.4)对余量进行更新；

⑤ 若候选集中的原子个数大于3k个，则停止迭代；否则，令r=rnew，n=n+1，转步骤②。

3 实验结果和分析

由于信号在不同基变换下的稀疏度不同，从而影响到恢复原始图像的质量。在本文中，为了在同等条件下客观地反应上述算法的重构性能，我们采用大小为256×256的Lena图像如（图1所示为原始图像）作为测试图像，然后采用离散余弦变换（图2所示为稀疏变换DCT）作为稀疏变换以及正态随机矩阵（图3所示为测量矩阵）作为测量矩阵，以M/N=1/2的采样速率，稀疏度k估计为测量值的1/4，分别应用OMP算法、SP算法、CoSaMP算法进行图像的重建，重构图像分别如图4、5、6所示：

图1.原始图像 图2.稀疏变换 图3.测量矩阵

图4.OMP算法重构的图像图5. SP算法重构的图像

图6.CoSaMP算法重构的图像

通过上述图像恢复的仿真结果，我们可以看出OMP算法恢复的图像质量明显优于CoSaOMP算法和SP算法。

4 结束语

压缩感知理论是一种全新的采样压缩理论，其中信号的重构算法是压缩感知中比较关键的一部分，它的关键在于如何从低维信号恢复出高维信号。本文对于已有的经典的机遇匹配类的重构算法作了具体的介绍和实验仿真，描述了这些算法的具体过程和优缺点，并通过仿真实验对它们进行了实际恢复效果的比较。

参考文献：

[1] Donoho D L.Compressed sensing[J].IEEE Transactions on Iformation Theory,2006.52(4):1289~1306

[2] Candes E,Tao T.Decoding by linear programming[J].IEEE Transactions on Information Theory,2005.51(12):4203~4215

[3] Candes E,Romberg J and Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on Information Theory,2006.52(2):489~509

[4] Candes E,Tao T.Tear-optimal signal recovery from random projections:Universal encoding strategies[J].IEEE Transactions on Information Theory,2006.52(12):5406~5425

[5] 姚远,刘鹏,王辉,等.基于稀疏矩阵存储的状态表压缩算法[J].计算机应用,2010.30(8):2157~2160

[6] Tropp J A,Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory，2007.53(12)：4655~4666

[7] 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

[8] Dai W，Mllenkovic O．Subspace pursuit for compressive sensing

signal reconstruction［J］．IEEE Transactions on Information Theory，2009.55(5)：2230~2249

[9] Needell D，Tropp J A．CoSaMP：Iterative signal recovery from

incomplete and inaccurate samples［J］．Applied and Computational Harmonic Analysis，2009.26(3)：301~321

[10] S S Chen，D L Donoho，M A Saunders，etc．Atomic

decomposition by basis pursuit［J］．SIAM Journal of Scientific Computing，1998.20(1)：33~61

[11] Blumensath T，Davies M E．Gradient pursuits[J]．IEEE Transactions on Signal Processing，2008.56(6)：2370~2382

[12] Blumensath T，Davies M E．Iterative hard thresholding for compressed sensing ［J］．Applied and Computational Harmonic Analysis，2009.27(3)：265~274