算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。
压缩感知的重构算法主要分为三大类：
1.组合算法 2.贪婪算法 3.凸松弛算法
三种算法对比分析如下：
| 算法类别 | 定义 | 优缺点 | 具体算法 |
| 贪婪算法 | 贪婪算法首先选取合适的原子，再逐步进行递增，进而逼近信号矢量，利用这种过程进行 | 计算量和精度的要求居中，也是三种重构算法中应用最大的一种 | (1)匹配追踪算法 (2)正交匹配追踪算法 (3)分段正交匹配追踪算法 (4)正则化正交匹配追踪算法 (5)稀疏自适应匹配追踪算法 |
| 组合算法 | 先是对信号进行结构采样，然后再通过对采样的数据进行分组测试，最后完成信号的重构 | 需要观测的样本数目比较多但运算的效率最高 | (1) 傅里叶采样 (2) 链式追踪算法 (3) HHS追踪算法 |
| 凸松弛算法 | 法，它将非凸问题转化为凸问题进行求解，即l0范数转化成l1范数并采用线性规划来求解 | 计算量大但是需要观测的数量少重构的时候精度高 | (1)基追踪算法 (2)最小全变差算法 (3)内点法 (4)梯度投影算法 (5)凸集交替投影算法 |
本篇主要介绍正交匹配追踪算法（OMP）
1、OMP算法的原理
OMP算法是在MP算法的基础上进行改进的，沿用了MP算法的重构的思想，但是又对MP算法进行了改进，使得算法的效率更高，应用更加的广泛。
MP算法的信号分解中步骤中介绍：，这说明信号在已经选择的原子上的投影（等是右边第一项）是非正交的，还存在着残差，也就是说每次迭代的过程是次最优的，不是最优解，要想最终的迭代收敛，需要的迭代次数较多。OMP算法就是根据MP算法的不足之处加以改进，把所选择的原子首先通过Schimidt正交化处理，使得在达到迭代条件的时候需要的迭代次数较MP算法少，但是正交化的过程中会增加计算量。
OMP算法正交化原理：
2、OMP算法的流程图
算法流程图如下：
3、OMP算法的算法步骤
算法步骤如下：
4、OMP算法的信号重构
本节对OMP算法进行重构，采用一维离散信号和二维lena信号对其进行信号重构，来观察OMP算法的重构功能。
（1）一维离散信号的OMP算法仿真
本次仿真使用matlab随机生成的一维离散信号，稀疏度k=15,信号长度N=512，观测向量的长度M=128，那么采样率M/N=0.25，其中的观测矩阵是高斯随机矩阵。采用OMP算法对一维信号进行重构，重构图如1：
图1：OMP算法重构一维信号
通过上面的重构可以得出，OMP算法对一维信号有很好的重构作用。
（2）二维lena图像的OMP算法重构
OMP算法对二维信号进行重构，在这里我们采取和MP算法二维信号重构的方法，也是先采取离散余弦变换（dct）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct），这样就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256X256的Lena的二维图像，M=180，N=256，稀疏度k=40，M/N=0.7，观测矩阵是高斯随机矩阵，采用OMP算法对二维图像进行重构，重构效果如图：
文章出处登录后可见！
