机器学习经典算法：k-SVD 前面为什么加个 k?

由 SVD 分解可得

，然后令

，其对应于最大的奇异值，以及令

。由于

，可知字典中的原子是单位向量。

后续将

得到的更新值放在

的对应位置，而后者现在至少有与以前一样多的零。在每次迭代中，误差都会减小，算法会收敛到局部最小值。

综上所述，

-SVD 算法的每次迭代包括以下计算步骤。

1、初始化

，即用

范数归一化它的每一个列向量，并令

。

2、第 1 阶段稀疏编码：用相关算法（如 OMP）解优化问题，获得稀疏编码表示向量

，

。

3、第 2 阶段字典更新：对于

中的任何列

，根据以下步骤进行更新：

从第 1 阶段计算所得的矩阵

中确定第

行中各非零元素的位置。

选择

中与

的第

行非零元素位置对应的列，构建误差矩阵

。

求

的 SVD 分解：

。

将

的第

列更新为最大奇异值对应的左奇异向量，即

。

更新

，将它的第

行的非零元位置设为

中的相应值。

4、如果满足收敛标准，则停止迭代；否则令

，继续迭代。

名称的 SVD 部分非常明显。但是，读者可能想知道前面为啥要加一个

。注意，这里的

跟算法中的步骤

没有关系，因为步骤可以用另一个字母表示。

那么它到底为啥要加上这个名头呢？实际上，该算法可以被认为是

-means 算法的推广。可以将代表每个簇的平均值视为字典的原子。在

-means 学习的第一阶段，给定每个簇的代表，执行稀疏编码方案；也就是说，每个输入向量都只分配一个簇。

因此，我们可以将

-means 聚类视为一种特殊的稀疏编码方案，它将一个系数向量与每个观察值相关联。请注意，此时每个系数向量只有一个非零元，根据与所有簇代表的最小欧几里德距离可得相应输入向量的簇。与

-SVD 字典学习的主要区别是每个观察向量可以与多个原子相关联；因此，相应系数向量的稀疏度可以大于

。

此外，基于输入向量到簇的分配，在

-means 算法的第二阶段，执行簇代表的更新，但对于每个代表仅涉及分配给它的输入向量。这与

-SVD 的第二阶段的情况相似。不同之处在于每个输入观察可能与多个原子相关联。如果设

，此时

-SVD 相当于

-means 算法。

关键词： 优化问题 输入向量 第二阶段