K-SVD

K-SVD is a dictionary learning algorithm from applied mathematics. Its job is to build a dictionary that lets data be written as a sparse combination of a few of its entries, called atoms, and it does this with a singular value decomposition approach. It generalizes the k-means clustering method: where k-means lets each sample use exactly one dictionary column, K-SVD relaxes that limit so each sample may use several atoms, up to a chosen bound on the number of nonzero entries, and the fit is measured with the Frobenius norm of the reconstruction error. The method alternates two steps. First it sparse-codes the input data against the current dictionary, then it updates the atoms one at a time so the dictionary fits the data better, applying a singular value decomposition to the residual of only those examples that actually use the atom being updated. It is structurally related to the expectation-maximization algorithm. K-SVD is widely used in image processing, audio processing, biology and document analysis. Its limits are stated plainly: choosing a dictionary is a non-convex problem and the iterative update does not guarantee the global optimum, although it works fairly well in practice.