压缩感知的重构算法.doc

压缩感知的重构算法 算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。 压缩感知的重构算法主要分为三大类： 1.组合算法 2.贪婪算法 3.凸松弛算法 每种算法之中又包含几种算法，下面就把三类重构算法列举出来。 组合算法：先是对信号进行结构采样，然后再通过对采样的数据进行 分组测试，最后完成信号的重构。 (1) 傅里叶采样（Fourier Representaion） (2) 链式追踪算法（Chaining Pursuit） (3) HHS追踪算法（Heavy Hitters On Steroids） 贪婪算法：通过贪婪迭代的方式逐步逼近信号。 (1) 匹配追踪算法（Matching Pursuit MP） (2) 正交匹配追踪算法（Orthogonal Matching Pursuit OMP） (3) 分段正交匹配追踪算法（Stagewise Orthogonal Matching Pursuit StOMP） (4) 正则化正交匹配追踪算法（Regularized Orthogonal Matching Pursuit ROMP） (5) 稀疏自适应匹配追踪算法（Sparisty Adaptive Matching Pursuit SAMP） 凸松弛算法： (1) 基追踪算法（Basis Pursuit BP） (2) 最小全变差算法（Total Variation TV） (3) 内点法（Interior-point Method） (4) 梯度投影算法（Gradient Projection） (5) 凸集交替投影算法（Projections Onto Convex Sets POCS） 算法较多，但是并不是每一种算法都能够得到很好的应用，三类算法各有优缺点，组合算法需要观测的样本数目比较多但运算的效率最高，凸松弛算法计算量大但是需要观测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中，也是三种重构算法中应用最大的一种。下面分别就贪婪算法中的MP，OMP算法以及凸松弛算法中的BP算法进行详细的介绍。 三种重建算法 本节主要是介绍一些基本的重建算法，比如贪婪迭代算法中的匹配追踪算法，正交匹配追踪算法，以及凸松弛算法中的基追踪算法，对其原理进行了介绍，并用matlab代码重构出来一维和二维的图形，进而比较这几种算法的性能。 1.匹配追踪算法（Matching Pursuit MP） 匹配追踪算法是Mallat和ZHANG在小波分析的基础上提出的，是贪婪迭代算法中的比较基本的算法，有其显著的特点，是学习研究贪婪算法的基础。 1.1 MP算法的原理 ，其中测量矩阵又称为过完备字典，每一列被称为一个原子，则测量矩阵中有n个原子，而y的长度为m，原子的个数远远大于信号的长度，即mn，因此测量矩阵又称为过完备字典。 信号y在测量矩阵上进行分解，可以用{}来表示，单位向量长度为1，要对过完备字典的原子进行归一化处理。 MP算法的基本思想： 从观测矩阵（过完备字典）中选择一个与信号y相关性最大（最匹配）的原子，也就是观测矩阵中的一列，构建信号的稀疏逼近，求出信号的残差，重复上面的操作，继续选择与信号残差最匹配的一个原子，如此反复迭代直到达到迭代次数，最后信号y就可以表示为这些原子的线性组合。 MP进行稀疏分解的步骤[1][2]： 从观测矩阵中选择一个与信号y最匹配的原子，也就是内积最大的一个原子，即： |y,|=|y,| （1） 其中，表示字典矩阵的列索引。先将信号y投影到向量 上，信号y也可以表示为： (2) (2)式等号右边的第一项为观测矩阵中最匹配原子的垂直投影分量，等式右边的第二项是y通过分解后的残差，且与y正交。 （2）式可以写为： （3） 对残差进行上面同样的分解，在第n次迭代过程中： （4） 因为和正交，则（4）式可以表示为： （5） 最后，信号y可以表示为： （6） 因为最后的残差正交于上次迭代产生的残差