1 基本概念
1.1 定义与名称
正交匹配追踪，英文为 Orthogonal Matching Pursuit，通常缩写为 OMP，是一种用于稀疏表示与信号重构的迭代式贪婪算法。它从给定字典中逐步挑选与观测信号最匹配的原子，并在每次选择后对已选集合进行正交化处理，以重新估计系数。
“正交”一词强调的是每轮更新后，当前残差与已选原子张成的空间保持正交关系，从而避免早期选择带来的误差不断积累。该方法既可视作匹配追踪的改进版本，也可视作带有逐步最小二乘重估的稀疏近似策略。
1.2 核心思想
OMP 的核心思想可以概括为“选一个、算一次、改一次”。算法先从字典中找出与当前残差相关性最高的原子，再将这些已选原子一起用于最小二乘拟合，得到新的系数估计。随后根据拟合结果更新残差，并进入下一轮迭代。
这种机制的关键在于，后续步骤不是简单叠加前一步的结果，而是不断回看整个已选集合，重新修正系数。因此，OMP 往往比普通的逐项匹配方法更稳定，重构误差也更容易下降。
1.3 适用问题类型
OMP 适用于具有稀疏结构、低维表示需求或可解释特征筛选需求的问题。其典型场景包括用少量基向量表示信号、从观测数据恢复原始信号，以及在高维数据中寻找最具代表性的变量。
1.3.1 稀疏表示问题
在稀疏表示中，目标是用尽可能少的字典原子来表达一个样本。OMP 通过逐步选择少量原子，使样本获得近似表示，因而常用于图像块、语音片段或其他高维观测的稀疏编码。
1.3.2 信号重构问题
当信号只被部分采样，或受到压缩测量时，OMP 可借助稀疏先验恢复原信号。其思路是从测量值反推少量非零系数，再据此重建完整信号。
1.3.3 特征选择问题
在机器学习中，OMP 也可用于从大量候选特征中挑选少数关键变量。由于每轮都依据当前残差选择最有帮助的特征，因此结果通常具有较强的可解释性。
2 算法原理
2.1 字典与观测模型
OMP 一般建立在“观测向量可由字典线性组合近似”这一模型上。字典由多个原子组成，每个原子可理解为一个基向量；观测信号则是这些原子的稀疏线性组合，外加一定误差。
在压缩感知场景中，字典常由测量矩阵与稀疏基共同构成；在特征选择中，字典则可直接对应候选变量构成的设计矩阵。只要模型满足稀疏性假设，OMP 就能发挥作用。
2.2 残差与相关性
残差表示当前近似值与观测值之间的差异，是判断下一步该选哪一个原子的依据。算法会计算残差与每个候选原子的内积或相关系数，相关性越高，说明该原子越可能解释当前未拟合部分。
由于残差在每轮迭代中都会变化，相关性也会随之更新。因此，OMP 并不是一次性排序，而是动态地重新评估所有候选项。
2.3 原子选择机制
原子选择机制遵循局部最优原则：每轮选取与当前残差最相关的原子，而不是同时搜索全局最优组合。这样的做法大幅降低了计算复杂度，使算法在实践中更易实现。
不过，这种贪婪选择也意味着算法依赖前几步的判断质量。如果初始选择偏差较大，后续步骤虽然能够修正一部分误差，但未必完全恢复最优解。
2.4 正交投影与最小二乘更新
选择新原子后，OMP 会把当前观测向量投影到已选原子的张成空间上，重新求解一组最小二乘系数。这个过程使当前近似在已选集合上达到最佳拟合。
与只对新原子单独更新不同，OMP 会同时考虑全部已选原子，因此投影结果更全面，残差也更小。正是这一步“整体重估”构成了它与普通匹配追踪的重要区别。
2.4.1 支撑集更新
支撑集指当前被选中的原子索引集合。每次迭代后，新的原子会被加入支撑集，随后算法仅在该集合对应的子空间内重新求解系数。
支撑集的增长通常是单调的，即不会主动删除已选原子。也正因为如此，OMP 常被看作一种“前向选择”型稀疏算法。
2.4.2 系数重估
系数重估通过最小二乘方式完成，其目标是让已选原子对观测的拟合误差最小。重估会改变所有已选原子的权重，而不仅是新加入原子的权重。
这种更新方式可以纠正早期系数估计的偏差，使得模型随着迭代逐步逼近真实稀疏表示。
2.5 迭代终止条件
OMP 的迭代通常在以下几种条件下停止：达到预设稀疏度上限、残差低于阈值、相关性不足以继续提升，或者达到最大迭代次数。实际应用中，终止条件往往由精度要求与计算预算共同决定。
3 算法流程
3.1 初始化
初始化时，通常将残差设为观测向量本身，支撑集置为空，系数向量初始化为零。此时算法尚未选取任何原子，所有候选项都处于同一起点。
3.2 相关性计算
算法计算当前残差与字典中各原子的相关程度，常用内积或标准化后的相关系数来衡量。该步骤用于判断哪一个原子最能解释当前误差。
3.3 原子选择
从所有候选原子中选出相关性最大的一个，并将其加入已选集合。若字典列未归一化，通常需先进行规范化，以避免长度差异影响选择结果。
3.4 支撑集扩展
新原子被加入支撑集后，算法将利用更新后的集合重新求解表示问题。支撑集扩展意味着模型复杂度略有增加，但也带来更高的拟合能力。
3.5 正交求解
在当前支撑集对应的子字典上执行最小二乘求解，得到所有已选原子的系数估计。此时的求解结果是对当前支撑集下最优拟合的近似。
3.6 残差更新
根据新的系数计算重构值，再从观测向量中减去该重构值，得到新的残差。更新后的残差通常比前一轮更小，并且与已选子空间正交。
3.7 输出结果
迭代结束后，算法输出支撑集、系数估计以及重构信号。若用于特征选择，则输出被选中的特征索引；若用于信号恢复，则输出重建后的信号向量。
4 数学表达
4.1 矩阵形式表示
OMP 通常写成一个稀疏线性表示问题：给定观测向量 y 与字典矩阵 D，寻找稀疏系数 x，使得 y 约等于 Dx。这里 D 的列向量即为原子。
4.2 目标函数
其典型目标可表述为在稀疏约束下最小化重构误差，即在尽量少的非零项下，使 y 与 Dx 的差距尽可能小。由于直接求解组合优化问题较困难，OMP 采用逐步近似的方式处理。
4.3 约束条件
约束通常体现为非零系数个数不超过某个上限，或残差范数不超过预设阈值。不同任务会采用不同的停止规则，从而形成对应的近似解。
4.4 投影算子
投影算子用于描述信号向已选子空间的正交投影。每轮重估本质上就是将观测信号投影到支撑集生成的线性空间中，以获得当前最优系数。
4.5 误差度量
误差通常采用残差的二范数来衡量，也可以使用相对误差、重构信噪比或其他任务相关指标。对于分类任务，还可能进一步观察特征子集带来的性能提升。
5 性质与特点
5.1 贪婪性
OMP 具有明显的贪婪特征，即每一步只追求局部最优选择。这使它在实现上简单直接，但也决定了它并不总能得到全局最优的稀疏解。
5.2 稀疏性保证
在适当条件下，OMP 可以恢复真实的稀疏表示，尤其当字典满足一定的低相关性要求时更为有效。其结果通常具有较强稀疏性，非零项数量较少。
5.3 收敛表现
OMP 一般会在有限步内终止，因为每轮迭代至少增加一个原子，并且支撑集大小受限。随着迭代推进，残差通常单调下降，但下降速度取决于字典质量和噪声水平。
5.4 计算复杂度
OMP 的主要开销来自相关性计算与最小二乘更新。若字典较大，反复计算内积与求解线性系统会带来一定成本，但整体上仍常被认为比全局优化方法更高效。
5.5 稳定性与鲁棒性
OMP 对噪声和字典相干性较为敏感，但在一定噪声范围内仍可保持较好的近似性能。若数据确实具有明显稀疏结构，其稳定性通常足以满足工程需求。
6 与相关算法的比较
6.1 与匹配追踪的区别
匹配追踪在每轮加入新原子后，往往只更新当前项的贡献，而不对所有已选原子重新联合求解。OMP 则会对整个已选集合做正交最小二乘重估，因此通常能获得更高精度。
6.2 与基础追踪类方法的关系
OMP 与一类基于逐步选择的追踪算法关系密切，都强调按残差驱动的迭代搜索。不同之处在于，OMP 通过正交投影强化了“整体修正”的能力。
6.3 与LASSO的比较
LASSO 属于凸优化方法，借助正则项促使系数稀疏；OMP 则是离散贪婪算法，通过逐步挑选特征获得稀疏解。前者更偏向全局优化，后者更强调速度和实现简洁性。
6.4 与最小二乘法的联系
OMP 中的系数重估环节本质上就是最小二乘求解，只不过它是在逐步扩展的支撑集上进行。可以说，OMP 将最小二乘作为局部子问题嵌入到稀疏选择流程中。
6.5 与其他稀疏重构算法的对照
与 Basis Pursuit、硬阈值迭代等方法相比，OMP 更容易实现，且每一步都有清晰的几何意义。代价是它对初始选择和字典结构更依赖，且不一定适合高度相关的特征集。
7 理论分析
7.1 唯一性条件
OMP 能否恢复唯一解，通常取决于字典列之间的相关性以及稀疏度是否足够低。若字典满足较强的可分离性，且真实非零项数量较少，则恢复结果更可靠。
7.2 重构精度分析
重构精度与字典性质、噪声大小和迭代步数密切相关。通常情况下，支撑集越接近真实集合，重构误差越小；若过早停止，误差则可能保留在较高水平。
7.3 误差传播
由于 OMP 是逐步构建解的，前期选择偏差可能影响后续的相关性计算，形成一定误差传播。不过，正交重估机制能够部分抵消这种影响，使误差不会像简单累加那样迅速放大。
7.4 一致性与可恢复性
一致性指算法在理想条件下是否能够稳定恢复同一稀疏结构，可恢复性则关注在给定测量和字典条件下是否能找回原信号。OMP 在满足适当条件时，二者通常都具有较好表现。
7.5 字典性质影响
字典的互相关程度、归一化程度以及列空间结构，都会显著影响 OMP 的表现。若字典列过于相似，算法更难准确区分原子，错误选择的概率也会升高。
8 应用领域
8.1 压缩感知
在压缩感知中，OMP 常用于从少量测量值恢复稀疏信号。它因实现直接、速度较快而成为经典重构方法之一。
8.2 图像去噪与重建
OMP 可应用于图像块稀疏表示，通过从字典中选出少量原子来近似图像局部结构。该思路常见于去噪、超分辨率和缺失像素修复等任务。
8.3 信号检测与分离
在多源信号混合场景中，OMP 可帮助识别某些显著成分，并将其从背景或干扰中分离出来。它特别适合结构较稀疏、峰值较明显的信号。
8.4 特征提取与分类
在分类任务中，OMP 可用于从大量候选变量中筛选少数判别性较强的特征。选出的特征通常具有较强解释性，也便于后续模型分析。
8.5 语音与通信处理
OMP 在语音编码、稀疏声源建模和通信信道估计中均有应用。由于这些任务往往具有稀疏结构或低秩近似特征，OMP 能提供较有竞争力的近似结果。
9 实现与工程实践
9.1 参数设置
实际实现中，最关键的参数包括最大稀疏度、残差阈值、最大迭代次数和停止精度。参数设得过松会降低重构质量，设得过严则会增加计算量。
9.2 字典构建
字典可由预定义基函数、训练样本或领域知识构造。工程上通常会对字典列做归一化处理，以保证相关性比较更公平。
9.3 数值求解方法
最小二乘子问题可采用 QR 分解、Cholesky 分解或其他稳定的线性代数方法求解。对于高维场景，数值稳定性往往比单纯的计算速度更重要。
9.4 加速策略
为了提升效率，常会在相关性计算、线性求解和矩阵更新上做优化。特别是在大规模字典或批量样本处理时，加速策略非常关键。
9.4.1 预计算矩阵
若字典固定，可预先计算部分内积或 Gram 矩阵，以减少迭代过程中的重复运算。该方法适用于存储空间允许的情况。
9.4.2 增量更新
每次只对新增原子带来的变化进行局部更新，而非每轮完整重算所有量，可以显著降低开销。增量式处理在支撑集较小但迭代次数较多时尤其有效。
9.4.3 并行化实现
相关性计算天然适合并行化，尤其是面对大规模候选原子时。借助多线程或图形处理单元，可进一步缩短运行时间。
9.5 常见实现误区
常见误区包括未对字典列归一化、停止条件设置不合理、数值求解不稳定，以及忽视噪声对残差阈值的影响。另一个常见问题是支撑集过大，导致模型出现过拟合或解释冗余。
10 扩展与变体
10.1 正则化正交匹配追踪
该变体在原有选择机制上加入正则化思想，以增强噪声环境下的稳定性，并缓解病态字典带来的数值问题。
10.2 分组正交匹配追踪
分组版本将原子按组选择，而不是逐个挑选。它适用于特征天然成组出现的场景，例如某些结构化信号或相关变量集合。
10.3 批量正交匹配追踪
批量 OMP 用于同时处理多个样本或多列观测矩阵，能够复用部分计算结果。相比逐个样本独立运行，它在工程上更高效。
10.4 多测量向量版本
多测量向量版本面向多个相关观测共享同一稀疏支撑集的情形。该方法常用于联合恢复问题，能利用样本间的共同结构提升精度。
10.5 结构化稀疏版本
结构化稀疏 OMP 会将先验结构纳入选择过程，例如块状、树状或层次化稀疏模式。这样可使恢复结果更符合实际数据的组织规律。
11 相关概念
11.1 稀疏表示
稀疏表示是指用少量非零系数来表达一个信号或样本的方式，是 OMP 的理论基础之一。
11.2 字典学习
字典学习是从数据中自动学习适合稀疏表示的原子集合的方法，常与 OMP 配合使用。
11.3 压缩感知理论
压缩感知研究如何利用稀疏性从少量测量中恢复信号，OMP 是其经典求解工具之一。
11.4 贪婪算法
贪婪算法是一类逐步做局部最优选择的算法范式，OMP 正是其中具有代表性的实例。
11.5 最小二乘估计
最小二乘估计是通过最小化平方误差来确定参数的方法，OMP 的每轮系数重估都建立在这一思想之上。