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

《基于压缩感知的信号重构算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、基于压缩感知的的信号重构算法1引言至今，已有众多国内外学者在重建算法领域做岀了新的研究和探索。Candes等证明了信号重建问题可以通过求解最小厶范数问题解决，但Donoho指出，求解最小厶范数是一个NP问题，需要穷举X屮非零值的所有K屮排列可能，因而无法直接求解。此后，研究人员提岀了一系列求得次最优解的算法，主要包括最小厶范数法、贪婪迭代匹配追踪系列算法等。其中，匹配追踪类方法为其近似求解提供了有力工具，文献中指出了该类方法用于稀疏信号重建时具有一定的稳定性。重建算法的关键是如何从压縮感知得到的低维数据中精确地恢复出原始的高维数据，即由M维测量向量重建出长度为N(M

2、号X的过程。传统的兀配追踪算法能够精确的重建出原始信号，但同吋又有不同方面的缺陷，因此有关压縮感知重建算法的研究还有很多值得探索和研究的地方。2最小/。范数模型从数学意义上讲，基于压缩感知理论的信号重建问题就是寻找欠定方程组(程的数量少于待解的未知数)的最简单解的问题，厶范数刻画得就是信号中非零元素的个数，因而能够使得结果尽可能地稀疏。通常我们采用下式描述最小厶范数最优化问题：min

3、

4、x

5、

6、()s.t.Y=^)X(3.1)实际中，允许一定程度的课差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中/是一个极小的常量：minXns.t.Y-d>X；<3(3.2)

7、但是这类问题的求解数值计算极不稳定，很难直接求解。基于压缩感知的的信号重构算法1引言至今，已有众多国内外学者在重建算法领域做岀了新的研究和探索。Candes等证明了信号重建问题可以通过求解最小厶范数问题解决，但Donoho指出，求解最小厶范数是一个NP问题，需要穷举X屮非零值的所有K屮排列可能，因而无法直接求解。此后，研究人员提岀了一系列求得次最优解的算法，主要包括最小厶范数法、贪婪迭代匹配追踪系列算法等。其中，匹配追踪类方法为其近似求解提供了有力工具，文献中指出了该类方法用于稀疏信号重建时具有一定的稳定性。重建算法的关键是如何从压縮感知得到的低维数据中精确地恢复出原始的高维

8、数据，即由M维测量向量重建出长度为N(M

9、

10、x

11、

12、()s.t.Y=^)X(3.1)实际中，允许一定程度的课差存在，因此将原始的最优化问题转化成一个较简单的近似形式求解，其中/是一个极小的

13、常量：minXns.t.Y-d>X；<3(3.2)但是这类问题的求解数值计算极不稳定，很难直接求解。3匹配追踪类算法匹配追踪类稀疏重建算法解决的是最小/。范数问题，最早提岀的有匹配追踪(MP)算法和止交匹配追踪(OMP)算法。MP的基本思想是在每一次的迭代过程中，从过完备原子库里(即感知矩阵)选择与信号最匹配的原子来进行稀疏逼近并求出余量，然后继续选出与信号余量最为匹配的原子。经过数次迭代，该信号便可以由一些原子线性表示。但是由于信号在己选定原子(感知矩阵的列向量)集合上的投影的非正交性使得每次迭代的结果可能是次最优的，因此为获得较好的收敛效果往往需要经过较多的迭代次数。OM

14、P算法则有效克服了这个问题，该算法沿用了匹配追踪算法中的原子选择准则，在重建时每次迭代得到F的支撑集的一个原子，只是通过递归对己选择原子集合进行正交化以保证迭代的最优性，从而减少迭代次数。实验表明对固定K-稀疏的N维离散时间信号X,用高斯随机矩阵时，只要M=O(KlogN),止交匹配追踪算法将以极大概率准确重构信号，而且运行吋间远比最小厶范数模型短。但是，正交匹配追踪算法精确重构的理论保证比最小厶范数算法弱，并非对所有信号都能准确重构，而且对于感知矩阵的耍求比约束等距性更加严格。Needell等在OMP的基础上提出了正则正交匹配追踪(RegularizedOrthogonal

15、MatchingPinsiiiLROMP)算法，对于所有满足约束等距性条件的矩阵和所有稀疏信号都可以准确重构。之后，Needell等人又提出了引入回溯思想的压缩采样匹配追踪(CtmpressiveSamplingMatchingPinsuit,CoSaMP)算法，不仅提供了比OMP算法更全面的理论保证，并且能在采样过程中对噪声有很强的鲁棒性。同样引入回溯思想的还有子空间追踪(SubspacePuisuiLSP）算法,在得到F的支撑集之前先建立一个候选集，之后再从候选集中舍弃不需要的原子，形成最终的支撑集