2.3.4 原子选择算法
目前，贪婪追踪算法及变种算法种类很多，在信号稀疏化的原子选择算法中已得到成熟应用。本节以贪婪追踪算法中的匹配追踪（MP）算法和正交匹配追踪（OMP）算法为例，介绍原子选择的原理和基本流程。
原子选择算法需要在给定冗余字典的条件下，求解未知稀疏矢量x。矢量x需要确定两个部分——解的支撑集（非零值的位置）和支撑集上的非零值（非零值的具体大小）。贪婪追踪算法的求解聚焦于支撑集的确定，一旦确定了支撑集，x的非零值可以很容易地用简单最小二乘估计得到。贪婪算法中的“贪婪”主要体现在搜索过程中。为避免对解0空间进行费时的全面搜索，贪婪算法采用了一系列的单项更新来进行局部优化：从x0=0开始，通过每步保持一组有效的列不变、迭代构造包含k项的近似xk的方式来扩展该集合。为了逼近原始信号y，在当前有效列的基础上，每一步都选择能最大限度地减少l2残差的列，每增加一个新列后更新l2残差，直到残差低于某个设定的阈值时结束。
1. MP算法
匹配追踪的基本思想是，由于观测值可以看作感知矩阵中原子的线性组合，相比其余原子，参与线性叠加的原子与观测矢量之间的相关性更高。因此，可以找到相关度最大的原子，去除对应分量，再寻找相关性次大的原子，依次类推。
MP本质上是一种贪婪算法，流程可用算法2-4描述。
算法2-4 MP算法
输入：观测信号y，字典D∈ℝN×M。
输出：表示矢量
。
1）初始化：令迭代残差矢量r0=y，迭代次数i=1，稀疏矢量
。
2）循环直到满足停止条件：
3） 搜索和残差ri-1相关度最大的原子索引λi：
4） 计算稀疏矢量重构值：
5） 更新迭代残差：
6） 更新迭代次数：i=i+1，若i=T（预设迭代次数），迭代结束，进入步骤7，否则返回步骤2。
7）得到稀疏矢量
。
MP算法需要其迭代残差ri与当次所选原子dλi的正交性来保证算法收敛，即
但这无法保证ri与之前所选择的原子集合{dλ1，dλ2，…，dλi-1}的正交性，导致原子搜索常常陷入局部最优。这也是MP算法需要较多的迭代次数才能保证收敛的原因。
2. OMP算法
OMP算法通过递归对已选择原子集合进行正交化，有效克服了MP的不足。OMP算法的具体流程参见算法2-5。
算法2-5 OMP算法
输入：观测信号y，字典D∈ℝN×M。
输出：表示矢量
。
1）初始化：令迭代残差矢量r0=y，迭代次数i=1，稀疏矢量
，支撑集下标集Λ0=∅。
2）循环直到满足停止条件：
3） 搜索和残差ri-1相关度最大的原子索引λi：
4） 更新支撑集原子和下标集：
Λi=Λi-1∪{λi}
Θi=［Θi-1dλi］
5） 计算稀疏矢量重构值：
6） 更新迭代残差：
7） 更新迭代次数：i=i+1，若i=T（预设迭代次数），则迭代结束，进入步骤8，否则返回步骤2。
8）得到稀疏表示信号
。
比较算法2-4的步骤4与算法2-5的步骤5可知，OMP每次计算重构信号都对之前选出的所有原子进行了“回溯”，同时对之前入选原子进行同步检验，可以最大限度地保证重构的全局最优性。