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


What we have here is an article entitled K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation. Its authors are Michal Aharon, Michael Elad, and Alfred Bruckstein and it was taken from IEEE TRANSACTIONS ON SIGNAL PROCESSING,it has been published on 11, NOVEMBER 2006. At first we are going to talk about the context of the work and This part will explain the scientific context of this article then in another section called Positioning we will detail what are the existing works on the subject of designing Dictionaries. For the tow others sections Contributions and Experiments we are going to present the contribution,the experiments and the validations that are shown in the article. The last section concludes this works.

Context of the work

Sparse representation has attracted much attention from researchers in fields of signal processing, image processing, computer vision, and pattern recognition. It also has a good reputation in both theoretical research and practical applications. Its application are many including compression, regularization in inverse problems, feature extraction, and more. In this article they propose a novel algorithm for adapting dictionaries in order to achieve sparse signal representations. 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.


In this section we have to deal with tow parts SPARSE CODING and DESIGN OF DECTIONARIES. The sparse coding is a necessary stage in the K-SVD method and in the past decade several efficient pursuit algorithms have been proposed, such as orthogonal mathching poursuit (OMP) algorithme ,the basis poursuit (BP) and The focal underdetermined system solver (FOCUSS). And for DESIGN OF DICTIONARIES it represent the main topic of the paper, the K-SVD algorithm is a generalization of the K-means algorithm wish is the most commonly used procedure for training in the vector quantization setting, it is natural to consider generalizations of this algorithm when turning to the problem of dictionary training. We have also the Maximum Likelihood Methods, The MOD Method, the Maximum A-Posteriori Probability Approach and the Unions of Orthonormal Bases Almost all previous methods can essentially be interpreted as generalizations of the K-means algorithm, and yet, there are marked differences between these procedures. And to obtain a successful dictionary training algorithm, there are several desirable properties:

  • Flexibility

  • Simplicity

  • Efficiency

  • Well-Defined Objective


The K-SVD is an iterative method that alternates between sparse coding of the examples based on the current dictionary and an update process for the dictionary atoms so as to better fit the data. This algorithm is fast it’s using a method that accelerate the convergence. The K-SVD algorithm is flexible and can work with any pursuit method.


To test and to prove the good performance of the K-SVD algorithm they used at first synthetic experiments by using a random matrix and applying different algorithm and that proved a superiority to other algorithms. Then in this article they present applications of the algorithm to Image Processing, filling in missing pixels and compression and many presented figures show the efficiency of the K-SVD algorithm.


In this article, the presented K-SVD algorithm cope with the problem of generating dictionaries by training them following those experiments such as filling in missing pixels and compression the K-SVD algorithm outperforms alternatives, and may successfully replace popular representation methods both in image enhancement and in compression. But still a future work required to improve this algorithm.

[Someone else is editing this]

You are editing this file