Skip to content

$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation

Michal Aharon, Michael Elad, Alfred Marcel Bruckstein

IEEE Transactions on Signal Processing · 2006 · 9,544 citations

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Aharon, M., Elad, M., & Bruckstein, A. M. (2006). $rm K$-SVD: An algorithm for designing overcomplete dictionaries for sparse representation. IEEE Transactions on Signal Processing, 54(11), 4311–4322. https://doi.org/10.1109/tsp.2006.881199

In text: (Aharon et al., 2006)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

Abstract

In recent years there has been a growing interest in the study of sparse representation of signals. Using an overcomplete dictionary that contains prototype signal-atoms, signals are described by sparse linear combinations of these atoms. Applications that use sparse representation are many and include compression, regularization in inverse problems, feature extraction, and more. Recent activity in this field has concentrated mainly on the study of pursuit algorithms that decompose signals with respect to a given dictionary. Designing dictionaries to better fit the above model can be done by either selecting one from a prespecified set of linear transforms or adapting the dictionary to a set of training signals. Both of these techniques have been considered, but this topic is largely still open. In this paper we propose a novel algorithm for adapting dictionaries in order to achieve sparse signal representations. Given a set of training signals, we seek the dictionary that leads to the best representation for each member in this set, under strict sparsity constraints. We present a new method-the K-SVD algorithm-generalizing the K-means clustering process. K-SVD is an iterative method that alternates between sparse coding of the examples based on the current dictionary and a process of updating the dictionary atoms to better fit the data. The update of the dictionary columns is combined with an update of the sparse representations, thereby accelerating convergence. The K-SVD algorithm is flexible and can work with any pursuit method (e.g., basis pursuit, FOCUSS, or matching pursuit). We analyze this algorithm and demonstrate its results both on synthetic tests and in applications on real image data

  1. A Computational Approach to Edge Detection1986
  2. Compressed sensing2006
  3. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images1984
  4. Scale-space and edge detection using anisotropic diffusion1990
  5. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems2009

Metadata from OpenAlex (CC0). Citations are generated from the published record.