sklearn学习笔记——正交匹配追踪算法OMP

正交匹配追踪算法OMP（Orthogonal Matching Pursuit）

1、MP算法(匹配追踪算法)

作为对信号进行稀疏分解的方法之一，将信号在完备字典库上进行分解。

MP算法的基本思想：

从字典矩阵D（也称为过完备原子库中），选择一个与信号 y 最匹配的原子(也就是某列)，构建一个稀疏逼近，并求出信号残差，然后继续选择与信号残差最匹配的原子，反复迭代，信号y可以由这些原子来线性和，再加上最后的残差值来表示。很显然，如果残差值在可以忽略的范围内，则信号y就是这些原子的线性组合。

如果选择与信号y最匹配的原子？如何构建稀疏逼近并求残差？如何进行迭代？

将信号投影到列向量，分为垂直投影分量和残值两部分

MP算法的缺点：

如上所述，如果信号(残值)在已选择的原子进行垂直投影是非正交性的，这会使得每次迭代的结果并不少最优的而是次最优的，收敛需要很多次迭代

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

【1】https://www.cnblogs.com/AndyJee/p/5047174.html    浅谈压缩感知（九）：正交匹配追踪算法OMP