基于压缩感知的信号重构算法

0基于压缩感知的的信号重构算法1引言至今，已有众多国内外学者在重建算法领域做出了新的研究和探索。Candes等证明了信号重建问题可以通过求解最小0l范数问题解决，但Donoho指出，求解最小0l范数是一个NP问题，需要穷举X中非零值的所有K中排列可能，因而无法直接求解。此后，研究人员提出了一系列求得次最优解的算法，主要包括最小1l范数法、贪婪迭代匹配追踪系列算法等。其中，匹配追踪类方法为其近似求解提供了有力工具，文献中指出了该类方法用于稀疏信号重建时具有一定的稳定性。重建算法的关键是如何从压縮感知得到的低维数据中精确地恢复出原始的高维数据，即由M维测量向量重建出长度为()NMN的信号X的过程。传统的匹配追踪算法能够精确的重建出原始信号，但同时又有不同方面的缺陷，因此有关压縮感知重建算法的研究还有很多值得探索和研究的地方。2最小0l范数模型从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组(程的数量少于待解的未知数)的最简单解的问题，0l范数刻画得就是信号中非零元素的个数，因而能够使得结果尽可能地稀疏。通常我们采用下式描述最小0l范数最优化问题：0minXs.t.YX(3.1)实际中，允许一定程度的误差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中是一个极小的常量：0minXs.t.22YX(3.2)但是这类问题的求解数值计算极不稳定，很难直接求解。3匹配追踪类算法1匹配追踪类稀疏重建算法解决的是最小0l范数问题，最早提出的有匹配追踪(MP)算法和正交匹配追踪(OMP)算法。MP的基本思想是在每一次的迭代过程中，从过完备原子库里(即感知矩阵)选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子。经过数次迭代，该信号便可以由一些原子线性表示。但是由于信号在己选定原子(感知矩阵的列向量)集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得较好的收敛效果往往需要经过较多的迭代次数。OMP算法则有效克服了这个问题，该算法沿用了匹配追踪算法中的原子选择准则，在重建时每次迭代得到ˆX的支撑集的一个原子，只是通过递归对己选择原子集合进行正交化以保证迭代的最优性，从而减少迭代次数。实验表明对固定K稀疏的N维离散时间信号X，用高斯随机矩阵时，只要(log)MOKN，正交匹配追踪算法将以极大概率准确重构信号，而且运行时间远比最小1l范数模型短。但是，正交匹配追踪算法精确重构的理论保证比最小1l范数算法弱，并非对所有信号都能准确重构，而且对于感知矩阵的要求比约束等距性更加严格。Needell等在OMP的基础上提出了正则正交匹配追踪(RegularizedOrthogonalMatchingPursuit,ROMP)算法，对于所有满足约束等距性条件的矩阵和所有稀疏信号都可以准确重构。之后，Needell等人又提出了引入回溯思想的压缩采样匹配追踪(CompressiveSamplingMatchingPursuit,CoSaMP)算法，不仅提供了比OMP算法更全面的理论保证，并且能在采样过程中对噪声有很强的鲁棒性。同样引入回溯思想的还有子空间追踪(SubspacePursuit,SP)算法，在得到ˆX的支撑集之前先建立一个候选集，之后再从候选集中舍弃不需要的原子，形成最终的支撑集，它们理论重建质量与相当，同时重建复杂度低，但是这些算法都是建立在稀疏度K已知的基础上。然而实际应用中，K往往是未知的，由此出现了对K自适应的稀疏自适应匹配追踪(SparsityAdaptiveMatchingPursuit,SAMP)算法，它通过固定步长逐步逼近进行重建，可以在K未知的情况下获得较好的重建效果，速度也远快于OMP算法。综合考虑，匹配追踪系列算法对于维数较低的小尺度信号问题运算速度很快，是一种效果较好的信号重建算法。23.1OMP算法OMP算法作为最早的贪婪迭代算法之一，它的思想对之后出现的各种贪婪算法都有着不容忽视的意义。OMP仍然沿用了MP算法中的原子选择准则，不同的是OMP算法要将所选原子利用Gram-Schmidt正交化方法进行正交处理，再将信号在这些正交原子构成的空间上投影，得到信号在各个已选原子上的分量和余量，然后用相同方法分解余量。在每一步分解中，所选原子均满足一定条件，因此余量随着分解过程迅速减小。通过递归地对已选择原子集合进行正交化保证了迭代的最优性，从而减少了迭代次数。另一方面，OMP的重建算法是在给定迭代次数的条件下重建，这种强制迭代过程停止的方法使得OMP需要非常多的线性测量来保证精确重建。总之，它以贪婪迭代的方法选择的列，使得在每次迭代中所选择的列与当前的冗余向量最大程度地相关，从测量向量中减去相关部分并反复迭代，直到迭代次数达到稀疏度K，强制迭代停止。首先需要说明的是，匹配追踪类算法通过求余量r与感知矩阵中各个原子之间内积的绝对值，来计算相关系数u：|,,1,2,Njjjuuurj…，(3.3)并采用最小二乘法进行信号逼近以及余量更新:2ˆargminiRXYX(3.4)ˆr,newYX(3.5)OMP算法的具体步骤如下：(1)初始余量0rY，迭代次数1n，索引值集合，J；(2)计算相关系数u,并将u中最大值对应的索引值存入J中；(3)更新支撑集，其中0J；(4)应用式(3.3)得到ˆX，同时用式(3.4)对余量进行更新；(5)若2newrr，令newrr，1nn，转步骤(2)；否则，停止迭代。3为了进一步说明OMP算法的重建效果，采用大小为512512的Lena图像作为测试图像，为便于测量矩阵的生成，将该图像数据分成1024个大小为1616的块，进而生成大小为2561024的图像数据。利用该方法对原图像进行预处理之后，采用离散余弦变换作为稀疏变换以及高斯随机矩阵作为测量矩阵。表3.1和图3-1直观地给出了Lena图像在采样率分别为M/N=0.7、0.5、0.3时的重建图像。OMP算法保证了每次迭代的最优性，减少了迭代的次数。但是，它在每次迭代中仅选取一个原子来更新原子集合，这样必然会付出巨大的重建时间代价。迭代的次数与稀疏度X或采样个数M密切相关，随着迭代次数的增大，耗时也将大幅增加。因此之后出现了许多改进的匹配追踪算法，如ROMP、StOMP、CoSaMP算法等等，都希望在重建时间和重建质量之间取得一个较好的平衡，保证重建质量的同时提高重建效率。3.2ROMP算法正则正交匹配追踪(ROMP)算法对所有满足RIP条件的矩阵和所有稀疏信号都可以精确重建，且重建速度较快。对于稀疏度为K的信号重建问题，ROMP算法首先根据相关原则进行原子的一次筛选，通过求余量r与测量矩阵中各个原子之间内积的绝对值，来计算相关系数u，并将按照此方法筛选出的K个原子的索引值存到候选集J中以便进行原子的二次筛选。ROMP算法采用正则化过程进行原子的二次筛选，即根据式(2.6)将J中索引值对应的原子的相关系数分成若干组:()2()uiuj,ijJ(3.6)然后选择能量最大的一组相关系数对应的原子索引值存入0J中。该正则化过程可以使得化ROMP算法最多经过K次迭代便可以得到一个原子数||小于2K的支撑集用于精确重建信号，对于没有选入支撑集的原子，正则化过程则能保证它们的能量一定远小于被选入原子的能量，是一种简单有效的原子筛选方法。经过一定的迭代得到用于信号重建的支撑集后，再采用最小二乘法进行信号逼近以及余量更新。ROMP算法的基本步骤如下：(1)初始余量0rY，估计信号稀疏度为K，迭代次数1n，索引值集合4,J;(2)用式（3.3）计算相关系数u，并从u中寻找K个最大值对应的索引值存入J中；(3)对J中索引值对应原子的相关系数进行正则化，并将正则化结果存入集合0J中，该集合中原子的相关系数必须满足式(3.6);(4)更新支撑集，其中0J；(5)应用式(3.4)得到ˆX，同时用式(3.5)对余量进行更；(6)若2K，则停止迭代；否则令newrr，1nn，转步骤(2)。从上述算法的步骤中可以看出，只有首先对信号稀疏度进行适当估计才能进一步精确重建信号，但大量实验表明，如果对信号的稀疏度预先估计过小，那么迭代多次依然无法达到停止迭代条件；如果对稀疏度估计的过大，那么重建质量无论从视觉效果还是从客观数据上都很差，远不能达到精确重建的效果。3.3CoSaMP算法OMP算法每次只选择一个与余量相关的原子，从原子的选择方式上看实现了单个原子的精确选择。引入回溯思想的压缩采样匹配追踪(CompressiveSamplingMatchingPursuit,CoSaMP)算法则从原子库中选择多个较相关的原子同时剔除部分原子，从而提高算法效率。CoSaMP算法保证了候选集合最多不会超过3K个原子，每次迭代支撑集拥有2K个原子，同时剔除的原子数目最多不超过K个。CoSaMP算法具体算法如下：(1)初始余量0rY，估计信号稀疏度为K，迭代次数1n，索引值集合,J;(2)用式(3.3)计算相关系数u，并从u中寻找2K个最大值对应的索引值存入J中；(3)J，应用(3.4)得到ˆZ,取前K个最大元素对应的原子放入支撑集。(4)应用式(3.4)得到ˆX，同时用式(3.5)对余量进行更；(5)若2K，则停止迭代；否则令newrr，1nn，转步骤(2)。表3.2和图3-2给出了CoSaMP算法下Lena图像在采样率分别为M/N=0.7、0.5、0.35时的重建图像。CoSaMP算法每次迭代中都要同时选中多个原子，而且最终用于重建的支撑集大小是确定的，这就需要我们在迭代过程中不断选中原子的同时剔一部分以前选中的原子。那么这种方式能否保证每轮迭代中至少选中一个最终用于信号重建的原子而不会被剔除，这是一个值得质疑的问题。本文就其原子的选择方式对算法准确性的影响进行了分析和推导。结论说明即便剔除了己经选定的部分原子依然可以保证留下的原子是最优的从而精确重建信号。4正则化自适应匹配追踪算法虽然CoSaMP算法引入了回退筛选的思想，其重建质量与LP相当，同时重建复杂度低，但是这些算法都是建立在稀疏度K已知的基础上。然而实际应用中信号的稀疏度K往往是未知的，由此出现了对稀疏度K自适应的SAMP算法，它通过设置一个可变步长，逐步对信号稀疏度进行估计，因此可以在K未知的情况下获得较好的重建效果，速度也远快于OMP算法。基于ROMP算法和SAMP算法的突出优势，本文提出了正则化自适应匹配追踪算法，该算法解决了稀疏度K未知的情况下信号精确重建问题，同时也是一种近似解决0l范数最小问题的贪婪迭代算法。正则化自适应匹配追踪算法(RegularizedAdaptiveMatchingPursuit,RAMP)在采用ROMP算法中正则化过程的基础上，结合了SAMP算法的自适应思想。该算法在稀疏度问题上克服了正则化过程的局限性，算法本身可以在迭代过程中自动调整所选原子数目来重建稀疏度未知的信号。算法中采用转换阶段的方式逐步增加该原子数，将同一个迭代过程分成多个阶段，设置一个可变步长代替所选原子数目，相邻两个阶段所对应的支撑集的大小之差即为当前步长，随着步长的增加和支撑集的不断增大，实现了在未知稀疏度的前提下步长逐步逼近K进而精确重建出原始信号的目的。正则化自适应匹配追踪算法结合了ROMP算法正则化思想以及RAMP算法自适应思想的新的重建算法，保证了全局优化的同时提高了算法的运算速度。下列步骤具体说明了该算法的过程，其中1与2分别为控制迭代次数与阶段转换的闳值，为达到较好的重建精度以及严格控制阶段转换的目的，根据所处理信号的具体信息适当地选择阈值的大小，算法具体步骤如下：6(1)初始余量0rY，初始步长0size，阶段1size，迭代次数1n，索引值集合,J；(2)若12r，则停止迭代，利用得到的原子进行最终的信号重建；否则进入步骤(3)；(