稀疏字典学习

稀疏字典学习是一种表征学习方法，其目的在于找出一组基本元素让输入信号映射到这组基本元素时具有稀疏表达式。我们称这些基本元素为“原子”，这些原子的组合则为“字典”。字典里的“原子”并不需要满足正交基这一特性，且往往它们会是过完备的生成集合。过多的原子除了可以让我们在叙述一个讯号的时候可以由很多种表达式，同时也提升了整个表达式的稀疏性，让我们可以以较简单的表达式来诠释讯号。

稀疏字典学习最主要应用在压缩感知及讯号还原上。在压缩感知上，当你的讯号具有稀疏或者接近稀疏特质时，那么只需要对讯号进行几次的随机取样就可以把高维度的讯号描述出来。但在现实世界中，并不是全部讯号都具有稀疏这一特性，所以我们需要把找出这些讯号的稀疏表达式，转换方式有很多种，根据不同的讯号有不同的转换方式。当高维度的讯号转换至稀疏讯号时，那么就可以透过少次数的线性取样，并利用一些还原算法如：基追踪（Basis Pursuit)、CoSaMP、正交匹配追踪(Orthogonal Matching Pursuit)等方法来对讯号进行还原。

在这整个过程中，关键在于如何找到一个转换方式把讯号转换到具有稀疏表达式的域内，也就是如何建立一个字典，让讯号投影在这个字典上时具有稀疏表达式。而稀疏字典学习就是利用学习的方式帮我们找出这个转换方法，即稀疏字典。稀疏字典学习的兴起是基于在讯号处理中，如何使用较少的元素来叙述一个讯号。在这之前，普遍上大家还是使用傅立叶转换（Fourier Transform）及小波转换（Wavelet Transform)。不过在某一些情境下，使用透过字典学习得到的字典来进行转换，能有效的提高讯号的稀疏性。高稀疏性意味着讯号的可压缩性越高，因此稀疏字典学习也被应用在资料分解、压缩和分析。

问题定义

假设输入讯号集合$X=[x_{1},...,x_{K}],x_{i}\in \mathbb {R} ^{d}$，

我们希望找到一个字典$\mathbf {D} \in \mathbb {R} ^{d\times n}:D=[d_{1},...,d_{n}]$和一个表达式$R=[r_{1},...,r_{K}],r_{i}\in \mathbb {R} ^{n}$，让$\|X-\mathbf {D} R\|_{F}^{2}$最小化，且其表达式 $r_{i}$足够稀松。

这个问题可以被视为是下面这个最佳化问题：

${\underset {\mathbf {D} \in {\mathcal {C}},r_{i}\in \mathbb {R} ^{n}}{\text{argmin}}}\sum _{i=1}^{K}\|x_{i}-\mathbf {D} r_{i}\|_{2}^{2}+\lambda \|r_{i}\|_{0}$，而

${\mathcal {C}}\equiv \{\mathbb {D} \in \mathbb {R} ^{d\times n}:\|d_{i}\|_{2}\leq 1\,\,\forall i=1,...,n\}$，$\lambda >0$

这里需要 ${\mathcal {C}}$来限制 $\mathbf {D}$的原子不会因 $r_{i}$的值非常小而变得无穷大。$\lambda$这里则是控制稀松性，$\lambda$越大，稀松性越大，$\lambda$越小，稀松性越小，但稀松性越大代表还原的误差也会越大，$\lambda$的取值常常伴随着稀松性与还原误差之间的取舍。

字典的性质

当n<d，上述定义的稀松字典$\mathbf {D}$被称为低完备（Undercomplete）；当n>d，稀松字典$\mathbf {D}$则被称为过完备（Overcomplete）。

低完备字典会让输入讯号投影到低维度空间，类似于降维(Dimension reduction)、主要成分分析。在投影到低完备的字典时，如何选择重要的子空间（Subspace）是非常重要的，选择对的子空间能够让讯号最大程度的被保留下来。使用低完备字典进行降维这个方法可以应用在资料分析或分类上。

过完备的字典由于由较多的“原子”组成，因此一般上拥有较丰富的表达式。此外，过完备的特性能让讯号投影在到过完备字典时拥有稀松的特性。而透过学习得到的字典，即透过稀松字典学习而来的字典能让讯号在投影过来之后拥有更加稀松的表达式。

算法

在问题定义有提到，在找寻一个可以让讯号投影至该空间并具有稀松特质的字典其实就是一种最佳化问题。这最佳化问题与稀松编码以及字典相关，目前大部分算法都是迭代式的相继更新字典以及其表达式。

最佳方向法 Method of optimal directions (MOD)

最佳方向法是其中一个最早被提出用来解决稀松字典学习的方法。最佳方向法的核心理念是下面的最小化问题，在下面的最小化问题中，它的表达式只有固定数量的非零数值。

$\min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T$

在这里，$F$为弗罗贝尼乌斯范数（Frobenius norm）。在整个算法过程中，MOD使用匹配追纵（Matching Pursuit)来取得讯号的稀松编码，随即计算$\mathbf {D} =XR^{+}$的解析解（Analytic solution），这里的$R^{+}$指的是摩尔－彭若斯广义逆（Moore-Penrose pseudoinverse)。随后这个更新后的$\mathbf {D}$会在再标准化（Renormalized）以达到我们的约束条件。这时，新的稀松编码也会同时计算得到。这个过程会一直重复直到稀松字典$\mathbf {D}$以及稀松编码$R$收敛为止。

K-SVD

K-SVD 主要是以奇异值分解为核心来更新稀松字典的“原子”。它会让输入讯号$x_{i}$以不超过$T_{0}$的元素以线性组合的方式表示，整个过程与MOD类似：

$\min _{\mathbf {D} ,R}\{\|X-\mathbf {D} R\|_{F}^{2}\}\,\,{\text{s.t.}}\,\,\forall i\,\,\|r_{i}\|_{0}\leq T_{0}$

整个算法的过程在，一、先固定字典，找出满足上述条件相对应的$R$（可以使用匹配追踪)。然后固定$R$，利用下面的式子迭代式的更新字典。

$\|X-\mathbf {D} R\|_{F}^{2}=\left|X-\sum _{i=1}^{K}d_{i}x_{T}^{i}\right|_{F}^{2}=\|E_{k}-d_{k}x_{T}^{k}\|_{F}^{2}$

相关应用

整个字典学习的架构，其实就是对我们的输入讯号进行线性分解，分解到字典里的少数“原子”，并具有稀松特性。而这些“原子”是由本身的讯号产生，或学习得出来的。稀松字典学习可以应用在影像或者是影片处理。这个技术也常常被应用在分类问题上，我们可以针对不同的分类来对字典进行设计，透过输入讯号映射到字典的稀松表达式，我们可以较容易的把该讯号进行有效的分类。

此外，字典学习还有一个性质，那就是在杂讯去除上非常有效。这时因为字典在学习时会找出输入讯号相似的特性，这时候具有意义的讯号会被学习到字典，而不具意义的讯号则会被排除在字典之外。那么，当输入讯号映射到字典时，由于字典不含有杂讯的“原子”，所以该讯号在还原回来时不会有杂讯。