Tutorial on Sparse Coding and Dictionary Learning for Image Analysis, CVPR 2010

General Information


A few years after this tutorial was given, the following monograph was published. It contains most of the material of the tutorial and is self-content.




Monday 14th, June 2010, Afternoon


4 hours

Short Description

Sparse coding calls for modelling data vectors as a linear combination of a few elements from a dictionary. Whereas the question of -designing- the best dictionary adapted to natural signals has been the topic of much research in the past, this tutorial focuses on recent techniques that -learn- the basis set from training data. This has already proven very effective for signal reconstruction, leading to state-of-the-art results for many signal or image processing tasks, as well as advances in computer vision tasks such as object recognition.

A critical component in this approach is how to sparsely encode a signal given the dictionary. The tutorial will describe the state of the art in this area, ranging from greedy algorithms and l1-optimization to simultaneous sparse coding of collections of signals. The actual dictionary plays a critical role, and it has been shown once and again that learned dictionaries significantly outperforms off-the-shelf ones such as wavelets. The second part of this tutorial will present the dictionary learning formulation and its links with existing matrix factorization techniques, as well as state-of-the-art applications to image processing tasks. The third part of the tutorial will be devoted to the most recent advances in the field, starting from learning dictionaries of image descriptors, a strategy used by the latest PASCAL VOC'09 challenge winners, to task-driven dictionaries and structured sparsity.

A similar tutorial was given at ICCV'09 in Kyoto, and its success prompts us to hold a second tutorial at CVPR'2010, with updates and new material.

Preliminary Syllabus

Course Material and Software

A Matlab toolbox for sparse decomposition and dictionary learning is available here.

The slides will all be available soon.

Relevant References

Among the vast literature on sparse coding, here are a few selected publications. The list is preliminary and subject to modifications:


Francis Bach is a researcher in the Willow INRIA project-team, in the Computer Science Department of the Ecole Normale Supérieure, Paris, France. He graduated from the Ecole Polytechnique, Palaiseau, France, in 1997, and earned his PhD in 2005 from the Computer Science division at the University of California, Berkeley. His research interests include machine learning, statistics, optimization, graphical models, kernel methods, sparse methods and statistical signal processing.

Julien Mairal received the graduate degree from Ecole Polytechnique and Ecole Nationale Supérieure des Téléecommunications, Paris, and the MS degree from the Ecole Normale Supérieure, Cachan. He is currently pursuing the Ph.D. degree under the supervision of Jean Ponce and Francis Bach at Ecole Normale Supérieure, Paris. His research interests include machine learning, computer vision and image processing.

Jean Ponce is a computer science professor at Ecole Normale Supérieure (ENS) in Paris, France, where he heads the joint ENS/INRIA/CNRS oject-team WILLOW. Before joining ENS, he spent most of his career in the US, with positions at MIT, Stanford, and the University of Illinois at Urbana-Champaign, where he was a full professor until 2005. Jean Ponce is the author of over 120 technical publications in computer vision and robotics, including the textbook ``Computer Vision: A Modern Approach'', which has been translated in Chinese, Japanese, and Russian. He is an IEEE Fellow, served as editor-in-chief for the International Journal of Computer Vision from 2003 to 2008, and chaired the IEEE Conference on Computer Vision and Pattern Recognition in 1997 and 2000, and the European Conference on Computer Vision in 2008.

Guillermo Sapiro was born in Montevideo, Uruguay, on April 3, 1966. He received his B.Sc. (summa cum laude), M.Sc., and Ph.D. from the Department of Electrical Engineering at the Technion, Israel Institute of Technology, in 1989, 1991, and 1993 respectively. After post-doctoral research at MIT, Dr. Sapiro became Member of Technical Staff at the research facilities of HP Labs in Palo Alto, California. He is currently with the Department of Electrical and Computer Engineering at the University of Minnesota, where he holds the position of Distinguished McKnight University Professor and Vincentine Hermes-Luh Chair in Electrical and Computer Engineering. He works on differential geometry and geometric partial differential equations, both in theory and applications in computer vision, computer graphics, medical imaging, and image analysis. He recently co-edited a special issue of IEEE Image Processing in this topic and a second one in the Journal of Visual Communication and Image Representation. He has authored and co-authored numerous papers in this area and has written a book published by Cambridge University Press, January 2001. He was awarded the Gutwirth Scholarship for Special Excellence in Graduate Studies in 1991, the Ollendorff Fellowship for Excellence in Vision and Image Understanding Work in 1992, the Rothschild Fellowship for Post-Doctoral Studies in 1993, the Office of Naval Research Young Investigator Award in 1998, the Presidential Early Career Awards for Scientist and Engineers (PECASE) in 1998, and the National Science Foundation Career Award in 1999. He is the funding Editor-in-Chief of the SIAM Journal on Imaging Sciences.