Learning Compressed Sensing

Compressed Sensing is mostly a set of methods designed for finding the sparsest solution to some underdetermined systems of linear equations.

After having understood this, here are some questions that one generally ask:
  • What sort of underdetermined systems are allowed in order to find the sparsest solution ? 
  • How can you find this sparsest solution ? 
  • How can my problem be mapped as a compressive sensing problem ?
Those are some of the questions that are being answered in some fashion or another in the following resources below (course note, videos) with varying degrees of difficulty. A second set of questions usually are then asked once some of these first issues are addressed:

  • Instead of the sparsest solution, can one find the most compressible solutions instead ?
  • instead of an underdetermined system of equations, can it be a system of nonlinear equations instead?
  • etc ....
Eventually, you might be interested in subscribing to the Nuit Blanche feed, or visit/join the following communities:

and post questions there. Be sure to read some of the notes/pages listed here before you do. It also helps when you provide some context about what you know.

Of related interest are these documents: The Big Picture in Compressive Sensing and the Advanced Matrix Factorization Jungle Page that aim at providing some context on these subjects.

In this page, you will find some expository material aimed at various crowds, pick the one you feel most comfortable with:

  • Three videos presenting compressive sensing by Mark Davenport. It's short and to the point.

  • Compressive Sensing I: Introduction 
  • Compressive Sensing II: Sensing Matrix Design 
  • Compressive Sensing III: Sparse Signal Recovery
  • a nice tutorial video on signal reconstruction with additive error metrics by Dror Baron and Jin Tan.

More in-depth explanation and teachings are provided below:

In terms of books, for less than $3.00 there is one the Kindle store: It can be read on the Kindle, iPad/iPod Touch and other tablets through the Kindle app:

Courses and Lecture Notes:
The following lectures were given at IAS in Princeton and provide a good introduction to CS and related issues:

You can also learn by doing, try any of these examples:

Webpages of  courses/classes given at different universities (undergraduate/graduate classes) can be found here and are listed below:

Emmanuel Candes was invited at the Centre for Mathematical Sciences in Cambridge, UK to give a series of lectures on compressed sensing. Here are the videos of these talks made at the LMS Invited Lecturer Series 2011:

Emmanuel Candes, Lecture 1: Some history and a glossy introduction

MPEG-4 Video *640x360   1.84 Mbits/sec1.21 GBViewDownload
Flash Video484x272   568.67 kbits/sec372.57 MBViewDownload
iPod Video480x270   506.21 kbits/sec331.65 MBViewDownload
MP344100 Hz125.0 kbits/sec81.70 MBListenDownload

Lecture 2: Probabilistic approach to compressed sensing

MPEG-4 Video *640x360   1.84 Mbits/sec992.84 MBViewDownload
Flash Video484x272   568.78 kbits/sec298.35 MBViewDownload
iPod Video480x270   506.27 kbits/sec265.56 MBViewDownload
MP344100 Hz125.02 kbits/sec65.38 MBListenDownload

Lecture 3: Deterministic approach to compressed sensing

MPEG-4 Video *640x360   1.84 Mbits/sec1.29 GB View Download
iPod Video480x270   506.19 kbits/sec353.32 MB View Download
MP344100 Hz125.0 kbits/sec87.05 MB Listen Download

Lecture 4: Incoherent sampling theorem

MPEG-4 Video *640x360   1.84 Mbits/sec1.11 GBViewDownload
Flash Video484x272   568.75 kbits/sec340.61 MBViewDownload
iPod Video480x270   506.25 kbits/sec303.18 MBViewDownload
MP344100 Hz125.02 kbits/sec74.67 MBListenDownload

 Lecture 5: Noisy compressed sensing/sparse regression

MPEG-4 Video *640x360   1.84 Mbits/sec1.18 GBViewDownload
Flash Video484x272   568.7 kbits/sec361.90 MBViewDownload
iPod Video480x270   506.2 kbits/sec322.13 MBViewDownload
MP344100 Hz125.01 kbits/sec79.35 MBListenDownload

Lecture 6: Matrix completion

MPEG-4 Video *640x360   1.84 Mbits/sec1.12 GBViewDownload
Flash Video484x272   568.75 kbits/sec345.26 MBViewDownload
iPod Video480x270   506.26 kbits/sec307.33 MBViewDownload
MP344100 Hz125.02 kbits/sec75.70 MBListenDownload

Lecture 7: Robust principal components analysis and some numerical optimization

MPEG-4 Video *640x360   1.84 Mbits/sec1.27 GBViewDownload
Flash Video484x272   568.66 kbits/sec391.37 MBViewDownload
iPod Video480x270   506.21 kbits/sec348.39 MBViewDownload
MP344100 Hz125.0 kbits/sec85.84 MBListenDownload

Lecture 8: Some Applications and Hardware Implementations

MPEG-4 Video *640x360   1.84 Mbits/sec1.11 GBViewDownload
Flash Video484x272   568.8 kbits/sec340.02 MBViewDownload
iPod Video480x270   506.2 kbits/sec302.66 MBViewDownload
MP344100 Hz125.0 kbits/sec74.54 MBListenDownload

Anders Hansen, Generalized sampling and infinite-dimensional compressed sensing

We will discuss a generalization of the Shannon Sampling Theorem that allows for reconstruction of signals in arbitrary bases. Not only can one reconstruct in arbitrary bases, but this can also be done in a completely stable way. When extra information is available, such as sparsity or compressibility of the signal in a particular bases, one may reduce the number of samples dramatically. This is done via Compressed Sensing techniques, however, the usual finite-dimensional framework is not sufficient. To overcome this obstacle I'll introduce the concept of Infinite-Dimensional Compressed Sensing.
MPEG-4 Video *640x360   1.84 Mbits/sec829.14 MBViewDownload
Flash Video484x272   568.77 kbits/sec249.05 MBViewDownload
iPod Video480x270   506.27 kbits/sec221.68 MBViewDownload
MP344100 Hz125.02 kbits/sec54.55 MBListenDownload

Once you have graduated from any of these courses, you may want to take a peak at the Big Picture in Compressive Sensing that features some of the most recent measurement matrices and reconstruction solvers. You can also read the blog...
...or subscribe to the Nuit Blanche feed