目前,常用的重构算法主要包含两大类,一类是贪婪迭代匹配追踪系列算法,代表算法有匹配追踪和正交匹配追踪(OMP)算法。另一类是凸优化算法,如内点法、投影梯度法等。凸优化算法的主要特征是重构误差较小,效果好,但是,该类方法因其时间复杂度较大,因此在解决大规模问题时实用性不是很好。相对而言,贪婪类的迭代算法计算复杂度低而且容易实现,而且,重构效果大多数情况下可以接受,因而应用范围要更广泛一些。后来陆续出现了很多关于OMP算法的一系列改进的算法,主要包括正则化正交匹配追踪(ROMP)、压缩采样匹配追踪(CoSaMP)【8】。
2.2 压缩感知的基本原理
2.2.1 压缩感知基本流程
总的说来,压缩感知方法的处理流程可简要描述为:基于待处理信号在某个基上的稀疏性或可压缩性,设计合理的测量矩阵,获得远小于信号维数但包含足够信号特征信息的采样,通过非线性优化算法重构信号。
在传统理论的指导下,信号X的编解码过程如图2-1所示。编码端首先获得X的N店采样值经变换后只保留其中K个最大的投影系数并对它们的幅度和位置编码,最后将编得的码值进行存储或者传输。
解压缩仅仅是编码过程的逆变换。实际上,采样得到的大部分数据都是不重要的,即K值很小,但由于奈奎斯特采样定理的限制,采样点数N可能会非常大,采样后的压缩是造成资源浪费的根本所在。