By-SanfordZhu

SAMP提出了一种不需要输入稀疏度K的算法，通过设置步长（很大程度影响速度、小程度影响精度）和合适的停止条件（很大程度影响精度）来进行稀疏度的估计和支撑集的填充。

1.去噪SAMP

在SAMP算法后加入了一个去噪模块，去噪原则参考第一跳变点原理，求出相邻稀疏的差值diff小于max(theta)/2^4的，并置为0

创新点分析：由于SAMP重构出的信号不是严格稀疏的，并且会有一定的误差。但是如果处理的是严格稀疏信号，那么实际中信号的稀疏度是确定的，所以通过某种准则，将噪点直接置0，可小幅度提升重构精度。具体的去噪准则根据信号类型可进行修改调整。

文献：压缩感知框架下的信号重构算法研究

2.变步长自适应匹配追踪算法--VssAMP算法

当K未知的时候，算法需要设计合适的停止迭代条件以代替K，并达到较好的重建效果。通过步长s逐步逼近K进行重建是一个较好的想法。

实验发现：当支撑集大小不断增加但又没达到K时，相邻两个阶段中重建信号的能量差是不断减少的。可以作为迭代停止的条件。

相邻重建信号的能量差在最初的阶段中下降很快，之后下降幅度减小，最后基本上稳定在某一范围内，这说明重建出的信号能量趋于稳定，基本可以视为重建完成，为算法停止迭代条件提供了保证。

创新点分析：提出双重阈值策略（阈值来控制步长），通过“大步长快速接近，小步长逐步逼近”的思想来进行重构。

文献：基于压缩感知的匹配追踪重建算法研究（硕士论文+光学学报）

3.SASP

主要贡献：提出了一种新的预估稀疏度的办法，如下图

创新点分析：通过定理对稀疏度进行了预估，同时结合弱选择+子空间回溯两种方式对原子进行选择和筛选。

文献：一种压缩采样中的稀疏度自适应子空间追踪算法

4.MSAMP

分析了SAMP弊端：

各个阶段增加的步长step为常数，而最终size的大小就被认为是稀疏度K的大小。显然step取值较大的时候，阶段迭代步数少，算法效率较高，但是对稀疏K的估计精度显然也会降低；而当step取值较小时，对稀疏度估计精度较高，但是迭代阶段数急剧增加，导致算法执行效率不高。其次该算法直接以初始阶段的步长step作为初值，也不利于算法效率的提高。理论分析和仿真实验均表明，SAMP的重构精度和效率受到阶段步长step和初始稀疏度估计值的限制。

创新点分析：将初始稀疏度估计和变步长思想结合，首先预估出一个K0(K0＜K)作为初始支撑集的长度，以免进行过度的估计，然后采用结合2中的双阈值策略进行变步长重构

文献：一种改进的稀疏度自适应匹配追踪算法

5.RIOMP

由于稀疏度K的设置问题，K设置过小，重构精度不够，K设置过大，残差会提前饱和，需要一个准则来限定迭代次数，以减少迭代时间。

创新点分析：算法比较了新的残差（回溯后的）和旧的残差（回溯前的）的差值，如果小于阈值，那么则认为迭代次数达到了饱和。

迭代和阈值，算法流程如下：

文献：A Reducing Iteration Orthogonal Matching Pursuit Algorithm for Compressive Sensing-2016

6.基于差分的稀疏度自适应：

针对SAMP算法以及VssAMP算法中重构效果对初始步长的依赖性，提出了一种基于差分的原子选择策略

本文通过大量实验发现：测量矩阵与残差的内积所得的相关系数经过归一化后得到的结果在一些位置变化较为明显。我们试图找到这些跳变点然后选择该点前面的原子作为支撑集。算是弱选择策略的改进版。

创新点分析:算法利用信号与测量矩阵之间相关系数的变化特性，不仅克服了SAMP算法和VssAMP算法中对初始步长的要求，能够实现对稀疏度的自适应匹配，而且重构效果较好。

文献：基于差分的稀疏度自适应重构算法

7.Fast sparsity adaptive matching pursuit algorithm

创新点分析：

1.提出了一种新的原子选择方式，通过非线性的增长来代替掉线性的增加。在迭代过程中逐渐减小初始的大步长，直到所选原子的数目精确的逼近信号的稀疏性。

2.为了防止过多的选择原子，引入了自适应调整步长策略，根据前后残差的变化情况，调整步长的大小，以获得较高的重建精度。

可借鉴的地方：

1.初始步长的设定，为arctan(S)，S为设定的步长，这样保证了初始步长为一个较小的值

2.当前残差大于上次残差的时候采取的策略：进行步长的调整

3.加入了迭代次数的比较

文献：Fast sparsity adaptive matching pursuit algorithm for large-scale image reconstruction

8.BAOMP

创新点分析：将阈值选择策略引入到回溯的过程中，实现双重阈值的原子选择和筛选。

算法流程如下：

文献：Backtracking-Based Matching Pursuit Method for Sparse Signal Reconstruction

9.FAST--SAMMP算法

创新点分析：

在MMP原本的搜索策略上加入了回溯策略，其中与传统回溯不同的是当前迭代求出的新集合是基于最开始的残差求出的，而以往的新集合是基于当前的残差求出的。

文献：Fast sparsity adaptive multipath matching pursuit for compressed sensing problems