Home     MCADS Lab     Research     Publications     Activities     Codes     Data     Teaching

Sparse and Low-Rank Modeling for High-Dimensional Data Analysis

Tutorial at CVPR 2015
June 7th, 2:00 pm - 6:00 pm
Room 203, Hynes Convention Center, Boston, MA


Ehsan Elhamifar, Guillermo Sapiro, Rene Vidal, John Wright

Ehsan    Guillermo    Rene    John   


The increasing amounts of high-dimensional data in computer vision and other science and engineering fields, requires robust tools and techniques for recovering the underlying low-dimensional structures in the data. Subspace methods are important for solving numerous problems in machine learning, pattern recognition and computer vision. While subspace methods have been studied intensively (from PCA and beyond), new results have recently emerged from the areas of sparse coding, matrix factorization and matrix completion. These results, in contrast with more classical subspace learning approaches, deal with multiple subspaces, of varying dimensions, and data nuisances, such as noise, outliers and missing entries. This makes these class of models non-linear and extremely rich. Applications of such methods range from computer vision (motion estimation, video analysis, scene/face recognition, etc) to data mining (collaborative filtering, web-data analysis, etc). The goal of this tutorial is to present the audience with a unifying perspective of this problem, introducing the basic concepts and connecting low-dimensional subspace methods with sparse modeling, matrix factorization, and dimensionality reduction. The presentation of the theoretical foundations will be complemented with applications in computer vision including motion segmentation, face recognition, registration, active learning, video summarization, and more.


  1. Ehsan Elhamifar: Introduction, Sparse Subspace Clustering, Sparse Subset Selection PDF

  2. John Wright: Theory of Sparse and Low-Rank Recovery PDF

  3. Rene Vidal: Subspace Clustering Algorithms PDF

  4. Guillermo Sapiro, Qiang Qiu: Learning Low-Rank Transformations PDF


  1. Introduction and tutorial overview

  2. Robust Principal Component Analysis

    • Low-dimensional models in high-dimensional data

    • Low-rank modeling for finding and harnessing low-dimensional structure of data

    • Robust PCA: algorithm and theory

    • Applications in robust batch image alignment, detection of symmetric structures in images, background subtraction, texture repairing, etc.

  3. Subspace Clustering via Sparse and Low-Rank Modeling

    • Union of subspace models in computer vision

    • Sparse Subspace Clustering: algorithm, theory, extensions

    • Low-rank Subspace Clustering algorithm

    • Applications to video segmentation, face and activity clustering, motion segmentation, etc.

  4. Subset Selection and Dataset Summarization via Simultaneous Sparse Recovery

    • Subset selection in low-dimensional models using self-expressiveness property

    • Sparse subset selection using pairwise similarities

    • Applications to video summarization, active learning, learning nonlinear dynamical models, activity clustering, image classification, etc.

  5. Learning Low-Rank Transformations

    • Subspace transform learning algorithms

    • Theory of subspace transform learning algorithms

    • Connections with random forests and deep learning, and applications


The intended audience are academicians, graduate students and industrial researchers who are interested in the state-of-the-art data modeling and machine learning techniques for the modeling and analysis of high-dimensional data that are considered to be mixed, multi-modal, inhomogeneous, heterogeneous, or hybrid. Audience with mathematical and theoretical inclination will enjoy the course as much as the audience with practical tendency.


  • Ehsan Elhamifar is currently a postdoctoral scholar in the department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. He will be an Assistant Professor of Computer Science at Northeastern University. He obtained his PhD in Electrical and Computer Engineering from the Johns Hopkins University. Ehsan is broadly interested in developing provably correct and efficient data analysis algorithms that can address challenges of complex and large-scale high-dimensional datasets. Specifically, he focuses on the intrinsic low-dimensionality of real data and uses tools from convex geometry and analysis, sparse / low-rank representation, high-dimensional statistics and graph theory to develop such algorithms. Ehsan obtained MS and MSE degrees in Electrical Engineering and Applied Mathematics and Statistics, respectively, from Sharif University of Technology in Iran and the Johns Hopkins University.

  • Guillermo Sapiro is a Professor in the Electrical and Computer Engineering Department at Duke University. He received his Ph.D. degrees from the Department of Electrical Engineering, The Technion–Israel Institute of Technology, Haifa, in 1993. After postdoctoral research at the Massachusetts Institute of Technology, Cambridge, he became a Member of Technical Staff at the research facilities of HP Labs, Palo Alto, CA. He was with the Department of Electrical and Computer Engineering at the University of Minnesota, where he held the position of Distinguished McKnight University Professor and Vincentine Hermes-Luh Chair in Electrical and Computer Engineering. Currently he is with Duke University. He is the founding Editor-in-Chief of the SIAM Journal on Imaging Sciences, currently ranked as the second highest impact journal in the whole discipline of applied mathematics. 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 postdoctoral 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.

  • Rene Vidal is an Associate Professor in the Biomedical Engineering Department at Johns Hopkins University. He received his M.S. and Ph.D. degrees in Electrical Engineering and Computer Sciences from the University of California at Berkeley in 2000 and 2003, respectively. Dr. Vidal is Associate Editor of the IEEE Transactions on Pattern Analysis and Machine Intelligence, the SIAM Journal on Imaging Sciences and the Journal of Mathematical Imaging and Vision. He was or will be program chair for ICCV 2015, CVPR 2014, WMVC 2009, and PSIVT 2007. Dr. Vidal is recipient of numerous awards for his work, including the 2012 J.K. Aggarwal Prize for “outstanding contributions to generalized principal component analysis (GPCA) and subspace clustering in computer vision and pattern recognition”, the 2012 Best Paper Award in Medical Robotics and Computer Assisted Interventions, the 2011 Best Paper Award Finalist at the Conference on Decision and Control, the 2009 ONR Young Investigator Award, the 2009 Sloan Research Fellowship, the 2005 NFS CAREER Award and the 2004 Best Paper Award Honorable Mention at the European Conference on Computer Vision. He is a fellow of the IEEE and a member of the ACM.

  • John Wright is an Assistant Professor in the Electrical Engineering Department at Columbia University. He received his PhD in Electrical Engineering from the University of Illinois at Urbana-Champaign in October 2009, and was with Microsoft Research from 2009-2011. His research is in the area of high-dimensional data analysis. In particular, his recent research has focused on developing algorithms for robustly recovering structured signal representations from incomplete and corrupted observations, and applying them to practical problems in imaging and vision. His work has received an number of awards and honors, including the 2009 Lemelson-Illinois Prize for Innovation for his work on face recognition, the 2009 UIUC Martin Award for Excellence in Graduate Research, and a 2008-2010 Microsoft Research Fellowship.