CO 769: Topics in Continuous Optimization

Recent Advances in Compressive Sensing, l1 Minimization and Rank Minimization

Meeting time

Tuesdays and Thursdays, 11:30--12:50, MC 5045

Instructor

S. Vavasis
MC 6054
519-888-4567 ext. 32130
Email: vavasis@math.uwaterloo.ca
Office hours: Tuesdays and Thursdays 1:00-2:30.

Compressive sensing

Compressive sensing was introduced independently by Candès, Romberg and Tao (2006) and Donoho (2006) and has attracted a considerable amount of attention from the signal processing, statistical, computer science and optimization communities. An earlier paper by Gilbert, Guha, Indyk, Muthukrishnan and Strauss (2002) also anticipated the results. The main result in this field states that a signal (i.e., a vector), if it is sufficiently sparse, can be recovered exactly from its inner product with a small number of random vectors. The recovery algorithm is l1 minimization, which is equivalent to linear programming. In general, recovery of the sparsest solution to linear equations is NP-hard, but in this special (and practically applicable) case, recovery can be solved in polynomial time. Specialized algorithms for l1 minimization have been around for many years in the optimization community. In the statistics community, l1 minimization is known as a data-fitting technique that is sometimes more robust than linear least-squares and is closely related to a technique called Lasso regression. These two original papers have led to dozens of followup works.

Course goal

This class will cover the original result and some of the followups. Among the followups, we are particularly interested in (a) efficient algorithms for l1 and (b) extension to rank minimization. The papers in the latter category show that the problem of minimizing the rank of A, subject to linear constraints on A, is sometimes solvable in polynomial time (even though the general problem is NP-hard) if the constraints have a certain random structure and the solution itself is low-rank.

List of papers

The following is a partial list of papers that will be covered. Unless otherwise indicated, all of these papers are available through the UW library computer. Please obtain the journal versions rather than preprint versions on the web if possible. In some cases, papers have appeared only as preprints, in which case please follow the link below.

These papers have been drawn from the comprehensive list of papers on compressive sensing available from Rice University. The remaining papers will also be drawn from the comprehensive list during the first few weeks of lecture according to the students' interest.

Basic theory

  • Anna Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, and Martin Strauss, Near-optimal sparse Fourier representations via sampling. ACM Symposium on Theory of Computing (STOC), 2002.
  • David Donoho, Compressed sensing. IEEE Trans. on Information Theory, 52(4), pp. 1289 - 1306, April 2006.
  • Emmanuel Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. on Information Theory, 52(2) pp. 489 - 509, February 2006.
  • E, Candès, Compressive Sampling, Proceedings of the 2006 International Congress of Mathematicians.
  • Yin Zhang, On theory of compressive sensing via l1-minimization: Simple derivations and extensions. Rice CAAM Department Technical Report TR08-11, 2008.
  • Anatoli Juditsky and Arkadi Nemirovskii, On verifiable sufficient conditions for sparse signal recovery via l1 minimization, (Preprint, 2008).

    • Algorithms

  • Joel Tropp and Anna Gilbert, Signal recovery from random measurements via orthogonal matching pursuit. IEEE Trans. on Information Theory, 53(12) pp. 4655-4666, December 2007.
  • Ewout van den Berg and Michael P. Friedlander, Probing the Pareto frontier for basis pursuit solutions. (Preprint, January 2008)
  • R. Berinde, P. Indyk, and M. Ruzic, Practical near-optimal sparse recovery in the l1 norm. (Proc. Allerton Conference on Communication, Control, and Computing, Monticello, IL, September 2008)
  • Zhaosong Lu. Gradient based method for cone programming with application to large-scale compressed sensing. Preprint, 2008.

    Rank minimization and the nuclear norm

  • Benjamin Recht, Maryam Fazel and Pablo A. Parrilo, Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
  • Emmanuel Candès and Benjamin Recht, Exact matrix completion via convex optimization. Preprint, 2008.
  • Brendan Ames and Stephen Vavasis, Nuclear norm minimization for the planted clique and biclique problems, in preparation.

    • Prerequisites

    Knowledge of linear programming at the level of CO 355. Basic knowledge of probability.

    Course requirements

    Course notes

    Problem Sets

    Stephen A. Vavasis, Department of Combinatorics and Optimization, University of Waterloo, 200 University Ave. W., Waterloo, ON N2L 3G1, vavasis@math.uwaterloo.ca.

    handed out 2009-Jan-5.