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 ${\displaystyle \{y_{i}\}_{i=1}^{M}}$  by nearest neighbor, by solving

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.}$ 

which is nearly equivalent to

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\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 ${\displaystyle x_{i}=e_{k}}$  enforces k-means algorithm to use only one atom (column) in dictionary ${\displaystyle D}$ . To relax this constraint, the target of the k-SVD algorithm is to represent the signal as a linear combination of atoms in ${\displaystyle 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 ${\displaystyle D}$ , the sparsity term of the constraint is relaxed so that the number of nonzero entries of each column ${\displaystyle x_{i}}$  can be more than 1, but less than a number ${\displaystyle T_{0}}$ .

So, the objective function becomes

${\displaystyle \quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.}$ 

or in another objective form

${\displaystyle \quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .}$ 

In the k-SVD algorithm, the ${\displaystyle D}$  is first fixed and the best coefficient matrix ${\displaystyle X}$  is found. As finding the truly optimal ${\displaystyle 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 ${\displaystyle T_{0}}$ .

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

${\displaystyle \|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\sum _{j\neq k}d_{j}x_{j}^{\text{T}}\right)-d_{k}x_{k}^{\text{T}}\right\|_{F}^{2}=\|E_{k}-d_{k}x_{k}^{\text{T}}\|_{F}^{2}}$ 

where ${\displaystyle x_{k}^{\text{T}}}$  denotes the k-th row of X.

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

To cure this problem, define ${\displaystyle \omega _{k}}$  as

${\displaystyle \omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{\text{T}}(i)\neq 0\},}$ 

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

So the minimization problem as mentioned before becomes

${\displaystyle \|E_{k}\Omega _{k}-d_{k}x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{\text{T}}\|_{F}^{2}}$ 

and can be done by directly using SVD. SVD decomposes ${\displaystyle {\tilde {E}}_{k}}$  into ${\displaystyle U\Delta V^{\text{T}}}$ . The solution for ${\displaystyle d_{k}}$  is the first column of U, the coefficient vector ${\displaystyle {\tilde {x}}_{k}^{\text{T}}}$  as the first column of ${\displaystyle V\times \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.^[2] However, this is common to other algorithms for this purpose, and k-SVD works fairly well in practice.^{[2][better source needed]}

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