K-SVD for Dummies: An Introduction to Sparse Representation and the K-SVD Algorithmy

 Sparse representation in redundant dictionaries is a hot topic in modern signal processing, with a wealth of recent achievements and state-of-the-art results for many problems. The basic idea is that natural signals can be efficiently modeled as linear combinations of pre-specified "atom signals" (the dictionary), where the linear coefficients are sparse - most of them zero.
The model is simple and powerful, yet raises many question: Is the representation problem solvable and under what conditions? What are these "atom signals" and how do we find them? And of course, how does all this help us solve practical image processing problems? In this lecture we discuss the sparsity model, explore some of the basic results in the field, and present the K-SVD algorithm for training redundant dictionaries. Some applications we will discuss include denoising, image inpainting, and compression.