2.3.3 字典学习算法
典型的字典学习算法包括主成分分析（Principal Component Analysis，PCA）、最优方向法（Method of Optimal Directions，MOD）[18]、K-均值（K-Means）算法、K-奇异值分解（K-SVD）算法[19]、贪婪自适应字典（Greedy Adaptive Dictionary，GAD）[17]等。PCA字典学习算法通过低维子空间来联合近似表示训练样本。MOD算法交替更新字典和分解系数，有效地得到信号的冗余字典，但是同时更新字典和系数带来了较大的构造复杂度。K-SVD算法每次选择字典中的一列进行更新，同时引入约束矩阵，使得迭代不会搜索到局部极值。该算法可与众多稀疏编码算法相结合，形成改进算法，如短时不变字典EKSVD[20]等。
除了上述直接从训练样本中学习字典的方法之外，另一种构建冗余字典的思想是联合冗余，即将多个字典相合并，直接得到一个更为冗余的字典。利用联合冗余字典得到的稀疏表示具有唯一性，这一点得到了理论证明[21-22]。
下面介绍较为常用的字典学习算法：K-均值、K-SVD和GAD算法。
1. K-均值字典学习算法
K-均值算法实现了矢量的聚类，可应用于码书的训练，在矢量量化中应用广泛。对于给定的一批矢量数据，K-均值算法可以实现基本的按距离聚类，即同一类矢量之间的距离较短，而不同类矢量之间的距离较长，类内距离小于类间距离。整个聚类过程通过迭代实现，即利用当前聚类结果，计算同一类矢量的均值作为聚类质心，然后根据这些质心对所有矢量按距离大小重新聚类，直到迭代收敛或大于规定次数时结束。当聚类完成后，这些质心所对应的矢量就是构成码书的码字。利用码字序号可以直接表示属于该类别的任意矢量，这样就可以实现矢量降维和信号压缩。
K-均值算法的流程可用算法2-1描述。
算法2-1 K-均值算法
输入：数据集合
。
输出：码书C。每个数据用码书中最靠近的码字来表示，使得总误差最小，即
式中，el表示第l次迭代所对应的逼近误差矢量，
是数据集合对应的稀疏表示集。
1）初始化，令码书矩阵C（0）∈ℝn×L，迭代次数J=1。
2）循环执行步骤3～6：
3） 稀疏逼近，将数据按码字分为L个集合（胞腔）
划分规则：每个数据域对应胞腔内码字距离均小于与其余码字距离，即
4） 更新码书中每个码字：
5） 按照每个数据到码字的最近距离更新S。更新迭代次数J=J+1。
6） 停止准则。若
（预设误差门限）则停止，否则返回步骤2。
从信号稀疏表示的角度分析，K-均值算法学习得到的码书就是一个字典。基于这个字典对任意一个矢量进行量化时，量化得到的表示矢量都只有一个元素为1，其他元素均为0。这种表示可看作稀疏度为1的信号稀疏化，表示误差较大。可以考虑以提高稀疏值为代价获得更逼真的表示。另一方面，K-均值算法采用了全部码字同时更新的迭代方式，无法较好地匹配信号。
2. K-SVD字典学习
K-均值算法学习得到的字典，每次只能用一个原子表示信号，较为粗糙。为了解决这个问题，K-SVD算法在借鉴K-均值算法聚类思想的基础上采用多个原子的线性组合来表示信号，改善了字典学习的性能。为了准确地更新每个原子，避免像K-均值算法那样一次更新全部均值，K-SVD算法在迭代中使用奇异值分解（SVD）算法来选择每个原子所对应的更新误差，并逐个对原子进行更新。
K-SVD算法流程可用算法2-2描述。
算法2-2 K-SVD算法
输入：训练样本
，初始字典D。
输出：最终字典D，稀疏分解系数S。
1）初始化。随机得到初始化字典D，令迭代次数J=1。
2）循环直到满足停止条件：
3） 稀疏逼近。用已有稀疏分解算法对所有数据求出分解系数：
4） 更新字典。对字典中每列dl，l=1，2，…，L：
①定义S的第l行为
，则该行中所有非零元素使用了原子dl，这些非零元素的下标构成的集合为
②计算当前稀疏表示误差矩阵：
③根据下标集合ωl从El中选出稀疏表示时用到dl的列，记为
。
④使用SVD算法计算
，更新字典第l列
，更新误差
V（:，l）。
5） 更新迭代次数J=J+1。
6） 停止准则：若
≤预设误差门限，则停止；否则返回步骤2。
K-SVD算法每次选择字典中的一列进行更新，同时引入约束矩阵
，使得字典更新过程更加精细，且不会陷入局部极值。K-SVD算法是目前学习型字典方案中较好的一种，字典对样本的适应性较强，无须信号先验信息即可获得较好的稀疏化效果。同时也需要注意，采用学习法的字典学习过程计算量大，学习过程复杂。
3. 贪婪自适应字典学习
K-SVD算法从逼近误差方面（如式（2-3））约束字典学习过程，而贪婪自适应字典（Greedy Adaptive Dictionary，GAD）算法以稀疏性（如式（2-4））为约束进行字典训练，以期得到尽可能稀疏的信号表达，同时兼顾原子的稀疏性。为了得到最佳的稀疏表示字典，GAD分析每个（残差）信号的稀疏性，每次迭代都优先选择稀疏性最好的（残差）信号作为原子。这样的迭代过程可以快速减少信号的能量，同时保证l1范数降为最低。
GAD算法的具体流程可用算法2-3描述。
算法2-3 GAD算法
1）初始化：令j=0，初始字典D0=［］（空矩阵），残差R0=X，下标集T0=∅（空集）。
2）循环直到满足停止条件：
3） 寻找残差中稀疏度量最低的列：
4） 更新原子，即将第j个原子更新为归一化的
：
5） 更新字典和下标集：
Dj=［Dj-1|dj］， Tj=Tj-1∪{kj}
6） 计算新的误差：
7） 更新j=j+1。
8）若满足停止准则则停止，否则返回步骤2。
为便于计算，在该算法中用稀疏度量（sparsity index）来衡量信号的稀疏程度：对于任意矢量x，其稀疏度量定义为
稀疏度量越低，则说明信号稀疏程度越高。举例来说，若有两个二维矢量x1=［1，1］，x2=［0，1］，x2更为稀疏。它们的稀疏度量分别为
，ξ2=1/1=1，ξ1>ξ2。
另外，需要构造原始信号矩阵X。可将信号按时序分为长度为L的矢量xk，相邻两矢量之间有M点重叠：
xk=［x（（k-1）（L-M）+1），…，x（kL-（K-L）M）］T
（2-8）
再将K个矢量组合为RL×K维矩阵X：
X（l，k）=x（l+（k-1）（L-M））
（2-9）
GAD算法中的停止条件可灵活选择如下两种方式之一：
①获得L个原子形成字典方阵，即重复步骤2～7共L次。
②根据信号稀疏逼近重构误差
式中，σ为设定的误差门限。重构信号
可由当前字典得到：
