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. 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_1 by nearest neighbor, by solving which is equivalent to The letter F denotes the Frobenius norm. The sparse representation term formula_4 enforces K-means algorithm to use only one atom (column) in dictionary formula_5. To relax this constraint, the target of the K-SVD algorithm is to represent signal as a linear combination of atoms in formula_5. 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_5, the sparsity term of the constraint is relaxed so that the number of nonzero entries of each column formula_8 can be more than 1, but less than a number formula_9. So, the objective function becomes or in another objective form In the K-SVD algorithm, the formula_5 is first fixed and the best coefficient matrix formula_13 is found. As finding the truly optimal formula_13 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_9. After the sparse coding task, the next is to search for a better dictionary formula_5. However, finding the whole dictionary all at a time is impossible, so the process is to update only one column of the dictionary formula_5 each time, while fixing formula_13. The update of the formula_19-th column is done by rewriting the penalty term as where formula_21 denotes the "k"-th row of "X". By  decomposing the multiplication formula_22 into sum of formula_23 rank 1 matrices, we can assume the other formula_24 terms are assumed fixed, and the formula_19-th remains unknown. After this step, we can solve the minimization problem by approximate the formula_26 term with a formula_27 matrix using singular value decomposition, then update formula_28 with it. However, the new solution of vector formula_29 is very likely to be filled, because the sparsity constraint is not enforced. To cure this problem, Define formula_30 as which points to examples formula_32 that use atom formula_28 (also the entries of formula_8 that is nonzero). Then, define  formula_35 as a matrix of size formula_36, with ones on the formula_37 entries and zeros otherwise. When multiplying formula_38, this shrinks the row vector formula_29 by discarding the zero entries. Similarly, the multiplication formula_40 is the subset of the examples that are current using the formula_28 atom. The same effect can be seen on formula_42. So the minimization problem as mentioned before becomes and can be done by directly using SVD. SVD decomposes formula_44 into formula_45. The solution for formula_28 is the first column of U, the coefficient vector formula_47 as the first column of formula_48. 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.