Sparse Coding一些算法思想(MP/OMP/BP)

MP(Matching Pursuits)

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

2.如何选择与信号y最匹配的原子？

答：计算信号y与字典矩阵（或者残差矩阵）中每列的内积，选择绝对值最大的一个原子，它就是与信号 y 在本次迭代运算中最匹配的。

r0=y;

思考：为什么pi*<ri-1,pi>???不应该求投影向量pi*<ri-1,pi>/|Pi|^2吗？

OMP(Orthogonal Matching Pursuits)

1.基本思想： MP算法中，信号(残值)在已选择的原子进行垂直投影是非正交性的，这会使得每次迭代的结果并不少最优的而是次最优的，收敛需要很多次迭代。OMP算法的改进之处在于：在分解的每一步对所选择的全部原子进行正交化处理，这使得在精度要求相同的情况下，OMP算法的收敛速度更快。

2.如何正交化处理：

OMP与MP算法不同之处，它的残值与前面每个分量正交，这就是为什么这个算法多了一个正交的原因，MP中仅与最近选出的的那一项正交。

3.算法步骤：

BP(Basis Pursuits)

1.基本思想：将优化问题

因为a不进行非负约束，而u>0,v>0,u和v大小不限；

PS：目标函数绝对值去掉求解：

所以，优化问题变为：

解为：

缺点:BP这类优化算法比MP，OMP这类贪婪算法,计算复杂度高,重构时间长.

FOCUSS(focal underdetermined system solver)

实质上是一种加权最小范数最小二乘法。FOCUSS算法利用后验知识迭代加权，使从最小范数获得的解的能量逐步集中。采用逐步迭代的方法，由前一次计算求得的迭代数据产生新的加权函数，利用新的加权函数求得的迭代数据使得能量较上一步更为集中。

参考文献

MP算法和OMP算法及其思想

匹配追踪算法（MP）简介

压缩感知重构算法之基追踪(Basis Pursuit, BP)