压缩感知的重构算法

《压缩感知的重构算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、压缩感知的重构算法算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。压缩感知的重构算法主要分为三大类：1.组合算法2.贪婪算法3.凸松弛算法每种算法之中又包含几种算法，下面就把三类重构算法列举出来。组合算法：先是对信号进行结构采样，然

2、后再通过对采样的数据进行分组测试，最后完成信号的重构。(1)傅里叶采样（FourierRepresentaion）(2)链式追踪算法（ChainingPursuit）(3)HHS追踪算法（HeavyHittersOnSteroids）贪婪算法：通过贪婪迭代的方式逐步逼近信号。(1)匹配追踪算法（MatchingPursuitMP）(2)正交匹配追踪算法（OrthogonalMatchingPursuitOMP）(3)分段正交匹配追踪算法（StagewiseOrthogonalMatchingPu

3、rsuitStOMP）(4)正则化正交匹配追踪算法（RegularizedOrthogonalMatchingPursuitROMP）(5)稀疏自适应匹配追踪算法（SparistyAdaptiveMatchingPursuitSAMP）凸松弛算法：(1)基追踪算法（BasisPursuitBP）(2)最小全变差算法（TotalVariationTV）(3)内点法（Interior-pointMethod）(4)梯度投影算法（GradientProjection）(5)凸集交替投影算法（Proje

4、ctionsOntoConvexSetsPOCS）算法较多，但是并不是每一种算法都能够得到很好的应用，三类算法各有优缺点，组合算法需要观测的样本数目比较多但运算的效率最高，凸松弛算法计算量大但是需要观测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中，也是三种重构算法中应用最大的一种。下面分别就贪婪算法中的MP，OMP算法以及凸松弛算法中的BP算法进行详细的介绍。三种重建算法本节主要是介绍一些基本的重建算法，比如贪婪迭代算法中的匹配追踪算法，正交匹配追踪算法，以及凸松弛算法中的基追

5、踪算法，对其原理进行了介绍，并用matlab代码重构出来一维和二维的图形，进而比较这几种算法的性能。1.匹配追踪算法（MatchingPursuitMP）匹配追踪算法是Mallat和ZHANG在小波分析的基础上提出的，是贪婪迭代算法中的比较基本的算法，有其显著的特点，是学习研究贪婪算法的基础。1.1MP算法的原理，其中测量矩阵又称为过完备字典，每一列被称为一个原子，则测量矩阵中有n个原子，而y的长度为m，原子的个数远远大于信号的长度，即m<

6、行分解，可以用{}来表示，单位向量长度为1，要对过完备字典的原子进行归一化处理。MP算法的基本思想：从观测矩阵（过完备字典）中选择一个与信号y相关性最大（最匹配）的原子，也就是观测矩阵中的一列，构建信号的稀疏逼近，求出信号的残差，重复上面的操作，继续选择与信号残差最匹配的一个原子，如此反复迭代直到达到迭代次数，最后信号y就可以表示为这些原子的线性组合。MP进行稀疏分解的步骤[1][2]：从观测矩阵中选择一个与信号y最匹配的原子，也就是内积最大的一个原子，即：

7、

8、=

9、

10、（1）其中，

11、表示字典矩阵的列索引。先将信号y投影到向量上，信号y也可以表示为：(2)(2)式等号右边的第一项为观测矩阵中最匹配原子的垂直投影分量，等式右边的第二项是y通过分解后的残差，且与y正交。（2）式可以写为：（3）对残差进行上面同样的分解，在第n次迭代过程中：（4）因为和正交，则（4）式可以表示为：（5）最后，信号y可以表示为：（6）因为最后的残差正交于上次迭代产生的残差，则最后的表达式为：（7）由（7）式可知，当残差为零时，可以得到信号的精确分解。定理1[3]存在，使得一切对于时，有成立。这样（7）

12、式中，按照指数衰减的形式趋于零，也就是成立。参考文献：[1]曹离然.面向压缩感知的稀疏信号重建算法研究.[D].哈尔滨工业大学，2011.[2]Y.C.PATI.OrthogonalMatchingPursuit:RecursiveFunctionApproximationwithApplicationstoWaveletDecomposition.IEEE.1993:40-44[3]韩红平.压缩感知中信号重构算法的研究.[D].南京邮电大学，2012.1.2MP算法的理论框图根据上面的MP算法