压缩感知是最近几年新兴起的一种采样压缩技术,它打破了传统的奈奎斯特采样定理的限制,对信号采样的同时进行压缩,已经取得了很大的研究进展。压缩感知主要由两部分组成,一是信号的采样,另一个则是重建恢复。前者主要是对高维的稀疏信号或可压缩信号通过测量矩阵获取低维测量值的过程,后者是利用这些低维的采样数据尽最大可能将原始数据还原。而重建算法作为压缩感知关键性的一步,决定着恢复信号的质量。本文是在充分研究经典贪婪算法的基础上,综合分析各种算法的优点和缺点,针对其缺点进行改进,提出几种性能更优的重构算法。文章首先对已有的贪婪匹配追踪算法进行介绍,分为两个方面,一是针对两种自下而上匹配追踪算法进行分析研究,二是针对两种自上而下匹配追踪算法进行介绍。详细的对各种算法进行说明,分别分析其优缺点,并赋予相应的一维,二维信号重建效果图。其次,本文在分析和总结正则化正交匹配追踪和正则化自适应匹配追踪算法的基础上,提出一种新方法,即回溯正则化自适应匹配追踪算法BRAMP,该算法能够在未知信号稀疏度的情况下很好地对原始信号进行重构。该改进算法通过设置模糊阈值自适应的选取一些原子,然后继承正则化筛选原则,对原子进行二次选取,最后则采用回溯的方式删掉个别错误的原子,依次迭代逐步扩大支撑集直至逼近稀疏度为止。相比于正则化自适应匹配追踪算法,该算法加入回溯过程后,重建效果大为提升,实验结果也证实了这一点。最后,本文在充分比较两种正交重建算法之后,提出一种新的压缩采样重建算法——广义正交最小二乘算法gOLS,该算法充分结合了广义正交匹配追踪算法的思想,利用残差值来一次选取多个优质原子,使得重构精度和复杂度均有所改善。由于每次迭代需要多次将所选原子集进行正交投影,导致算法的计算复杂度较高,因此本文利用投影定理和三角法则,对原子选取步骤进行等价替换,将原始比较残差值的过程转变为求相关性的大小,使得每次迭代只需要进行一次正交投影即可完成原子筛选,能够保证在维持原有重建质量的前提下,实现计算复杂度的大为降低。