1、压缩感知的重构算法算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。压缩感知的重构算法主要分为三大类：1.组合算法 2.贪婪算法 3.凸松弛算法每种算法之中又包含几种算法，下面就把三类重构算法列举出来。组合算法：先是对信号进行结构采样，然后再通过对采样的数据进行分组测试，最后完成信号的重构。(1) 傅里叶 采样（Fourier Re
2、presentaion）(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)
3、稀疏自适应匹配追踪算法（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）算法较多，但是并不是每一种算法都能够得到很好的应用，三类算法各有优缺点，组合算法需要观测的样本数目比较多但运算的效率最高，凸松弛算法计算量大但是需要观
4、测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中，也是三种重构算法中应用最大的一种。下面分别就贪婪算法中的 MP，OMP 算法以及凸松弛算法中的 BP 算法进行详细的介绍。三种重建算法本节主要是介绍一些基本的重建算法，比如贪婪迭代算法中的匹配追踪算法，正交匹配追踪算法，以及凸松弛算法中的基追踪算法，对其原理进行了介绍，并用 matlab 代码重构出来一维和二维的图形，进而比较这几种算法的性能。1.匹配追踪算法（Matching Pursuit MP）匹配追踪算法是 Mallat 和 ZHANG 在小波分析的基础上提出的，是贪婪迭代算法中的比较基本的算法，有其显著的特点，是学习研
5、究贪婪算法的基础。1.1 MP 算法的原理，其中测量矩阵 又称为过完备字典，每一列被称xy为一个原子，则测量矩阵中有 n 个原子，而 y 的长度为 m，原子的个数远远大于信号的长度，即 m|= | （1）0sup),.1(nii其中， 表示字典矩阵的列索引。先将信号 y 投影到向量 0上，信号 y 也可以表示为：0(2)R100,(2)式等号右边的第一项为观测矩阵中最匹配原子 的垂直投影分0量，等式右边的第二项 是 y 通过 分解后的残差，且与 y 正交。R10（2）式可以写为：（3）|,| 10222y对残差 进行上面同样的分解，在第 n 次迭代过程中：R1（4）Rnnnnn1,因为 和 正
6、交，则（4）式可以表示为：nn（5）|,| 1222 n最后，信号 y 可以表示为：（6）Rnini ii 10,因为最后的残差 正交于上次迭代产生的残差 ，则最后的表Rn1 n达式为：（7）|,| 1222Ryninoi 由（7）式可知，当残差 为零时，可以得到信号的精确分解。n1定理 13 存在 ，使得一切对于 时，有00n成立。|21ynnR这样（7）式中， 按照指数衰减的形式趋于零，也就是|1n成立。,|202ini参考文献： 1 曹离然 .面向压缩感知的稀疏信号重建算法研究.D.哈尔滨工业大学，2011.2 Y.C.PATI.Orthogonal Matching Pursuit:
7、Recursive Function Approximation with Applications to Wavelet Decomposition.IEEE.1993:40-443 韩红平 .压缩感知中信号重构算法的研究.D.南京邮电大学，2012.1.2 MP 算法的理论框图根据上面的 MP 算法的原理，得出 MP 算法的理论图 1，这样更容易理解。开始输入信号设置参数形成过完备原子库满足迭代停止条件？是，迭代停止否保存结果在过完备原子库中搜索最佳原子从残余分量中减去在最佳原子上的分量t=t+1图 1：MP 算法框图参考文献：1 韩红平 .压缩感知中信号重构算法的研究D.南京邮电大学，2
8、0121.3 MP 算法的算法流程根据 1.2 中介绍的 MP 算法的理论框图，现在写出 MP 算法的算法流程12 ，这样让我们对 MP 算法有一个更加清晰的理解。输入：测量矩阵 ，测量向量 ，稀疏度 k)(NM)1(Ny输出：重构信号 x（1）：初始化余量 ，迭代次数 n=0 1；yr0（2）：计算余量与测量矩阵的每一列的内积 ；共有 NrgnTn1个内积数值。(3)：找出 N 个 中的绝对值最大的元素 ，k 为对应的最大内gn )(n积的列号。（4）：计算信号的近似解 ；1kkgxnnn（5）：更新余量 ；knr1（6）：若满足迭代条件，则 n=n+1， ，若不满足迭代条件nx则返回步骤（
9、2） ；迭代次数为稀疏度的 2 倍。参考文献：1 Linfeng Du,Rui Wang. Analysis on Greedy Reconstruction Algorithms Based on Compressed Sensing.J.IEEE 2012:783-7892 文首先.压缩感知匹配追踪算法的研究.D.20131.4 MP 算法的信号重构本节分别通过对一维离散信号，二维 Lena 为例，进行 MP 算法的信号重构。（1）一维离散信号的 MP 算法仿真本次仿真使用 matlab 随机生成的一维离散信号，稀疏度 k=23,信号长度 N=256，观测向量的长度 M=80，那么采样率
10、M/N=0.3，其中的观测矩阵 是高斯随机矩阵。采用 MP 算法对一维信号进行重构，重构图如 1：图 1：MP 算法重构一维信号通过上面的重构可以得出，MP 算法对一维信号有很好的重构效果。（2）二维 lena 图像的 MP 算法重构我们上面的研究知道 MP 算法对一维信号有很好的重构作用，但是算法不只是要在一维信号中有好的重构功能，还要能很好的重构二维信号才可以，这样应用的范围才会更大。我们知道压缩感知重构的是可压缩的稀疏信号，二维信号是不稀疏的，这就要在进行算法重构的时候进行一些处理，我们可以先采用离散余弦变换（dct）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct） ，这样就
11、转化为了我们所需要的。本次在 matlab 中的仿真，我们采用的是 256 的 Lena 的二维图像，M=180，N=256，稀256疏度 k=40， M/N=0.7，观测矩阵是高斯随机矩阵，采用 MP 算法对二维图像进行重构，重构效果如图 2（b）：（a）原始图片 （b） MP 算法重构（M/N=0.7）通过上面的(a)图和（b）图可知，采样率为 0.7 的时候，MP算法也能对二维图像进行精确重构。2.正交匹配追踪算法（OMP）2.1OMP 算法的原理OMP 算法是在 MP 算法的基础上进行改进的，沿用了 MP 算法的重构的思想，但是又对 MP 算法进行了改进，使得算法的效率更高，应用更加的
12、广泛。MP 算法的信号分解中步骤中介绍： ，这Ry100,说明信号在已经选择的原子上的投影（等是右边第一项）是非正交的，还存在着残差，也就是说每次迭代的过程是次最优的，不是最优解，要想最终的迭代收敛，需要的迭代次数较多。OMP 算法就是根据 MP 算法的不足之处加以改进，把所选择的原子首先通过Schimidt 正交化处理，使得在达到迭代条件的时候需要的迭代次数较 MP 算法少，但是正交化的过程中会增加计算量。在每一步中如何对选择的全部原子进行正交化处理呢？这是OMP 算法和 MP 算法的不同之处。下面介绍 OMP 算法正交化原理1：信号 y 经 k 步分解：且 ，n=1, ，k Rakknn1 0,nk（1）（1）式和 MP 算法的不同在于， MP 算法是残差和前面的一个分量正交，而 OMP 算法是残差和前面的每个分量都正交。k+1 步分解为：
