稀疏分解中的MP与OMP算法
【给力追-女孩干货】【Ｑ/Ｑ:⒈０１б.x.９⒌２６】 MP：matching pursuit匹配追踪 OMP：正交匹配追踪
主要介绍MP与OMP算法的思想与流程，解释为什么需要引入正交？ 1）稀疏分解要解决的问题是在冗余字典A中选出k列，用这k列的线性组合近似表达待稀疏分解信号y，可以用表示为y=Aθ，求θ。?
2）压缩感知重构要解决的问题是事先存在一个θ和矩阵A，然后得到y=Aθ（压缩观测），现在是在已知y和A的情况下要重构θ。
上面各式中，A为M×N矩阵（MN，稀疏分解中为冗余字典，压缩感知中为传感矩阵A=ΦΨ，即测量矩阵Φ乘以稀疏矩阵Ψ），y为M×1的列向量（稀疏分解中为待稀疏分解信号，压缩感知中为观测向量），θ为N×1的列向量（稀疏分解中为待求分解系数，压缩感知中为信号x的在变换域Ψ的系数，x=Ψθ）。 所不同的是，在稀疏分解中θ是事先不存在的，我们要去求一个θ用Aθ近似表示y，求出的θ并不能说对与错；在压缩感知中，θ是事先存在的，只是现在不知道，我们要通过某种方法如OMP去把θ求出来，求出的θ应该等于原先的θ的，然后可求原信号x=Ψθ。
其实MP也好，改进后的OMP也罢，最初提出都是面向稀疏分解的，当时还没有压缩感知的概念，只是后来压缩感知提出后将其引入到了压缩感知重构中，因为前面也说了，其实他们的本质是一样的，都是已知y和A的情况下求y=Aθ中的θ。
1.冗余字典与稀疏表示?
作为对信号进行稀疏分解的方法之一，将信号在完备字典库上进行分解。即在字典中找到一组基来表示信号，而用一组特定基表达一个信号其实就是找到相应的一组展开系数。一组基表达信号的能力取决于信号的特性是否与基向量的特性相吻合。例如，光滑连续信号可以被傅里叶基稀疏的表达，但脉冲信号不行。再如，带有孤立不连续点的平滑信号可用小波基稀疏表达，但小波基在表达傅里叶频谱中有窄带高频支撑的信号时却是无效的。
现实世界中的信号经常包含有用单一基所不能表达的特征。对于这些信号，你或许希望可以选择来自不同基的向量（如用小波基和傅里叶基来联合表达一个信号）。因为你想保证你可以表达一个信号空间的所有信号向量，所以由所有可选向量组成的字典应该能够张成这个信号空间。然而由于这组字典中的向量来自不同的基，它们可能不是线性独立的，会造成用这组字典做信号表达时系数不唯一。然而如果创建一组冗余字典，你就可以把你的信号展开在一组可以适应各种时频或时间-尺度特性的向量上。你可以自由的创建包含多个基的字典。例如，你可以构造一组表达平方可积空间的基，这组基包含小波包基和局部余弦基。这样构造的字典可以极大地增加你稀疏表达各种特性信号的能力。
2.字典非线性近似
? 定义表达你的信号空间的归一化基本模块作为字典。这些归一化向量叫做原子。如果字典的原子张成了整个信号空间，那么字典就是完全的。如果有原子之间线性相关，那么字典就是冗余的。在大多数匹配追踪的应
用中，字典都是完全且冗余的。
? 假设{φk}表示字典的原子。假设字典是完全且冗余的。使用字典的线性组合表达信号将是不唯一的。
? 一个重要的问题是是否存在一种最好的表达方式，一种直观的最好方式是选择φk使得近似信号和原始信号有最大的内积，如最好的φk满足
即对于正交原子，为投影到由φk张成的子空间上的幅值。 匹配追踪的中心问题是你如何选择信号在字典中最优的M个展开项。 3.MP算法 》基本思想
MP算法的基本思想：从字典矩阵D（也称为过完备原子库中），选择一个与信号 y 最匹配的原子(也就是某列)，构建一个稀疏逼近，并求出信号残差，然后继续选择与信号残差最匹配的原子，反复迭代，信号y可以由这些原子的线性和，再加上最后的残差值来表示。很显然，如果残差值在可以忽略的范围内，则信号y就是这些原子的线性组合。
》算法流程
用Φ={φk}表示一个原子归一化的字典，x表示信号。 (1)首先初始化残差e0=x；
(2)匹配追踪的第一步是从字典中找到与e0的内积绝对值最大的原子，表示为φ1；
(3)通过从e0减去其在φ1所张成空间上的正交投影得到残差e1； 其中e0,?φ1表示e0与φ1的内积。由于已经说明Φ为原子归一
化的字典，即φ1为单位列向量，所以e0在φ1所张成空间上的正交投影可以表示为e0,?φ1φ1?(由于为一个向量，所以e0在φ1所张成空间上的正交投影即为e0在φ1方向上的正交投影分量)，若φ1不是单位列向量，则e0在φ1方向上的正交投影分量为e0,?φ1φ1-(φ1Tφ1)，其中上标T表示转置。
(4)对残差迭代执行(2)、(3)步；
其中φm+1是从字典中找到与em的内积绝对值最大的原子。 (5)直到达到某个指定的停止准则后停止算法。
这里要从数学上说明一点：由于内积em,?φm+1实际上为一个数(标量)，所以
（分母中乘上φTm+1φm+1?，一开始没想明白，注意这里的φm+1? 是单位向量，则转置乘上自己是一个数值，也就是1）
若令P=φm+1?(φTm+1φm+1)-1φTm+1?，（这里的P是用每次选择出的与残差内积最大的原子来计算的，而下面OMP中的P是用每次选择过的原子组成的矩阵来计算的！！！）则第(4)步的迭代公式为
注意矩阵P每次迭代都是不同的。 》提出一个问题?
在描述MP算法时，有类似这样的话：在匹配追踪(MP)中，字典原子不是相互正交的向量。因此上面减去投影计算残差的过程中会再次引入与前面使用的原子不正交的成分。或者是：信号(残值)在已选择的原子进行垂直投影是非正交性的，这会使得每次迭代的结果并不是最优的而是次最优的，收敛需要很多次迭代。
那么如何理解什么是最优的，什么是次最优的？为什么不是正交的呢？
首先回顾下正交投影，一个向量(b)在另一个向量(a)上的投影： p称为b在a上的正交投影，正交投影就是法线垂直于a的投影（不知道这种说法对不对，有待考究）实际上就是寻找在a上离b最近的点。如果我们把p看作是a的估计值，那么我们定义e = b - p，称e为误差(error)。
现在，我们的任务是找到这样的p，我们可以规定p = xa（x是某个数），那么e = b - xa，因为e与p也就是a垂直，所以有a(b - xa) = 0，展开化简得到：
?将x代入到p中，得到：我们发现，如果改变b，那么p相对应改变，然而改变a，p无变化。
有了上面的背景知识，我们可以正式进入主题了，投影矩阵(projection matrix)：?p = Pb，显然这里有：
这个投影到底有什么用呢，从线性代数的角度来说，Ax = b并不一定总有解，这在实际情况中会经常遇到（m n）。所以我们就把b投影到向量p上，求解Ax = p。
接下来，我们可以考虑更高维度的投影，三维空间的投影是怎么样的呢，我们可以想象一个三维空间内的向量在该空间内的一个平面上的投影：
我们假设这个平面的基(basis)是a1, a2.那么矩阵A = [a1 a2]的列空间就是该平面。假设一个不在该平面上的向量b在该平面上的投影是p，那么我们就有下面这个表达式p = x1a1+ x2a2= Ax，我们的任务就是
M P 算 法 和 O M P 算 法 及 其 思 想
