稀疏表示学习(二)-- 如何计算稀疏表示

木卯 于 2021-06-14 发布

稀疏表示学习(二)

本次主要学习资料是Duke大学Guillermo Sapiro教授的公开课——Image and video processing, by Pro.Guillermo Sapiro 课程。该课程可以在 Bilibili 上找到学习资源。

1. 稀疏建模的理论和实现 - Theory and Implementation

我们已经有了信号和字典,怎么求其稀疏表示 $\alpha$ ? 我们想要具有非零系数最少的 $\alpha$,非零系数的数量也称为 support。我们假设现在没有噪声。注意到:$\alpha$ 并不一定唯一,例如当字典 D 的几列是相同的。当时用DCT离散余弦变换或者傅立叶变换时,$\alpha$ 是唯一的。因为后者产生的字典的每一列和其他列是正交的(线性无关的)。因此看起来字典 D 和稀疏表示 $\alpha$ 的唯一性有很大的关系,更进一步,是 D 中的 k 和 generalization。

img1

我们要解决的问题实际上是一个 NP-hard 的问题。一种解决方法是,首先设置 L 为 1,然后有 C(K, L) 种 suppoet,对每一种 support 通过最小二乘计算出来稀疏表示 $\alpha$ 使得有最小重构误差。验证重构误差是否小于阈值。如果全部都不满足,则 L 加一,选择更多的列来重构。

img2

假设 K = 1000, L = 10,计算量是非常非常庞大的。尽管 1ns 就能计算一次 LS,也需要 $8 \times 10^6$ 年才能算完。

有两种基本的方法可以解决上述问题:

img3

Relaxation Method

将 $L_0-\text{norm}$ 放松为 $L_1-\text{norm}$ ,当 D 和 L 满足某些条件时,可以保证这两个是等效的。从一个NPC问题转化到了一个凸优化问题。

img4

img5

Greedy Method

首先找到最重要的 atom,也就是 $|D\alpha - y|^2_2$ 有最小值。然后再找第二重要的 atom…..。一直到重构误差小于阈值。

img6

当选择了两个 atom 时,贪心算法出来的并不一定是向这两个 atom 张成的子空间投影,这样其实误差不是最小的。所以在 OMP 算法中对每次所选定的原子构成的子空间进行投影,用最小二乘算法即可。

遗留的问题是:Why should they work?

背后的理论会告诉我们,虽然有时候我们进行了放松,但是实际上却可以产生正确的结果。

2. 总结

img7