概述
贪婪算法是一种搜索算法，基于局部的最优解，对于稀疏性较差或者存在噪声的信号重构性能较差。
模型
解决这样的一个问题：
x x x为稀疏度为 K K K的一个向量，观测矩阵为 A A A，观测向量为 b b b，同时伴有加性噪声 n n n，即： b = A x + n b=Ax+n b=Ax+n。期望从 b b b中恢复 x x x。也就是说在满足一定条件的情况下，用较少的观测值重构较长的信号。
称 A A A的列向量为原子（注意算法编写中应归一化）。
收敛条件：通常是重构向量不再变化或者残差较小或者稀疏度满足要求。
MP算法
MP算法全称为matching pursuit。每一步都选择对当前残差贡献最大的原子作为投影方向，计算投影长度，不断迭代，直到满足预设的收敛条件。
这里有一个问题。MP算法在投影方向的选择过程中，因为原子之间并非正交，而残差只与当前投影方向正交，所以可能选择之前已经选择过的方向，这会导致迭代的收敛速度较慢。
OMP算法
OMP算法全称为orthoganal matching pursuit。对于MP算法中迭代慢的问题，OMP做了改进。具体改进的地方在于系数的计算。在OMP算法中，每一步都选择对当前残差贡献最大的原子，向前面步骤中所有已选择的原子构成的子空间做投影，计算投影系数。这样可以保证每次迭代的残差和前面选择的原子均正交，也就是每次选择的都是一个新的方向，加快了算法收敛的速度。
最后
以上就是甜美冬天为你收集整理的贪婪算法（MP\OMP）模型MP算法OMP算法的全部内容，希望文章能够帮你解决贪婪算法（MP\OMP）模型MP算法OMP算法所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复