压缩感知的重构算法算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。
因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。
压缩感知的重构算法主要分为三大类：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 算法的原理x y Φ=，其中测量矩阵Φ又称为过完备字典，每一列被称为一个原子，则测量矩阵中有n 个原子，而y 的长度为m ，原子的个数远远大于信号的长度，即m<<n ，因此测量矩阵又称为过完备字典。
信号y 在测量矩阵上进行分解，Φ可以用{ϕϕn ...1}来表示，单位向量长度为1，要对过完备字典的原子进行归一化处理。
MP 算法的基本思想：从观测矩阵（过完备字典）中选择一个与信号y 相关性最大（最匹配）的原子，也就是观测矩阵中的一列，构建信号的稀疏逼近，求出信号的残差，重复上面的操作，继续选择与信号残差最匹配的一个原子，如此反复迭代直到达到迭代次数，最后信号y 就可以表示为这些原子的线性组合。
MP 进行稀疏分解的步骤[1][2]：从观测矩阵中选择一个与信号y 最匹配的原子，也就是内积最大的一个原子，即：|<y,ϕΓ0>|=sup ),...1(n i ∈|<y,ϕi >| （1） 其中，Γ0表示字典矩阵的列索引。
先将信号y 投影到向量 Φ∈Γϕ0上，信号y 也可以表示为：R y y 100,+Γ>Γ=<ϕϕ (2)(2)式等号右边的第一项为观测矩阵中最匹配原子ϕΓ0的垂直投影分量，等式右边的第二项R 1是y 通过ϕΓ0分解后的残差，且与y 正交。
（2）式可以写为：|||||,|||||10222R y y +Γ=><ϕ （3） 对残差R 1进行上面同样的分解，在第n 次迭代过程中：R R R n n n n n 1,++Γ>Γ=<ϕϕ （4） 因为R n 和ϕΓn 正交，则（4）式可以表示为：|||||,|||||1222R R R n n n n ++Γ=><ϕ （5） 最后，信号y 可以表示为：R y n i n i i i y 10,+=+Γ>Γ<=∑ϕϕ （6）因为最后的残差R n 1+正交于上次迭代产生的残差R n ，则最后的表达式为：|||||,|||||1222R y y n i n o i ++Γ=><∑=ϕ （7） 由（7）式可知，当残差R n 1+为零时，可以得到信号的精确分解。
定理1[3] 存在0>λ，使得一切对于0≥n 时，有||||||||21y n n R λ-+≤成立。
这样（7）式中，||||1R n +按照指数衰减的形式趋于零，也就是|,|||||202><∑Γ==ϕi y y n i 成立。
参考文献：[1] 曹离然.面向压缩感知的稀疏信号重建算法研究.[D].哈尔滨工业大学，2011.[2] Y .C.PATI.Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition.IEEE.1993:40-44[3] 韩红平.压缩感知中信号重构算法的研究.[D].南京邮电大学，2012.1.2 MP 算法的理论框图根据上面的MP 算法的原理，得出MP 算法的理论图[1]，这样更容易理解。
图1：MP算法框图参考文献：[1] 韩红平.压缩感知中信号重构算法的研究[D].南京邮电大学，20121.3 MP 算法的算法流程根据1.2中介绍的MP 算法的理论框图，现在写出MP 算法的算法流程[1][2]，这样让我们对MP 算法有一个更加清晰的理解。
输入：测量矩阵)(N M ⨯Φ，测量向量)1(⨯N y ，稀疏度k 输出：重构信号∧x（1）：初始化余量y r =0，迭代次数n=0 1；（2）：计算余量与测量矩阵的每一列的内积r g n T n 1-Φ=；共有N 个内积数值。
(3)：找出N 个g n 中的绝对值最大的元素)(k g n ，k 为对应的最大内积的列号。
（4）：计算信号的近似解][][][1k k k g x x n n n +=-；（5）：更新余量ϕk n n n k g r r ⋅-=-][1；（6）：若满足迭代条件，则n=n+1，x n x =∧，若不满足迭代条件则返回步骤（2）；迭代次数为稀疏度的2倍。
参考文献：[1] Linfeng Du,Rui Wang. Analysis on Greedy Reconstruction Algorithms Based on Compressed Sensing.[J].IEEE 2012:783-789[2] 文首先.压缩感知匹配追踪算法的研究.[D].20131.4 MP 算法的信号重构本节分别通过对一维离散信号，二维Lena 为例，进行MP 算法的信号重构。
（1）一维离散信号的MP算法仿真本次仿真使用matlab随机生成的一维离散信号，稀疏度k=23,信号长度N=256，观测向量的长度M=80，那么采样率M/N=0.3，其中的观测矩阵 是高斯随机矩阵。
采用MP算法对一维信号进行重构，重构图如1：图1：MP算法重构一维信号通过上面的重构可以得出，MP算法对一维信号有很好的重构效果。
（2）二维lena图像的MP算法重构我们上面的研究知道MP算法对一维信号有很好的重构作用，但是算法不只是要在一维信号中有好的重构功能，还要能很好的重构二维信号才可以，这样应用的范围才会更大。
我们知道压缩感知重构的是可压缩的稀疏信号，二维信号是不稀疏的，这就要在进行算法重构的时候进行一些处理，我们可以先采用离散余弦变换（dct）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct），这样就转化为了我们所需要的。
本次在matlab中的仿真，我们采用的是256256的Lena的二维图像，M=180，N=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 算法进行了改进，使得算法的效率更高，应用更加的广泛。
MP 算法的信号分解中步骤中介绍：R y y 100,+Γ>Γ=<ϕϕ，这说明信号在已经选择的原子上的投影（等是右边第一项）是非正交的，还存在着残差，也就是说每次迭代的过程是次最优的，不是最优解，要想最终的迭代收敛，需要的迭代次数较多。
OMP 算法就是根据MP 算法的不足之处加以改进，把所选择的原子首先通过Schimidt 正交化处理，使得在达到迭代条件的时候需要的迭代次数较MP 算法少，但是正交化的过程中会增加计算量。
在每一步中如何对选择的全部原子进行正交化处理呢？这是OMP 算法和MP 算法的不同之处。
下面介绍OMP 算法正交化原理[1]： 信号y 经k 步分解：R a k k n k n n y +Γ=∑=ϕ1且0,>=Γ<ϕnR k ，n=1,…，k （1） （1）式和MP 算法的不同在于，MP 算法是残差和前面的一个分量正交，而OMP 算法是残差和前面的每个分量都正交。
k+1步分解为：R a k k n k n n y 1111+++=+Γ=∑ϕ 且 0,1>=Γ<+ϕnR k n=1,…，k+1 （2） k+1阶减去k 阶：R R a a a kk k k k n k n k n k n -+Γ+Γ-++++=+∑111111)(ϕϕ （3） 要想对选择的全部原子进行正交化处理，要求（3）式等于零。
测量矩阵的原子不正交，为了说明（3）式等于零，下面引入一个辅助模型，模型表示的是ϕΓ+1k 对前k 个项ϕΓn（n=1，…，k ）的依赖，数学语言描述如下：r b k kn kn n n +Γ=Γ∑=+ϕϕ11且 <ϕΓnr k , > =0,n=1,…,k (4)ϕΓ+1k 在),...,(1ϕϕk上张成的正交投影，等式右边的第二项是残差，（4）式代入（3）式中：0)()(1111111=-++Γ+-++++++=∑R R r a b a a ak k k k k kn k k kn k nkn nϕ(5)如果（6）和（7）式成立，则（5）式必然成立，0111=+-+++b a a akn k k k n k n （6）0111=-++++R Rr a k k kk k (7)令a a k k k =++11，有：b a a akn k kn k n-=+1 n =1,…,k (8)01=-++R R r a k n k k n =1,…,k (9)（8）和（9）两式成立，以上就是OMP 算法进行正交化的过程。