Contents

This course covers compressed sensing (CS) and approximate message passing (AMP), two powerful frameworks at the intersection of signal processing, statistical inference, and optimization. Starting from the fundamentals of sparse signal recovery, the course introduces students to key concepts in high-dimensional statistics, signal processing and Bayesian inference that underlie CS and AMP. Special attention will be given to the AMP algorithm and its variants, which provide an iterative solution to a wide set of linear inverse problems.

To give an introductory example, look at the time-domain signal on the right. Classical Nyquist-rate sampling of the signal would require 32 samples to fully reconstruct the signal. However, using compressed sensing techniques, it is possible to sample only the 8 red points in the picture and still get a perfect reconstruction. 

The reason why this is possible lies in the frequency domain representation, which turns out to be sparse. That means only a comparably small number of frequency coefficients is non-zero. In this case, special algorithms, which are subject of this lecture, allow for reconstruction even if the signal is heavily undersampled. 

The key for successful reconstruction lies in choosing the sampling points at random. In this lecture we will review the basics of probability in high-dimensional spaces and see how they lead to strong recovery guarantees. Compressed sensing refers to the theory and the reconstruction algorithms which allow to reconstruct heavily undersampled signals which have a sparse representation in some bases. We will discuss applications from communications, radar, medical imaging, and coding theory. 

Part of this lecture is a coding challenge in which student get the chance to implement their own sparse recovery algorithm. A mysterious price is given to the most successful participant.