Sparse and Low-Rank Representation for Computer Vision — Theory, Algorithms, and Applications

Organizers:  Yi Ma (Microsoft Research Asia, China), John Wright (Columbia University, USA), Allen Y. Yang (UC Berkeley, USA)
Duration: half day
Abstract: The recent vibrant study of sparse representation and compressive sensing has led to numerous groundbreaking results in signal processing and machine learning. In this tutorial, we will present a series of three talks to provide a high-level overview about its theory, algorithms, and broad applications to computer vision and pattern recognition. We will also point out ready-to-use MATLAB toolboxes available for participants to further acquire hands-on experience on these related topics.


  • Session 1: Introduction to Sparse Representation and Low-Rank Representation (Lecturer: John Wright), One Hour.

    This session introduces the basic concepts of sparse representation and low-rank representation. The emphasis will be on how to model and recover low-dimensional structures in high-dimensional signals, and how to verify that the models are appropriate. We will illustrate this process through examples drawn from a number of vision applications. We will gently introduce the foundational theoretical results in this area, and show how theory informs the modeling process.

  • Session 2: Variations of Sparse Representation and Their Numerical Implementation (Lecturer: Allen Yang), One Hour.

    This session discusses several extensions of the basic sparse representation concept, from the original l-1 minimization formulation to group sparsity, Sparse PCA, Robust PCA, and compressive phase retrieval. These variations extend the applications of compressive sensing to multiple-view objection recognition, informative feature selection, and medical imaging. Efficient numerical algorithms are a focus of our discussion, which are responsible for recovering stable estimates of the sparse signals in high-dimensional space. Finally, we briefly discuss how to properly implement the sparsity minimization algorithms on modern many-core CPU/GPU environments.

  •  Session 3: Finding and Harnessing Low-Dimensional Structures of High-dimensional Data (Lecturer: Yi Ma), One Hour.

    This session extends the techniques to enable the analysis of large batches of visual data. We will show how tools and ideas from convex optimization give simple, robust algorithms for recovering low-rank matrices from incomplete, corrupted and noisy observations. Participants will learn how to identify problems for which these tools may be appropriate, and how to apply them effectively to solve practical problems such as robust batch image alignment and the detection of symmetric structures in images. We will illustrate the power and potential of these revolutionary tools in a wide range of applications in computer visions including but not limited to: Face and Text Recognition, Texture Repairing, Video Panorama, Camera Calibration, Holistic Reconstruction of Urban Scenes, etc. Finally, we will show generalizations to the problem of learning sparse codes for large sets of visual data, give example applications.

Material: A website for the tutorial has been created for the participants at:

The tutorial slides will be distributed through the above website prior to the conference. Previously, the proposers have made other related tutorials available on their respective websites. The participants will be provided with the pointers to these webpages. Finally, the participants will be provided with access to a comprehensive set of numerical libraries in MATLAB and C for solving the sparse optimization problems covered in this tutorial.