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 algorithm

edit

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  .

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  , the sparsity term of the constraint is relaxed so that the number of nonzero entries of each column   can be more than 1, but less than a number  .

So, the objective function becomes

 

or in another objective form

 

In the k-SVD algorithm, the   is first fixed and the best coefficient matrix   is found. As finding the truly optimal   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   each time, while fixing  . The update of the  -th column is done by rewriting the penalty term as

 

where   denotes the k-th row of X.

By decomposing the multiplication   into sum of   rank 1 matrices, we can assume the other   terms are assumed fixed, and the  -th remains unknown. After this step, we can solve the minimization problem by approximate the   term with a   matrix using singular value decomposition, then update   with it. However, the new solution for the vector   is not guaranteed to be sparse.

To cure this problem, define   as

 

which points to examples   that use atom   (also the entries of   that is nonzero). Then, define   as a matrix of size  , with ones on the   entries and zeros otherwise. When multiplying  , this shrinks the row vector   by discarding the zero entries. Similarly, the multiplication   is the subset of the examples that are current using the   atom. The same effect can be seen on  .

So the minimization problem as mentioned before becomes

 

and can be done by directly using SVD. SVD decomposes   into  . The solution for   is the first column of U, the coefficient vector   as the first column of  . After updating the whole dictionary, the process then turns to iteratively solve X, then iteratively solve D.

Limitations

edit

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]

See also

edit

References

edit
  1. ^ Michal Aharon; Michael Elad; Alfred Bruckstein (2006), "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation" (PDF), IEEE Transactions on Signal Processing, 54 (11): 4311–4322, Bibcode:2006ITSP...54.4311A, doi:10.1109/TSP.2006.881199, S2CID 7477309
  2. ^ a b c Rubinstein, R., Bruckstein, A.M., and Elad, M. (2010), "Dictionaries for Sparse Representation Modeling", Proceedings of the IEEE, 98 (6): 1045–1057, CiteSeerX 10.1.1.160.527, doi:10.1109/JPROC.2010.2040551, S2CID 2176046{{citation}}: CS1 maint: multiple names: authors list (link)