K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation

Paper:http://sites.fas.harvard.edu/~cs278/papers/ksvd.pdf
参考周志华《机器学习》
（阅读笔记，如有不当，敬请谅解）

1、写在前面

该篇论文是一篇methodology的论文，主要是解决稀疏表示的经典论文。

1.1、基本术语

• 什么是稀疏：一个数据的所有特征中，有很多的特征与当前要解决的问题是无关的（一般会在矩阵中就直接以0表示），这样就是稀疏。
• 优点：稀疏性很明显的具有数据开销小（0较多）的优点，学习器训练的难度也可能会很小。
• 如果数据本身它不是稀疏的，是稠密的，那么我们想让它有稀疏的优点，所以我们就可以对数据进行稀疏表示（Sparse Representation），而这个学习的过程就是字典学习，找到合适的字典，来转换成稀疏的表示形式。

1.2、稀疏表示的过程

给定数据集$\mathcal{X}:\{{x_1,x_2,...,x_m}\}$，即有：
$\min_{B,\alpha_i} \sum_{i=1}^{m}{\|x_i - B\alpha_i\|_2^2}+\lambda\sum_{i=1}^{m}{\|\alpha_i\|_1}$
其中$B\in\mathbb{R}^{d\times k}$是字典矩阵（转换的桥梁），$k$是字典的词汇量（样本数），$d$是样本特征数。很明显的，通过矩阵运算，上述公式目标有两点，其一：通过2范数，使$B\alpha_i=x_i$，其二：通过1范数，$\alpha_i$尽可能稀疏（0变多）。
即$\alpha_i\in\mathbb{R}^{k}$是样本$x_i\in\mathbb{R}^{d}$的稀疏表示，$\alpha_i$和$x_i$都是列向量，列向量中的元素就是该样本的特征数据。

1.3、如何求$B$和$\alpha_i$

分成两个步骤，先固定字典矩阵$B$求$\alpha_i$，再固定$\alpha_i$求$B$：
$\min_{\alpha_i} \|x_i - B\alpha_i\|_2^2+\lambda\|\alpha_i\|_1$
统一把$\alpha_i$和$x_i$合并成矩阵$A$和$X$，该矩阵即包含了所有的信息，第二步固定$\alpha_i$求$B$即转换成了矩阵F范数。
$\min_{B} \|X - BA\|_F^2$
其中$X=(x_1,x_2,...,x_m)\in \mathbb{R}^{d\times m}$,$A=(\alpha_1,\alpha_2,...,\alpha_m)\in \mathbb{R}^{k\times m}$,$X$和$A$就是将每一列（列向量）组合起来，直接就变成了矩阵。
$F-norm:\|X \|_F=\sqrt{\sum_{i}\sum_{j}x_{i,j}^2}$
而K-SVD就是求解字典矩阵$B$的方法。

2、K-SVD

上式$\min_{B} \|X - BA\|_F^2$可改写。
首先对$BA$进行改写，其中下标表示列数，上标表示行数：
$BA={\left[\begin{matrix}b_1^1 & b_2^1 & \cdot & \cdot & \cdot & b_k^1 \\b_1^2 & b_2^2 & \cdot & \cdot & \cdot & b_k^2 \\\cdot & \cdot & \cdot & & & \cdot \\\cdot & \cdot & & \cdot & & \cdot \\\cdot & \cdot & & & \cdot & \cdot \\b_1^d & b_2^d & \cdot & \cdot & \cdot & b_k^d \\\end{matrix}\right] }_{d \times k} \times {\left[\begin{matrix}\alpha_1^1 & \alpha_2^1 & \cdot & \cdot & \cdot & \alpha_m^1 \\\alpha_1^2 & \alpha_2^2 & \cdot & \cdot & \cdot & \alpha_m^2 \\\cdot & \cdot & \cdot & & & \cdot \\\cdot & \cdot & & \cdot & & \cdot \\\cdot & \cdot & & & \cdot & \cdot \\\alpha_1^k & \alpha_2^k & \cdot & \cdot & \cdot & \alpha_m^k \\\end{matrix}\right] }_{k \times m}\\={{\left[\begin{matrix}\sum_{j=1}^{k}b_j^1\alpha_1^j & \sum_{j=1}^{k}b_j^1\alpha_2^j & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_j^1\alpha_m^j \\\sum_{j=1}^{k}b_j^2 \alpha_1^j & \sum_{j=1}^{k}b_j^2\alpha_2^j & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_j^2\alpha_m^j \\\cdot & \cdot & \cdot & & & \cdot \\\cdot & \cdot & & \cdot & & \cdot \\\cdot & \cdot & & & \cdot & \cdot \\\sum_{j=1}^{k}b_j^d\alpha_1^j & \sum_{j=1}^{k}b_j^d \alpha_2^j & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_j^d\alpha_m^j \\\end{matrix}\right] }}_{d \times m}$
然后有$b_j\alpha^j$:
$b_j\alpha^j={\left[\begin{matrix}b_j^1\\b_j^2\\\cdot \\\cdot \\\cdot \\b_j^d\\\end{matrix}\right] } \times {\left[\begin{matrix}\alpha_1^j & \alpha_2^j & \cdot & \cdot &\cdot & \alpha_m^j \\\end{matrix}\right] }\\ = {{\left[\begin{matrix} b_j^1\alpha_1^j & b_j^1\alpha_2^j & \cdot & \cdot & \cdot & b_j^1\alpha_m^j \\ b_j^2\alpha_1^j & b_j^2\alpha_2^j & \cdot & \cdot & \cdot & b_j^2\alpha_m^j \\\cdot & \cdot & \cdot & & & \cdot \\\cdot & \cdot & & \cdot & & \cdot \\\cdot & \cdot & & & \cdot & \cdot \\ b_j^d\alpha_1^j & b_j^d \alpha_2^j & \cdot & \cdot & \cdot & b_j^d\alpha_m^j \\\end{matrix}\right] }}_{d \times m}$
求和有:
$\sum_{j=1}^{k}b_j\alpha^j=BA\\={{\left[\begin{matrix}\sum_{j=1}^{k}b_j^1\alpha_1^j & \sum_{j=1}^{k}b_j^1\alpha_2^j & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_j^1\alpha_m^j \\\sum_{j=1}^{k}b_j^2 \alpha_1^j & \sum_{j=1}^{k}b_j^2\alpha_2^j & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_j^2\alpha_m^j \\\cdot & \cdot & \cdot & & & \cdot \\\cdot & \cdot & & \cdot & & \cdot \\\cdot & \cdot & & & \cdot & \cdot \\\sum_{j=1}^{k}b_j^d\alpha_1^j & \sum_{j=1}^{k}b_j^d \alpha_2^j & \cdot & \cdot & \cdot & \sum_{j=1}^{k}b_j^d\alpha_m^j \\\end{matrix}\right] }}_{d \times m}$
所以用$\sum_{j=1}^{k}b_j\alpha^j$来表示$BA$，即有下式，其中$E_i=\sum _{i\neq j} b_j\alpha^j$，即直接求解特定的$b_i$。
$\min_{B} \|X - BA\|_F^2\\=\min_{b_i} \|X - \sum _{j=1}^k b_j\alpha^j\|_F^2\\=\min_{b_i} \|(X - \sum _{i\neq j} b_j\alpha^j) -b_i\alpha^i\|_F^2\\=\min_{b_i} \|E_i-b_i\alpha^i\|_F^2$
特别地，因为其他列都是固定的，所以在化简的时候可以简便，直接对$E_i$进行化简即可。

Tips

奇异值分解其实与特征值分解有很紧密的相似性，我们针对的特征值分解$\lambda$一般都是方阵，用来提取这个矩阵最主要的特征，而现实中方阵的要求却较为严格。那么一般矩阵就是用奇异值分解来提取特征信息。

• 实矩阵$A\in\mathbb{R}^{m\times m}$，特征值分解：$A=Q_{m\times m}\sum Q_{m\times m}^{-1}$，$Q$是矩阵$A$的正交特征向量组成的矩阵，$Q$是正交阵，所以转置和逆都是一样的$(Q^{-1}=Q^T)$，另外$\sum$是对称阵，且只有主对角线上有元素，值是矩阵$A$的各特征值$\lambda$（$\lambda$的位置对应特征向量的位置）。
• 实矩阵$A\in\mathbb{R}^{m\times n}$，奇异值分解：$A=U_{m\times m}\sum_{m\times n}V_{n\times n}^T$，其中$\sum$也同特征值分解一样，是由奇异值组成的对称阵，仅主对角线上有元素。
• Eckart-Young-Mirsky 定理：给定一个秩为$r$的矩阵$A$，欲求其最优$k$秩的近似矩阵$\hat{A}$，其中$k\leq r$，可以用F范数表示为如下：
  $\min_{\hat{A}\in \mathbb{R}^{m\times n}} \|A - \hat{A}\|_F\\rank(\hat{A})=k.\\rank(A)=r.\\k\leq r$
  对矩阵$A$奇异值分解后$A=U_{m\times m}\sum_{m\times n}V_{n\times n}^T$，仅保留矩阵$\sum$的最大的$k$个奇异值，其他的置0，那么即得到了秩为$k$的矩阵$\hat{A}_k=U\sum_kV^T$，很明显地，矩阵$\hat{A}$即变得稀疏了，秩也低了。

即我们上述的式子$\min_{b_i} \|E_i-b_i\alpha^i\|_F^2$，所以最后相当于只需要对$E_i$进行奇异值分解得到最大奇异值对应的正交向量即可（Eckart-Young-Mirsky 定理）。直接对$E_i$进行奇异值分解会同时修改$b_i$和$\alpha^i$，从而可能破坏原本地稀疏性。K-SVD对$E_i$进行专门处理，$\alpha^i$仅保留非零元素，$E_i$则仅保留$b_i$和$\alpha^i$的乘积项，然后再进行奇异值分解，这样就保持了稀疏性。