稀疏表示
1. 引言
稀疏表示具有完善的理论基础和使用价值并且广泛应用于图像处理，模式识别和机器视觉等领域。本文主要介绍稀疏表示算法理论基础和其在图像处理中的应用。理论基础全面介绍了稀疏表示的理论框架和不同lp-范数正则化项下优化算法。应用上结合无监督字典学习方法和有监督字典学习方法介绍了稀疏表示在图像处理和目标识别领域的应用。着重介绍在图像去噪，图像超分辨率，人脸识别以及目标识别等领域的应用算法，并分析算法的特点，和后续的发展趋势。最后总结稀疏表示在图像中的应用并对稀疏表示的发展方形进行展望。本文主要介绍系数表达的基本概念和l0范数的求解，后续的lp范数以及求解和应用见后续更新。
2. 稀疏表示框架
稀疏表示的目的就是从已有的字典中选择具有代表性的原子来表示输入图像。字典通常会是一个过完备的字典，因此在进行编码时得到的向量通常只有少数几个元素是为零的，其他的都为零，因此把这样的编码向量称之为稀疏编码。定义输入信号为y，已经学习到的字典为D，稀疏编码为 ，则稀疏编码的目标函数如下：：
其中，K是稀疏约束， 为
-范数，为向量中非零元素的个数。
通常我们更容易处理不含有约束的优化问题，因此将式引入拉格朗日乘子，则可以改写为
下面对式从贝叶斯角度进行推导，假定，根据贝叶斯公式可得
其中，为条件概率，
为先验概率。假设稀疏编码稀疏服从指数分布，那么
，
其中，p=0,为-范数稀疏编码。
上式即为一般稀疏表示的目标函数。但是这里含有零范数，是一个非凸的NP难问题，因此在进行稀疏表示时出现了两大方向：一是对式采用贪婪的算法求取近似解；二是将-范数进行松弛为l1-范数或者l2-范数。图1展示了不同范数的解空间。零范数和l1-范数l2-范数的解可以进行近似。在目标函数的约束下，l1-范数和零范数的解更为相近，l1-范数解空间为凸集但是却不是光滑可微的，l2-范数近似程度较差，但是为凸集而且可微便于优化。因此在不同的应用背景下具有不同的要求。
图1 单位-范数示意图：(a)p=0;(b)p=1;(c)p=2;(c)0<p<1
3. l0 -范数稀疏表示
l0 -范数稀疏表示目标函数即为式所示。如图2所示，解空间是非凸的，无法找到最优解，因此通常采用贪婪算法进行求解。经典的贪婪算法为MP[3]，OPM[4]算法。
3.1 MP算法
- 初始化：
其中，R表示残差字典D必须是归一化的，即
1) 找到最接近残差的字典元素
找到內积最大的字典元素，说明该元素和残差最接近
2) 更新残差
由图2可知，得到的残差和字典元素正交，因此根据勾股定理有
3) 继续迭代
4) 终止条件
5) 最终表示形式
其中， 就最终关于字典D的稀疏表示[3]。
6) 算法的收敛性
从下面的向量图我们可以清楚地看出，k+1的残差Rk+1是k步残差Rk 的分量。根据直角三角形斜边大于直角边，|Rk+1|<=|Rk|，则算法收敛
图2 MP示意图
3.2 OMP算法
Orthogonal Pursuit Algorithm算法简称 OPM算法。其是一种在MP算法上的改进算法[4]。
如果我们的字典只有两个向量d1，d2，那么MP算法会在这两个向量间交叉迭代投影，也就是f=a1d1+a2d2+a3d1+a4d2+…..；也就是之前投影过的原子方向，之后还有可能投影。换句话说，MP的方向选择不是最优的，是次优的。
图 3 MP示意图
MP算法的次最优性来源其残差只与当前投影方向垂直，这样在接下来的投影中，很有可能会再次投影到原来的方向。
于是，在投影时，如果我们使得残差Rk+1与x1-xk+1的所有向量垂直，则可以克服这个问题，如下：
对于已经进行匹配过的字典中的元素不再进行匹配。OMP算法如下：