K-SVD详解

K- SVD :为稀疏表示设计过完备字典

1.稀疏表示

我们现在有:
一个样本向量y = [y1,y2,y3,…,yn].
一个字典D (size:n×M)
其中，D中的每一列

称为D的原子。
稀疏表示就是要用D的原子的线性组合来将y表示出来。换句话说，就是要解y=Dx这个方程组，并且这个x向量中的0元素越多越好（0越多越稀疏）。
但是，因为D的列数M远大于行数n（这就是所谓的过完备），学过线性代数的人都知道，这样会导致这个方程组有无穷多解。所以我们要从这些解中找到一个最稀疏的精确解x。

但是精确确定最稀疏的解被证明是np难问题（其实说白了，你要在无穷多的解中找出一个最稀疏的，你是不是要把所有解都求出来呢？这个计算量是个天文数字），所以，我们退而求其次，求出一个近似精确的解：


是L0范数，是向量非0元素的个数。

稀疏编码：追踪算法

稀疏编码就是根据给定的y和字典D来计算稀疏解x（x也被称作稀疏系数）的过程，追踪算法是用来求解近似稀疏解的算法。
因为求解确定的y=Dx解被证明是np难问题，所以通过追踪算法来求解y≈Dx的近似解。
用的比较多的是正交匹配追踪（OMP）和欠定系统局灶解法（FOCUSS）。

K-SVD 算法

在之前所说的稀疏表示求解过程中，字典D都是事先确定好的，固定不变。如何通过一组训练数据，通过训练使字典D更加适合这些数据呢？这就是k-svd的用武之地。它通过一组给定的训练向量，在严格的稀疏性的限制下，寻找一个能使训练集中的每一个成员都实现最优的表示的字典。

那么字典的更新具体是如何进行的呢？这是一个迭代的过程，分为下面两步：
1.在当前字典的基础上更新样本的稀疏系数。
2.更新字典，使其更加适应于数据。

1,2步交替进行，直到字典D和稀疏系数x都不再变化，即达到收敛。
k-svd非常灵活，可以与任何追踪算法一起工作（步骤1）。

k-means 聚类算法的扩展

k-svd中的k是什么意思呢？它表示k-svd算法是k-means聚类算法的扩展。
如果向量y只能被字典D中的其中一个原子表示（计算y到D中每个原子的欧氏距离，选择距离最近的原子作为y的稀疏表示）那么这将是一种极端的稀疏表示，并且乘以该原子的稀疏系数x只有一个非0元素且值为1.而这就是k-means算法的内容。
k-svd和k-means的不同之处在于，稀疏系数x可以有多个非0元素而且可以取任意值。
而相似之处在于，k-means中更新聚类中心的过程对应着k-svd中更新字典原子的过程，而k-svd中的对稀疏系数的更新对应着k-means中对各个样本所属类的更新。k-means中也是不断迭代这两个过程，直到达到收敛。

k-svd算法内容

k-svd分为两步：
1.在当前字典的基础上更新样本的稀疏系数。
2.更新字典，使其更加适应于数据。

由于要一次处理多个样本向量，所以式子变为了这样：

其中
Y表示有k个样本向量的矩阵，X表示每个样本向量对应的稀疏系数组成的矩阵。
size: Y：n×K，D：n×M , X：M×K

先说第一步：
第一步主要是在字典D固定的条件下，更新稀疏矩阵X。
因为

所以，更新X的操作可分解为K次单独更新X的每一列。

i=1,2,…,K.
这样，问题又回到了简单的只有一个y向量的情况，任何一种追踪算法都可解决。

再来说说第二步，用SVD更新字典D：
我们将DX分解为K个秩1矩阵之和，这里每个秩1矩阵都是D中第k列乘X中第k行（k=1,2，…,M）。
秩1矩阵：秩为1的矩阵，可表示为一个列向量乘以一个行向量的形式。

对于字典D的更新，我们依次更新字典D中的第k列dk和X中与其对应的第k行 ，更新时固定D中其他行和X中其他列，直到D中所有列和X中的所有行都更新完为止。
损失函数改变为：

更新D中第k列时，将提出来，剩下的就是固定不变的了。与Y合并为Ek。
这里就有一个问题，如果用SVD直接求出：

然后取U的第一列和V的第一行作为更新后的dk和xkt（x的第k行），确实可以使损失函数达到最小值，但是这样可能完全改变xkt，使其失去稀疏性，这样第一步做的工作都白费了。
k-svd的解决方法是，每次只有xkt中的非0元素参与更新。
首先，记录xkt中的非0元素的索引组成wk。

如：

然后构造矩阵Ωk，size：M×|wk| ，在第（wk(i),i）处，元素为1，其余都是0。
|wk|的大小等于wk元素的个数。
如：

这样，使

xRk就是xTk丢弃掉0元素后仅剩非0元素的向量。

同理：

size：n×|wk| (xTk保留第1,4个元素，Y保留第1,4列)

size：n×|wk| (也是保留和xTk非零元素对应的列)

至此，式

变为：

我们通过对EkR矩阵进行svd分解：

取U第一列和VT第一行作为更新后的dk和xRk。
将字典中的M个原子都更新完成之后，字典D和稀疏系数矩阵X均更新完成。步骤2完成。

重复步骤1和步骤2，当D和X不再变化时，达到收敛。停止迭代。

下面是k-svd算法的完整表示：