3.1 算法描述

OMP算法的改进之处在于：在分解的每一步对所选择的全部原子进行正交化处理，这使得在精度要求相同的情况下，OMP算法的收敛速度更快。

那么在每一步中如何对所选择的全部原子进行正交化处理呢？在正式描述OMP算法前，先看一点基础思想。

先看一个 k 阶模型，表示信号 f 经过 k 步分解后的情况，似乎很眼熟，但要注意它与MP算法不同之处，它的残值与前面每个分量正交，这就是为什么这个算法多了一个正交的原因，MP中仅与最近选出的的那一项正交。

(1)

k 1 阶模型如下：

(2)

应用 k 1阶模型减去k 阶模型，得到如下：

(3)

我们知道，字典矩阵D的原子是非正交的，引入一个辅助模型，它是表示对前k个项的依赖，描述如下：

(4)

和前面描述类似，在span(x1, ...xk)之一上的正交投影操作，后面的项是残值。这个关系用数学符号描述：

请注意，这里的 a 和 b 的上标表示第 k 步时的取值。

将(4)带入(3)中，有：

（5）

如果一下两个式子成立，(5)必然成立。

(6)

(7)

令，有

其中。

ak的值是由求法很简单，通过对(7)左右两边添加作内积消减得到：

后边的第二项因为它们正交，所以为0，所以可以得出ak的第一部分。对于，在（4）左右两边中与作内积，可以得到ak的第二部分。

对于(4)，可以求出，求的步骤请参见参考文件的计算细节部分。为什么这里不提，因为后面会介绍更简单的方法来计算。

3.2