目前，常用的重构算法主要包含两大类，一类是贪婪迭代匹配追踪系列算法，代表算法有匹配追踪和正交匹配追踪(OMP)算法。另一类是凸优化算法，如内点法、投影梯度法等。凸优化算法的主要特征是重构误差较小，效果好，但是，该类方法因其时间复杂度较大，因此在解决大规模问题时实用性不是很好。相对而言，贪婪类的迭代算法计算复杂度低而且容易实现，而且，重构效果大多数情况下可以接受，因而应用范围要更广泛一些。后来陆续出现了很多关于OMP算法的一系列改进的算法，主要包括正则化正交匹配追踪(ROMP)、压缩采样匹配追踪(CoSaMP)【8】。

2.2  压缩感知的基本原理

2.2.1  压缩感知基本流程

    总的说来，压缩感知方法的处理流程可简要描述为：基于待处理信号在某个基上的稀疏性或可压缩性，设计合理的测量矩阵，获得远小于信号维数但包含足够信号特征信息的采样，通过非线性优化算法重构信号。

    在传统理论的指导下，信号X的编解码过程如图2-1所示。编码端首先获得X的N店采样值经变换后只保留其中K个最大的投影系数并对它们的幅度和位置编码，最后将编得的码值进行存储或者传输。

    解压缩仅仅是编码过程的逆变换。实际上，采样得到的大部分数据都是不重要的，即K值很小，但由于奈奎斯特采样定理的限制，采样点数N可能会非常大，采样后的压缩是造成资源浪费的根本所在。