K-means, K-SVD, LC-KSVD and DPL

August 4, 2015

从 K-means 到 K-SVD¹¹ M. Aharon, M. Elad, and A.M. Bruckstein, “The K-SVD: An Algorithm for Designing of Overcomplete Dictionaries for Sparse Representation”, the IEEE Trans. On Signal Processing, Vol. 54, no. 11, pp. 4311-4322, November 2006. http://www.cs.technion.ac.il/~elad/publications/journals/2004/32_KSVD_IEEE_TSP.pdf²² O. Bryt and M. Elad, Compression of Facial Images Using the K-SVD Algorithm, Journal of Visual Communication and Image Representation, Vol. 19, No. 4, Pages 270-283, May 2008. http://www.cs.technion.ac.il/~elad/publications/journals/2007/FaceCompress_KSVD_JVCIR.pdf³³ R. Rubinstein, T. Peleg and M. Elad, Analysis K-SVD: A Dictionary-Learning Algorithm for the Analysis Sparse Model, IEEE Trans. on Signal Processing, Vol. 61, No. 3, Pages 661-677, March 2013. http://www.cs.technion.ac.il/~elad/publications/journals/2011/Analysis-KSVD-IEEE-TSP.pdf，到 LC-KSVD⁴⁴ Zhuolin Jiang, Zhe Lin, Larry S. Davis. “Label Consistent K-SVD: Learning A Discriminative Dictionary for Recognition”. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(11): 2651-2664. http://www.umiacs.umd.edu/~zhuolin/projectlcksvd.html，到 DPL⁵⁵ Gu, S., Zhang, L., Zuo, W., & Feng, X. (2014). Projective dictionary pair learning for pattern classification. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, & K. Q. Weinberger (Eds.), Advances in Neural Information Processing Systems 27 (pp. 793–801). Curran Associates, Inc. http://papers.nips.cc/paper/5600-spectral-clustering-of-graphs-with-the-bethe-hessian。

K-means 算法

任务：通过最近邻寻找能够表达数据样本 ​$\{\mathbf{y}_i\}^N_{i=1}$ 的最优编码本（codebook，既字典参数），既求解如下问题

​ $$\min_{\mathbf{C, X}} \left\{ \|\mathbf{Y} - \mathbf{CX}\|^2_F \right\} \text{ subject to } \forall i \text{, } \mathbf{x}_i = \mathbf{e}_k \text{ for some } k$$

初始化： 设置编码本矩阵 ​$\mathbf{C}^{(0)} \in \Re^{n \times K}$. 设置 ​$J=1$。

循环至收敛 （使用停止规则）

1. 稀疏编码阶段：将训练样本 ​${\bf Y}$ 分为如下 ​$K$ 个集合。

​ $$\left( \mathbf{R}^{(J-1)}_1, \mathbf{R}^{(J-1)}_2, \cdots, \mathbf{R}^{(J-1)}_K \right)$$

每个集合中存放与 ​${\bf c}^{J-1}_k$ 列最相似的样本的索引。

​ $$\mathbf{R}^{(J-1)}_k = \left\{ i \mid \forall_{l \neq k}, \|\mathbf{y}_i - \mathbf{c}^{(J-1)}_k\|_2 < \|\mathbf{y}_i - \mathbf{c}^{(J-1)}_l\|_2 \right\}$$

2. 编码本更新阶段：​${\bf C}^{(J-1)}$ 中的任一列 ​$k$ 都根据如下公式更新。

​ $${\bf c}^{(J)}_k = \frac{1}{|{\bf R}_k|}\sum_{i \in {\bf R}^{(J-1)}_k}{\bf y}_i$$

3. 令​$J = J + 1$

K-means 相当于是只使用编码本矩阵中的一列的稀疏表达。又因为只有一列，所以系数为1。其中该列由如下公式确定。

​ $$\forall_{k \neq j} \; \left\|{\bf y}_i - {Ce}_j \right\|^2_2 \leqslant \left\|{\bf y}_i - {Ce}_k \right\|^2_2$$

Julia Code Highlight Test

include("diagadd!.jl")

function updateA!(A::Array{Any,1}, 
                  D::Array{Any,1}, 
                  DataMat::Array{Any,1}, 
                  P::Array{Any,1}, 
                  τ::Float64, 
                  DictSize::Int64)
    # Update tempDictCoef by Eq. (8)

    for i=1:length(A)
        @inbounds TempDict::Matrix{Float64} = D[i]
        @inbounds TempData::Matrix{Float64} = DataMat[i]
        tempDictCoef::Matrix{Float64}       = TempDict' * TempDict
        tempDictDataCoef::Matrix{Float64}   = TempDict' * TempData
        @inbounds C::Matrix{Float64}        = P[i] * TempData
        diagadd!(tempDictCoef, τ)
        fma!(tempDictDataCoef, C, τ)
        @inbounds A[i]                      = tempDictCoef \ tempDictDataCoef
    end
end