匹配追踪MP和正交匹配追踪OMP

近期看了一些匹配追踪MP和正交匹配追踪OMP的相关论文和博文，现在将自己的理解简记于此，仅供参考。

1 算法流程

$$模型：y=Ax$$ $$初始化：r=y，{\Omega }_n=0$$	MP	OMP
1. 求相关度（内积）	$$n=\arg \underset{n=1,2,3???}{\max }<A(:,n),r>$$	$$n=\arg \underset{n=1,2,3???}{\max }<A(:,n),r>$$ $${\Omega }_n={\Omega }_n\cup n$$
2. 估计x	$$\widehat{x_n}=<A(:,n),r>$$	$$\widehat{x(:,{\Omega }_n)}=<A^{?}(:,{\Omega }_n),r>$$
3. 更新残差	$$r=y?A(:,n)?\widehat{x_n}$$	$$r=y?A(:,{\Omega }_n)?\widehat{x(:,{\Omega }_n)}=A?\hat{x}$$

第一步：MP和OMP求解相同。

第二步：MP将最大的内积直接作为估计得到的x，A中仅包含当前被选择的列向量（原子）；而OMP通过最小二乘法求解，A中包含所有已被选择的列向量。（两者都是一种近似，和投影相关，内积的几何意义是投影，最小二乘也一样，下边几何图更容易明白）。

第三步：MP根据当前选择的向量更新残差，仅能保证残差与当前列向量正交，后续选择可能重复操作，收敛速度慢；而OMP根据所有被选择过的列向量，可以保证残差与所有被选择过的列向量正交，加速收敛。

2 几何意义

第一副图是MP的几何意义
y = Ax，无法求解，那么就来求解将y近似为p的p = Ax。其中内积等于投影的长度（A中列向量都是归一化的），具体理解可以根据图下方的两行公式，这里就不在重复书写了。

第二副图是OMP的几何意义
y同样是近似为投影p，只是这个投影是y投影到a1和a3所在的面上，而非单个向量。后边的求解也正好对应最小二乘法的过程，详情可参考：一文让你彻底搞懂最小二乘法（超详细推导）

其他MP和OMP相关的博文就不放了，知乎和CSDN搜索关键词会有很多，需要深入学习的话可以多参考一些，会发现大佬们各自不同的见解，非常值得学习。

本人对相关研究尚浅，可能有错误的地方，烦请指点。

2023.12.28