1. 建矩阵 ，其内容为：

   

   其中每一行对应一个样本，每一列对应一个特征。

2. 特征选择所考虑的问题是：矩阵 中的许多列与当前学习任务无关。

   通过特征选择去除这些列，则学习器训练过程仅需要在较小的矩阵上进行。这样学习任务的难度可能有所降低，涉及的计算和存储开销会减少，学得模型的可解释性也会提高。

3. 考虑另一种情况： 中有大量元素为 0 ，这称作稀疏矩阵。

   当数据集具有这样的稀疏表达形式时，对学习任务来讲会有不少好处：

   • 如果数据集具有高度的稀疏性，则该问题很可能是线性可分的。对于线性支持向量机，这种情况能取得更佳的性能。
   • 稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已经有很多很高效的存储方法。

1. 字典学习：学习一个字典，通过该字典将样本转化为合适的稀疏表示形式。它侧重于学得字典的过程。

   稀疏编码：获取样本的稀疏表达，不一定需要通过字典。它侧重于对样本进行稀疏表达的过程。

   这两者通常是在同一个优化求解过程中完成的，因此这里不做区分，统称为字典学习。

2. 一个自然的想法进行线性变换，即寻找一个矩阵 使得 。

3. 现在的问题是：既不知道变换矩阵 ，也不知道 的稀疏表示 。

   因此求解的目标是：

   • 根据 能正确还原 ，或者还原的误差最小。
   • 尽量稀疏，即它的分量尽量为零。

   因此给出字典学习的最优化目标：

   其中 称作字典矩阵。 称作字典的词汇量，通常由用户指定来控制字典的规模，从而影响到稀疏程度。

   • 上式中第一项希望 能够很好地重构 。
   • 第二项则希望 尽可能稀疏。

5.2 算法

1. 这里有个最优化问题：

   该问题有多种求解方法，常用的有基于逐列更新策略的算法。

   令 为字典矩阵 的第 列， 表示稀疏矩阵 的第 行。 固定 其他列，仅考虑第 列，则有：

   

   令 ，它表示去掉 的稀疏表示之后，样本集的稀疏表示与原样本集的误差矩阵。

   考虑到更新字典的第 列 时，其他各列都是固定的，则 是固定的。则最优化问题转换为：

   

   求解该最优化问题只需要对 进行奇异值分解以取得最大奇异值所对应的正交向量。

2. 直接对 进行奇异值分解会同时修改 和 ， 从而可能破坏 的稀疏性。因为第二步 “以 为初值来更新字典 ” 中， 在更新 前后 的非零元所处的位置和非零元素的值很可能不一致。

   为避免发生这样的情况 KSVD 对 和 进行了专门处理：

   • 仅保留非零元素。
   • 仅保留 和 的非零元素的乘积项，然后再进行奇异值分解，这样就保持了第一步得到的稀疏性。