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

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

2、 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

3、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 reconstructi

4、on algorithms, which论文发表专家 ED国学JK友志厕 www.qikanwang,netuse 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 al

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

6、度，从而保证信号的精确重构。 假设给定一组基（设为标准正交基甲），如果一个长度为n的信号x 可以用甲中k个基向量线性表示，那么有：（1.1）论文发表专家 ED国学JK友志厕 www.qikanwang,net则称X为k阶稀疏信号。其中系数，由此可以看出，x和s是对 同一信号的两种等价描述形式，X为信号时域形式，s为信号在甲 域的变换形式。当我们用一个已知的测量矩阵来采样未知的稀疏信号X时，则可 得到m维的线性测量值y=rm。(1.2)其中，是mXn维的矩阵，称作传感矩阵。对于测量值y，可以看 成是s关于传感矩阵的测量值。当传感矩阵满足rip (约束等距条 件)5时，可以通过求解问题(1.2)的

7、逆问题先求出稀疏系数s， 然后由式(1.1)解出X，从而将x从m维的观测向量y中正确地恢复 出来。信号稀疏重构问题的最直接有效方法是通过一个类似10范 数的最优化问题来重构原始信号X，即：s.t. 甲 X=y(1.3)其中是重构出的信号。通过上述分析可知，压缩传感理论的研究主要包括三个方面：信 号的稀疏表示、测量矩阵的设计和信号的重构算法。信号的重构算 法是压缩传感理论当中相当关键的一部分，其算法主要有两类：一 类是匹配追踪类重构算法，主要是求解10范数的最小化问题，主 要包括正交匹配追踪(omp)算法6、正则化正交匹配追踪(romp) 算法7、子空间追踪(sp)算法8、压缩抽样匹配追踪(co

8、samp) 算法9；另一类是凸松弛类算法，它是把l0范数最小化直接转化论文发表专家 ED国学JK友志厕 www.qikanwang,net为11范数最小化，并通过凸优化方法求解，主要包括基追踪算法 10、梯度追踪算法11、迭代硬阈值算法12等。下面主要对匹 配追踪类重构算法进行具体的介绍和比较分析。2 cs匹配追踪类重构算法匹配追踪类重构算法主要是运用贪婪算法思想来解决11范数问 题。其基本思想是在每一次的迭代过程中，从过完备原字库里(即 测量矩阵？)选择与信号最匹配的原子来进行稀疏逼近并求出余 量，然后继续选出与信号余量最为匹配的原子，并把它们放在不断 更新的原子支撑集？ A中，依次类推，经

9、过数次迭代，该信号便可 以用这些原子进行线性表示。在允许一定重构误差存在的情况下，10范数最小化求解模型为式 (2.1)。s.t.(2.1)其中：s为信号x的稀疏变换域形式，是一个较小的常数。在匹配追踪类算法中，对于相关系数u的计算，是通过余量r与 测量矩阵？()中各个原子之间内积的绝对值来求解的，如式(2.2)：(2.2)然后采用最小二乘法进行求解信号逼近值以及余量的更新值rnew：(2.3)(2.4)论文发表专家 ED国学JK技志厕 www.qikanwang,net2.1正交匹配追踪（omp）算法omp算法是对mp（匹配追踪）算法的一种改进。该算法仍然沿用了 mp算法中的原子选择准则，即

10、从原子集合w中选择和观测信号或迭 代余量最为匹配的原子。除此之外，omp算法需要将已选择的原子 运用gram-schmidt正交化方法进行处理，然后再将信号投影在这 些正交原子构成的空间上，从而得到信号在各个已选原子上的分量 和迭代余量。基于这种正交性处理，omp算法不会重复地选择原子， 因此经过有限次（k次）迭代后就能够收敛到稀疏解，从而大大降 低了迭代次数。正是由于这种原子正交化处理的加入，加大了 omp 算法的计算量，使得信号重构时间远远长于匹配追踪算法，所以对 于一些大规模信号，omp算法可能无法使用。另外，omp的重构算法是在迭代次数已知的条件下重构的，这种 使迭代过程强制停止的方法

11、使得omp算法需要大量的线性测量来保 证其重构精度。omp算法以贪婪迭代的方法选择出列，使得在每次 迭代中选择的列与当前的冗余向量最大程度地相关，然后从测量向 量中减去相关部分并反复迭代，直至迭代次数达到稀疏度k后强制 停止。其具体步骤如下：初始余量r0=y，迭代次数n=1，信号稀疏度为k，索引值集合；用式（2.2）计算相关系数u，并找出u中最大值对应的索引值论文发表专家 ED国学JK技志厕 www.qikanwang,net 口，存入索引集合中，即；更新原子支撑集？ A；应用式(2.3)得到，同时用式(2.4)对余量r进行更新；若，令r=rnew, n=n+1，转步骤，否则，停止迭代。2.2

12、正则化正交匹配追踪(romp)算法romp算法解决了 omp算法对感知矩阵要求比较严格这一问题。文 献中所提出的romp算法对所有满足rip条件的矩阵和所有能够准 确估计出稀疏度的信号都可以精确重构，并且重建速度较快。对于k-稀疏的信号重构问题，romp算法和omp算法的不同之处 主要是在于进行了两次原子的选择。首先它和omp算法一样米用相 关性原则进行原子的一次筛选，然后通过求余量r与测量矩阵？中 各个原子内积的绝对值，来计算相关系数u，并按照此方法将筛选 出的k个原子的索引值存到候选索引集j中以进行原子的二次筛 选。对于原子的二次筛选，romp算法主要是采用了正则化过程，因 此它被叫做正则

13、化正交匹配追踪算法。其方法是根据式(2.5)将j 中索引值所对应原子的相关系数分成若干组：i,jEj(2.5)然后选择能量最大的一组相关系数所对应的原子索引值存入g0 中，同时将其原子存入更新支撑集？A中。该正则化过程可以使得 romp算法最多经过k次迭代便可以得到一个原子数小于2k的支撑 集？ A用于精确重构信号，对于没有选入支撑集的原子，此正则化论文发表专家 ED国学JK技志厕 www.qikanwang,net过程则能够保证它们的能量一定远小于被选入原子的能量，从而提 高了信号的重构可靠性。经过一定的迭代次数得到用于信号重构的 支撑集？ A后，再采用最小二乘法进行信号逼近及余量更新。其算

14、法的基本步骤是：设初始余量r0=y，迭代次数n=1,信号稀疏度为k,索引值集合；用式(2.2)计算相关系数u,并找出u中最大值对应的索引值 口，存入索引集合中，即；对j中索引值所对应原子的相关系数进行正则化，并将结果 存入集合g0中，同时保证该集合中原子的相关系数必须满足式；更新原子支撑集？ A；应用式(2.3)得到，同时用式(2.4)对余量进行更新；若候选集的原子个数不小于2k个，则停止迭代，否则，令 r=rnew，n=n+1，转步骤。2.3子空间追踪(sp)算法sp算法是一种存在或不存在噪声干扰的情况下都可以用于稀疏信号重构的方法。这一算法与omp类算法相比具有更低的计算复杂 度。分析显示

15、，在无噪声情况下，对于由带有一个常量参数的受限 等距矩阵所提供的任意稀疏信号，sp算法都可以精确恢复原信号； 存在噪声或信号不是严格稀疏时，sp算法可以通过加倍测量数和信论文发表专家 ED国学JK友志厕 www.qikanwang,net 号干扰能量常量的方法，来确定重构均方差的上界。sp算法的基本思想是在贪婪算法的基础上借用回溯的思想，在每 一次迭代过程中混合一个简单的方法来重新估计所有候选者的可 信赖性，这主要体现在原子的选择方式上。该算法与omp算法不同 的是从原子库中选择多个较相关的原子后再剔除部分原子，保证每 次迭代时支撑集？A中有k个原子，因而候选集合中最多不会超过 2k个原子，每

16、次剔除的数目最多也不会超过k个。该算法的具体步 骤如下：设初始余量r0=y，迭代次数n=1，信号稀疏度为k，索引值集 合；用式(2.2)计算相关系数u，并找出u中k最大值对应的索 引值m0,m1mk，将其存入索引集合中，即；更新原子支撑集？ A；应用式(2.3)得到，同时用式(2.4)对余量进行更新；若候选集中的原子个数大于2k个，则停止迭代，否则，令 r=rnew，n=n+1，转步骤。2.4压缩抽样匹配追踪(cosamp)算法needell等人提出的cosamp算法也可以很好地进行信号重构。它 和sp算法一样也是在贪婪算法的基础上结合了组合算法中的回溯 思想，在每一次迭代过程中，重新评估所有

17、候选项的可能性。不同 的是，该算法是在每次迭代后支撑集中就有2k个原子，因而保证论文发表专家 ED国学JK友志厕 www.qikanwang,net 了候选集合中最多不会超过3k个原子，同时剔除的原子数目最多 不会超过k个。这种从原字库中选择多个较相关的原子同时再剔除 部分原子的方法，提高了该算法的效率。cosamp算法的具体步骤：设初始余量r0=y，迭代次数n=1，信号稀疏度为k，索引值集 合；用式(2.2)计算相关系数u，并找出u中2k最大值对应的索 引值m0，m1m2kT，m2k，将其存入索引集中，即;更新原子支撑集;应用式(2.3)得到，同时用式(2.4)对余量进行更新；若候选集中的原

18、子个数大于3k个，则停止迭代；否则，令 r=rnew，n=n+1，转步骤。3实验结果和分析由于信号在不同基变换下的稀疏度不同，从而影响到恢复原始图 像的质量。在本文中，为了在同等条件下客观地反应上述算法的重 构性能，我们采用大小为256X256的lena图像如(图1所示为原 始图像)作为测试图像，然后采用离散余弦变换(图2所示为稀疏 变换dct)作为稀疏变换以及正态随机矩阵(图3所示为测量矩阵) 作为测量矩阵，以m/n=1/2的采样速率，稀疏度k估计为测量值的 1/4，分别应用omp算法、sp算法、cosamp算法进行图像的重建， 重构图像分别如图4、5、6所示：论文发表专家由国导氟友志网gw

19、ww.qikanwang,net图1.原始图像图2.稀疏变换图3.测量矩阵图4. omp算法重构的图像 图5. sp算法重构的图像图6. cosamp算法重构的图像通过上述图像恢复的仿真结果，我们可以看出omp算法恢复的图 像质量明显优于cosaomp算法和sp算法。4结束语压缩感知理论是一种全新的采样压缩理论，其中信号的重构算法 是压缩感知中比较关键的一部分，它的关键在于如何从低维信号恢 复出高维信号。本文对于已有的经典的机遇匹配类的重构算法作了 具体的介绍和实验仿真，描述了这些算法的具体过程和优缺点，并 通过仿真实验对它们进行了实际恢复效果的比较。参考文献：donoho d pressed

20、 sensingj.ieee transactions on iformation theory,2006.52(4):12891306candes e,tao t.decoding by linear programmingj.ieee transactions on information theory,2005.51(12):42034215candes e,romberg j and tao t.robust uncertainty论文发表专家 ED国学JK技志厕 www.qikanwang,netprinciples:exact signal reconstruction from

21、highly incomplete frequency informationj.ieee transactions on information theory,2006.52(2):489509candes e,tao t.tear-optimal signal recovery from random projections:universal encoding strategiesj.ieee transactions on information theory,2006.52(12):54065425姚远，刘鹏，王辉，等.基于稀疏矩阵存储的状态表压缩算法 j.计算机应用,2010.30

22、(8):21572160tropp j a,gilbert a c.signal recovery from random measurements via orthogonal matching pursuitj.ieee transactions on information theory， 2007.53(12): 46554666needell d， vershynin r. uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit j .foundations of computational mathematics,