COURSE DESCRIPTION:  Due to their wide applicability, sparse and low-rank models have quickly become some of the most important tools for today’s researchers in machine learning, statistics, optimization, bioinformatics, computer vision, as well as signal and image processing. Application areas in which sparse and low-rank modelling tools have been applied span a wide range of topics in these fields including: clustering, object recognition and classification, regularized regression, face recognition, Robust Principle Component Analysis, Deep Learning feature selection, Collaborative Filtering, Natural Language Processing, compressive sensing, as well as image/video inpainting, super-resolution, and denoising.

With this 495 topics class we want to help quickly bring interested students and researchers from this wide array of disciplines up to speed on the power and wide applicability of sparse and low-rank models. The ultimate aim of the course is to equip you with all the modeling and optimization tools you’ll need in order to formulate and solve problems of interest using sparse and low-rank tools. We hope to help build these skills through lectures and reading materials which introduce sparse and low-rank recovery problems in the context of its many applications, as well as by describing in a detailed but user-friendly manner the modern techniques from nonlinear optimization used to solve them. In addition to a well curated collection of reference materials, registered students will receive a draft of a forthcoming manuscript authored by the instructors on sparse and low rank models and algorithms to use as class notes.

COURSE INSTRUCTORS: Prof. Aggelos Katsaggelos and Jeremy Watt

Tentative course outline:

  1. Sparse and low rank model prototypes: Least Squares and Principal Component Analysis
    1. Least Squares: applications where sparsity naturally arises
    2.      i. Applications in feature selection, compression, neuroscience, and compressive sensing
    3. Principal Component Analysis: the mother of all low-rank matrix approximation problems
    4.      i. Applications in clustering, Collaborative Filtering, finance, and video analysis
  2. Algorithms for solving sparse and low-rank recovery problems
      1. Greedy algorithms for large scale sparse recovery problems
      2.      i. Orthogonal Matching Pursuit and related methods
      3. Review of essential tools
      4.      i. Linear algebra: eigen and singular values/vectors

             ii. Geometry: orthogonal projections, convexity

           iii. Optimization: (projected) gradient descent, Newton’s method, constrained problem

                   c.               Smooth reformulations for small to medium sized sparse and low-rank problems 
                   d.              Nonlinear optimization techniques for large scale sparse and low-rank problems   
                       i. Accelerated Proximal Gradient Methods
                       ii. Alternating Direction Method of Multipliers

PREREQUISITES: A basic understanding of Linear Algebra and Calculus is required. Previous exposure to the basics of nonlinear optimization is helpful, but not required (concepts needed from optimization will be introduced as needed throughout the course)

COURSE HAND-OUTS: This course is based on a forthcoming book and a preprint of the relevant chapters will be made available to students.

PROBLEM SETS: Students will be responsible for completing a term project based on the topics covered in the course. Projects can include but are not limited to: an application of course ideas to a novel problem of interest to the student, a relevant literature survey, or an implementation and comparison of several algorithms from the course. Students are encouraged to work in groups of up to 3.

EXAMS: There will be no exams in this course.

TERM PROJECT: Students will be responsible for completing a term project based on the topics covered in the course.  Projects can include but are not limited to: an application of course ideas to a novel problem of interest to the student, a relevant literature survey, or an implementation and comparison of several algorithms from the course.  Students are encouraged to work in groups of up to 3.

GRADES: Final grades for the course will be assigned using the following weights

  • Problem sets……...40%
  • Term project……...60%

REFERENCE TEXTS: The forthcoming book on which the course is based will serve as the main reference text.  Some other important references include:

  • Aharon, M. and Elad, M. and Bruckstein, A., "K-SVD An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation", Signal Processing, IEEE Transactions on (2006), 4311--4322.
  • Beck, A. and Teboulle, M., "A fast iterative shrinkage-thresholding algorithm for linear inverse problems", SIAM Journal on Imaging Sciences 2, 1 (2009), pp. 183--202.
  • Boyd, Stephen and Parikh, Neal and Chu, Eric and Peleato, Borja and Eckstein, Jonathan, "Distributed optimization and statistical learning via the alternating direction method of multipliers", Foundations and Trends® in Machine Learning 3, 1 (2011), pp. 1--122.
  • Wright, J. and Yang, A.Y. and Ganesh, A. and Sastry, S.S. and Ma, Y., "Robust face recognition via sparse representation", Pattern Analysis and Machine Intelligence, IEEE Transactions on 31, 2 (2009), pp. 210--227.