主要参考资料为Michael Elad的PPT和From Mars to Hollywood with a stop at the hospital课程中p064开始的几个Video。
基本概念
从对压缩感知的初步了解，可以认识到，很多信号是可以稀疏表达的，至少在某个基下面具有这样的性质。这就是稀疏表达的出发点，一个信号可以看做几个主要基信号（也就是字典）的线性组合。如果从信号的稀疏性出发，事实上给了我们关于信号的一个先验知识，这一点将用来约束我们对问题的描述。
对于我们的信号x，我们可以将其看做字典D和一个向量a的积。其中信号x有N个element，a为K个维度，D则是NxK维度。因为a中只有少数几个点不为零（图中的红点），D乘以a就相当于，从D中选取对应的那几个列向量进行线性组合，从而得到X。所以D中的每一列都叫做atom，相当于字典里的词条。
image.png
稀疏表达的一个作用就是找出信号中最重要的元素，而忽略其他不必要的噪声。比如一张含有噪声的图像，因为噪声是无法很好的fit到字典的atom中的，所以利用稀疏表达进行图像重建以后就可以有效的去除这些噪声。
求解算法
下面的算法作为了解即可，并不需要掌握其实现过程，因为不管是MATLAB还是Python都提供了这些工具包。
Basis Pursuit（BP）算法
我们的目标是找到字典D和a，并且a非常的稀疏，并且根据稀疏表达复原的信号应该和原始信号尽量的接近。如果用数学公式表示出来的话，如下图左上所示。正如我们在压缩感知一文中指出，解L0太复杂了，所以这里采用了L1进行近似（下图右上所示）。对于BP算法，了解到这里就OK了。
BP算法
Matching Pursuit（MP）算法
Matching Pursuit（MP）算法提供了另外一种解决方案。
MP算法
- 找到字典中最重要的atom，也就是最接近信号的atom。
- 找到字典中第二个atom，使第一个，第二个atom组合的结果更加接近信号。
- 当组合的error小到一定程度的时候，停止。
（Orthogonal MP）OMP算法，则是MP算法的一种变体。它在更新的时候允许a的系数进行改变。
