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:
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:
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:
subscribing to the Nuit Blanche feed, or visit/join the following communities:- the Google+ Community,
- the CompressiveSensing subreddit,
- the Facebook page
- the LinkedIn Compressive Sensing group and/or the
- Matrix Factorization Group
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:
- A book: An Introduction to Compressive Sensing by Chinmay Hegde, Richard Baraniuk, Mark A. Davenport, Marco F. Duarte
- A set of Tutorial and review papers at the Rice Repository site.
- A nice overview by Mike Davies entitled Foundations of Compressed Sensing
- I answered the following question on Quora: "What is compressed sensing (compressive sampling) in layman's terms?". My answer is here and uses the well known 12 balls weighting problem.
- Similarly, another way of seeing how compressive sensing work is to view how compressive sensing systems are implemented in hardware:
- A while back, I wrote how the Rice one pixel camera work ?
- A non-exhaustive list of many other hardware/sensors
- With some colleagues, we demonstrated how to use randomness found in Nature to encode images ( see my Compressive Sensing article in Scientific Reports and the attendant Project Page)
- A presentation designed for very early undergraduates, it's also a work in progress (constructive criticism is welcome):
- A presentation that might provide some insight to engineers and other learned professionals but who may not be entirely familiar to what compressive sensing is. In particular, we try to avoid a unique reference to the L_1 norm and other deeper (and sometimes too narrow) mathematical statement while favoring the hardware/sensor issues:
- Miki Lustig produced several XKCD-like comics on Compressive Sensing in MRI
- Dustin Mixon's Compressed sensing: Variations on a theme (The attendant presentation is here)
- A while back, I created a small video of a clown and a woman talking about compressed sensing, let me know if it helps better understand the subject:
- Three videos presenting compressive sensing by Mark Davenport. It's short and to the point.
- Compressive Sensing I: IntroductionCompressive Sensing II: Sensing Matrix DesignYou can also learn by doing, try any of these examples: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:
- Introduction to Compressive Sensing by Richard Baraniuk, Mark Davenport, Marco Duarte, and Chinmay Hegde.at Connexions.org.
- An Introduction to Compressed Sensing by Mark Davenport, Marco Duarte, Yonina Eldar, Gitta Kutyniok
- Compressive Sensing - An Introduction by Massimo Fornasier and Holger Rauhut.
- Notes on Compressed Sensing by Simon Foucart
The following lectures were given at IAS in Princeton and provide a good introduction to CS and related issues:- Anna Gilbert's lecture 1 Background on sparse approximation
- Anna Gilbert's lecture 2 Hardness results for sparse approximation problems
- Anna Gilbert's lecture 3 Dictionary geometry, greedy algorithms, and convex relaxation
- Rebecca Willett's lecture 1Methods for sparse analysis of high-dimensional data, I
- Rebecca Willett's lecture 2 Sparsity: Correcting Error in Data
- Rebecca Willett's lecture 3 Sparsity: Compressed Sensing
- Rebecca Willett's lecture 4 Sparsity: Generalized Sparsity Measures and Applications
- Rachel Ward's lecture 1 Methods for sparse analysis of high-dimensional data, II
- Sofya Raskhodnikova's lecture 1 Sublinear-Time Algorithms
- Sofya Raskhodnikova's lecture 2 Sublinear-Time Algorithms
- Sofya Raskhodnikova's lecture 3 Sublinear-Time Algorithms
- Sofya Raskhodnikova's lecture 4 Sublinear-Time Algorithms
- Michael Friedlander has some basic examples in the SPGL1 toolbox but he and Ewout van den Berg also features a long suite of examples with different measurement matrices in the SPARCO toolbox.
- Gabriel Peyre has several walk through examples (tours)
- Examples from Sparselab
- Generally any of the solvers listed here have examples on how to use them.
Webpages of courses/classes given at different universities (undergraduate/graduate classes) can be found here and are listed below:
- Emmanuel Candes' STAT 330 course: An Introduction to Compressed Sensing (Spring 2010)
- EE546/STAT593C - Sparse Representations: Theory, Algorithms, and Applications by Maryam Fazel and Marina Meila (Spring 2010)
- Convex Geometry in High-Dimensional Data Analysis, CS838 Topics In Optimization by Ben Recht (Spring 2010)
- Thomas Strohmer's course CS 280: Sparse Representations and Compressive Sensing (Spring 2010)
- Piotr Indyk : Sketching, Streaming and Sub-linear Space Algorithms (Fall 2007)
- Piotr Indyk : Streaming Etc. (at Rice University) Spring 2009.
- Ronitt Rubinfeld Sublinear Time Algorithms.( MIT 6.896 ) Fall 2010
- CS5540: Computational Techniques for Analyzing Clinical Data taught by Ramin Zabih and Ashish Raj (Spring 2010)
- Deanna Needell Non Asymptotic Random Matrix Theory CS 280 at UC Davis taught by Roman Vershynin (2009)
- Compressed Sensing by Mike Wakin on Connexions (2008)
- 2010S JEB1433 Medical Imaging at University of Toronto by Adrian Nachman (Spring 2010)
- Compressive Sensing by Mark Davenport, Richard Baraniuk, Ronald DeVore. (2007)
- Andrew McGregor, "Crash Course in Data Streams: Part I" and "Part II" (John Hopkins APL '10).
- EE 578 Optimization in System Sciences by Maryam Fazel (Winter 2010)
- Lecture notes entitled Compressed Sensing and Sparse Signal Processing by Wu-Sheng Lu (Nov 2010).
- 520.648 Compressed Sensing and Sparse Recovery by Trac D. Tran and Sang "Peter" Chin (John Hopkins, Spring 2011)
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
Format Quality Bitrate Size MPEG-4 Video * 640x360 1.84 Mbits/sec 1.21 GB View Download Flash Video 484x272 568.67 kbits/sec 372.57 MB View Download iPod Video 480x270 506.21 kbits/sec 331.65 MB View Download MP3 44100 Hz 125.0 kbits/sec 81.70 MB Listen Download
Lecture 2: Probabilistic approach to compressed sensing
FormatQualityBitrateSize
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
FormatQualityBitrateSize
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
Format Quality Bitrate Size MPEG-4 Video * 640x360 1.84 Mbits/sec 1.18 GB View Download Flash Video 484x272 568.7 kbits/sec 361.90 MB View Download iPod Video 480x270 506.2 kbits/sec 322.13 MB View Download MP3 44100 Hz 125.01 kbits/sec 79.35 MB Listen Download
Lecture 6: Matrix completion
FormatQualityBitrateSize
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
FormatQualityBitrateSize
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
FormatQualityBitrateSize
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
FormatQualityBitrateSizeWe 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...