K-SVD

k-SVD is a kind of generalization of k-means, as follows. The k-means clustering can be also regarded as a method of sparse representation. That is, finding the best possible codebook to represent the data samples $\backslash \{y\_i\backslash \}^M\_\{i=1\}$ by nearest neighbor, by solving

:$$

\quad \min \limits _{D, X} \{ \|Y - DX\|^2_F\} \qquad \text{subject to } \forall i, x_i = e_k \text{ for some } k.

which is nearly equivalent to

:$$

\quad \min \limits _{D, X} \{ \|Y - DX\|^2_F\} \qquad \text{subject to }\quad \forall i , \|x_i\|_0 = 1

which is k-means that allows "weights".

The letter F denotes the Frobenius norm. The sparse representation term $x\_i\; =\; e\_k$ enforces k-means algorithm to use only one atom (column) in dictionary $D$. To relax this constraint, the target of the k-SVD algorithm is to represent the signal as a linear combination of atoms in $D$.

The k-SVD algorithm follows the construction flow of the k-means algorithm. However, in contrast to k-means, in order to achieve a linear combination of atoms in $D$, the sparsity term of the constraint is relaxed so that the number of nonzero entries of each column $x\_i$ can be more than 1, but less than a number $T\_0$.

So, the objective function becomes

:$$

\quad \min \limits _{D, X} \{ \|Y - DX\|^2_F \} \qquad \text{subject to } \quad \forall i \;, \|x_i\|_0 \le T_0.

or in another objective form

:$$

\quad \min \limits _{D, X} \sum_{i} \|x_i\|_0 \qquad \text{subject to } \quad \forall i \;, \|Y - DX\|^2_F \le \epsilon.

In the k-SVD algorithm, the $D$ is first fixed and the best coefficient matrix $X$ is found. As finding the truly optimal $X$ is hard, we use an approximation pursuit method. Any algorithm such as OMP, the orthogonal matching pursuit can be used for the calculation of the coefficients, as long as it can supply a solution with a fixed and predetermined number of nonzero entries $T\_0$.

After the sparse coding task, the next is to search for a better dictionary $D$. However, finding the whole dictionary all at a time is impossible, so the process is to update only one column of the dictionary $D$ each time, while fixing $X$. The update of the $k$-th column is done by rewriting the penalty term as

:$$

\|Y - DX\|^2_F = \left\| Y - \sum_{j = 1}^K d_j x^\text{T}_j\right\|^2_F = \left\| \left(Y - \sum_{j \ne k} d_j x^\text{T}_j \right) - d_k x^\text{T}_k \right\|^2_F = \| E_k - d_k x^\text{T}_k\|^2_F

where $x\_k^\backslash text\{T\}$ denotes the k-th row of X.

By decomposing the multiplication $DX$ into sum of $K$ rank 1 matrices, we can assume the other $K-1$ terms are assumed fixed, and the $k$-th remains unknown. After this step, we can solve the minimization problem by approximate the $E\_k$ term with a $rank\; -1$ matrix using singular value decomposition, then update $d\_k$ with it. However, the new solution for the vector $x^\backslash text\{T\}\_k$ is not guaranteed to be sparse.

To cure this problem, define $\backslash omega\_k$ as

:$$

\omega_k = \{i \mid 1 \le i \le N , x^\text{T}_k(i) \ne 0\},

which points to examples $\backslash \{\; y\_i\; \backslash \}\_\{i=1\}^N$ that use atom $d\_k$ (also the entries of $x\_i$ that is nonzero). Then, define $\backslash Omega\_k$ as a matrix of size $N\backslash times|\backslash omega\_k|$, with ones on the $(i,\backslash omega\_k(i))\backslash text\{th\}$ entries and zeros otherwise. When multiplying $\backslash tilde\{x\}^\backslash text\{T\}\_k\; =\; x^\backslash text\{T\}\_k\backslash Omega\_k$, this shrinks the row vector $x^\backslash text\{T\}\_k$ by discarding the zero entries. Similarly, the multiplication $\backslash tilde\{Y\}\_k\; =\; Y\backslash Omega\_k$ is the subset of the examples that are current using the $d\_k$ atom. The same effect can be seen on $\backslash tilde\{E\}\_k\; =\; E\_k\backslash Omega\_k$.

So the minimization problem as mentioned before becomes

:$$

\| E_k\Omega_k - d_k x^\text{T}_k\Omega_k\|^2_F = \| \tilde{E}_k - d_k \tilde{x}^\text{T}_k\|^2_F

and can be done by directly using SVD. SVD decomposes $\backslash tilde\{E\}\_k$ into $U\backslash Delta\; V^\backslash text\{T\}$. The solution for $d\_k$ is the first column of U, the coefficient vector $\backslash tilde\{x\}^\backslash text\{T\}\_k$ as the first column of $V\; \backslash times\; \backslash Delta\; (1,\; 1)$. After updating the whole dictionary, the process then turns to iteratively solve X, then iteratively solve D.

Choosing an appropriate "dictionary" for a dataset is a non-convex problem, and k-SVD operates by an iterative update which does not guarantee to find the global optimum. However, this is common to other algorithms for this purpose, and k-SVD works fairly well in practice.{{better source|date=May 2014}}

• Sparse approximation
• Singular value decomposition
• Matrix norm
• k-means clustering
• Low-rank approximation

{{DISPLAYTITLE:k-SVD}}

Category:Norms (mathematics)

Category:Linear algebra

Category:Cluster analysis algorithms