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.
[1][2] k-SVD can be found widely in use in applications such as image processing, audio processing, biology, and document analysis.
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
by nearest neighbor, by solving which is nearly equivalent to which is k-means that allows "weights".
The letter F denotes the Frobenius norm.
The sparse representation term
enforces k-means algorithm to use only one atom (column) in dictionary
To relax this constraint, the target of the k-SVD algorithm is to represent the signal as a linear combination of atoms in
However, in contrast to k-means, in order to achieve a linear combination of atoms in
, the sparsity term of the constraint is relaxed so that the number of nonzero entries of each column
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
After the sparse coding task, the next is to search for a better dictionary
However, finding the whole dictionary all at a time is impossible, so the process is to update only one column of the dictionary
-th column is done by rewriting the penalty term as where
denotes the k-th row of X.
rank 1 matrices, we can assume the other
terms are assumed fixed, and the
After this step, we can solve the minimization problem by approximate the
matrix using singular value decomposition, then update
To cure this problem, define
, this shrinks the row vector
is the subset of the examples that are current using the
So the minimization problem as mentioned before becomes and can be done by directly using SVD.
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.