K-SVD

In applied mathematics, K-SVD is a dictionary learning algorithm for creating a dictionary for sparse representations, via a singular value decomposition approach. K-SVD is a generalization of the k-means clustering method, and it works by iteratively alternating between sparse coding the input data based on the current dictionary, and updating the atoms in the dictionary to better fit the data. It is structurally related to the expectation maximization (EM) algorithm. K-SVD can be found widely in use in applications such as image processing, audio processing, biology, and document analysis.
Problem description.
The goal of dictionary learning is to learn an overcomplete dictionary matrix formula_1 that contains formula_2 signal-atoms (in this notation, columns of formula_3). A signal vector formula_4 can be represented, sparsely, as a linear combination of these atoms; to represent formula_5, the representation vector formula_6 should satisfy the exact condition formula_7, or the approximate condition formula_8, made precise by requiring that formula_9 for some small value and some norm. The vector formula_10 contains the representation coefficients of the signal formula_5. Typically, the norm formula_12 is selected as , , or .
If formula_13 and D is a full-rank matrix, an infinite number of solutions are available for the representation problem. Hence, constraints should be set on the solution. Also, to ensure sparsity, the solution with the fewest nonzero coefficients is preferred. Thus, the sparsity representation is the solution of either
or
where the formula_16 counts the nonzero entries in the vector formula_6. (See the zero "norm".)
K-SVD algorithm.
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 formula_18 by nearest neighbor, by solving
which is equivalent to
The letter F denotes the Frobenius norm. The sparse representation term formula_21 enforces K-means algorithm to use only one atom (column) in dictionary formula_3. To relax this constraint, the target of the K-SVD algorithm is to represent signal as a linear combination of atoms in formula_3.
The K-SVD algorithm follows the construction flow of the K-means algorithm. However, in contrary to K-means, in order to achieve a linear combination of atoms in formula_3, the sparsity term of the constraint is relaxed so that the number of nonzero entries of each column formula_25 can be more than 1, but less than a number formula_26.
So, the objective function becomes
or in another objective form
In the K-SVD algorithm, the formula_3 is first fixed and the best coefficient matrix formula_30 is found. As finding the truly optimal formula_30 is impossible, 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 formula_26.
After the sparse coding task, the next is to search for a better dictionary formula_3. However, finding the whole dictionary all at a time is impossible, so the process is to update only one column of the dictionary formula_3 each time, while fixing formula_30. The update of the formula_36-th column is done by rewriting the penalty term as 
where formula_38 denotes the "k"-th row of "X".
By decomposing the multiplication formula_39 into sum of formula_2 rank 1 matrices, we can assume the other formula_41 terms are assumed fixed, and the formula_36-th remains unknown. After this step, we can solve the minimization problem by approximate the formula_43 term with a formula_44 matrix using singular value decomposition, then update formula_45 with it. However, the new solution of vector formula_38 is very likely to be filled, because the sparsity constraint is not enforced.
To cure this problem, Define formula_47 as
which points to examples formula_49 that use atom formula_45 (also the entries of formula_25 that is nonzero). Then, define formula_52 as a matrix of size formula_53, with ones on the formula_54 entries and zeros otherwise. When multiplying formula_55, this shrinks the row vector formula_56 by discarding the zero entries. Similarly, the multiplication formula_57 is the subset of the examples that are current using the formula_45 atom. The same effect can be seen on formula_59.
So the minimization problem as mentioned before becomes 
and can be done by directly using SVD. SVD decomposes formula_61 into formula_62. The solution for formula_45 is the first column of U, the coefficient vector formula_64 as the first column of formula_65. After updating the whole dictionary, the process then turns to iteratively solve X, then iteratively solve D.
Limitations.
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.