稀松字典学习

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

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

${\displaystyle {\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}}$ ^[2]，而

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

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

字典的性质

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

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

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

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

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

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

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

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

K-SVD

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

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

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

${\displaystyle \|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}}$ 

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

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

1. ^ Needell, D.; Tropp, J.A. CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Applied and Computational Harmonic Analysis. 2009-05, 26 (3): 301–321 [2018-11-18]. ISSN 1063-5203. doi:10.1016/j.acha.2008.07.002. （原始内容存档于2018-10-24）. 
2. ^ 稀疏表示以及字典學習 - 程式人生. www.796t.com. [2022-09-26]. （原始内容存档于2022-09-29） （中文（台湾））.