稀疏表示学习（二）-- 如何计算稀疏表示
稀疏表示学习（二）
本次主要学习资料是Duke大学Guillermo Sapiro教授的公开课——Image and video processing, by Pro.Guillermo Sapiro 课程。该课程可以在 Bilibili 上找到学习资源。
1. 稀疏建模的理论和实现 - 如何计算稀疏表示
我们已经有了信号和字典，怎么求其稀疏表示 α \alpha α ? 我们想要具有非零系数最少的 α \alpha α，非零系数的数量也称为 support。我们假设现在没有噪声。注意到： α \alpha α 并不一定唯一，例如当字典 D 的几列是相同的。当时用DCT离散余弦变换或者傅立叶变换时， α \alpha α 是唯一的。因为后者产生的字典的每一列和其他列是正交的（线性无关的）。因此看起来字典 D 和稀疏表示 α \alpha α 的唯一性有很大的关系，更进一步，是 D 中的 k 和 generalization。
我们要解决的问题实际上是一个 NP-hard 的问题。一种解决方法是，首先设置 L 为 1，然后有 C(K, L) 种 suppoet，对每一种 support 通过最小二乘计算出来稀疏表示 α \alpha α 使得有最小重构误差。验证重构误差是否小于阈值。如果全部都不满足，则 L 加一，选择更多的列来重构。
假设 K = 1000， L = 10，计算量是非常非常庞大的。尽管 1ns 就能计算一次 LS，也需要 8 × 1 0 6 8 \times 10^6 8×106 年才能算完。
有两种基本的方法可以解决上述问题：
- Relaxtion methods：将 L 0 − norm L_0-\text{norm} L0−norm 放松为 L 1 − norm L_1-\text{norm} L1−norm 。
- Greedy methods：贪心算法。
Relaxation Method
将 L 0 − norm L_0-\text{norm} L0−norm 放松为 L 1 − norm L_1-\text{norm} L1−norm ，当 D 和 L 满足某些条件时，可以保证这两个是等效的。从一个NPC问题转化到了一个凸优化问题。
Greedy Method
首先找到最重要的 atom，也就是 ∥ D α − y ∥ 2 2 \|D\alpha - y\|^2_2 ∥Dα−y∥22 有最小值。然后再找第二重要的 atom…。一直到重构误差小于阈值。
当选择了两个 atom 时，贪心算法出来的并不一定是向这两个 atom 张成的子空间投影，这样其实误差不是最小的。所以在 OMP 算法中对每次所选定的原子构成的子空间进行投影，用最小二乘算法即可。
遗留的问题是：Why should they work？
背后的理论会告诉我们，虽然有时候我们进行了放松，但是实际上却可以产生正确的结果。