求解几种稀疏表示模型的ADMM算法研究(5)
（2.1）
其中的参数
由于测试样本的类别最初是未知的，可以将所有的训练集串联成一个新的矩阵，记做：
（2.2）
这样矩阵A就是包含所有训练样本的超完备字典。那么y根据所有训练样本的线性表达可以记做：
（2.3）
其中 是系数向量，如果y属于第i类那么在 中除了与第i类相关的系数外其余均为零。这样一来， 能够表示测试样本的类别，因此对方程组 的求解是至关重要的。
一个有效的测试样本可以仅仅只被与其属于同一类的训练样本充分表达。因此我们希望能够求解针对方程 最稀疏的解，即求解L0优化问题：
（2.4）
其中 代表0范数，即计算向量中非零分量的个数。一般来说当x的分量中非零的个数少于m/2，那么此x即为最稀疏的解。然而，在一个欠定线性方程系统中，求解最稀疏解的问题是NP-hard问题。也就是说，在一般情况下，除了穷举法以外，没有已知的更有效的方法来求解此问题。为此需要对问题进行转化。
可以证明，如果解 是足够稀疏的，那么L0最小化问题（2.5）与以下的L1最小化问题等价[2]：
（2.5）
该问题可以利用标准的线性规划方法在多项式时间内求解。论文网
对于（2.3），由于真实情况下的数据往往是有噪声的，因此通常直接利用（2.3）不能对测试样本进行精确的表达。针对这些微小的稠密噪声，可以对（2.3）进行修改如下：
（2.6）
其中 是噪声项，且 。通过解决以下问题，稀疏解 仍然可以近似得到：
（2.7）
若假设残差 也是稀疏的，则可以对式（2.8）做改进如下：
（2.8）
问题（2.8）、（2.9）可以利用二阶规划有效的解决。对于任意的矩阵A，问题的解能够保证与稀疏解近似：对于 以及 ，如果有 ，那么得到的解 满足
（2.9）
2.1.2 框架与算法
对于一个给定的属于某一类训练集的测试样本，首先通过（2.6）或者（2.8）计算其稀疏表示系数 。在理想情况下， 中的非零分量仅存在于A中某些列所对应的那些分量，这些列均属于测试样本所在类别i。然而受噪声以及模型误差的影响，在其他类所对应的分量中也会有非零项。为了充分利用图像的子空间结构特性，可以根据得到的这些系数对测试样本y的恢复情况的好坏来判断y的类别。对于每一类，如第i类，令 为该类的特征函数。利用残差最小化
上一篇：大学生学习行为的模型及其经济分析