Contemporary Sampling Techniques and Compressed Sensing

Lecturer: Anders Hansen
Teaching assistant: Clarice Poon
Time and location: MWF, 9am, MR12

This is a graduate course on sampling theory and compressed sensing for use in signal processing and medical imaging. Compressed sensing is a theory of randomisation, sparsity and non-linear optimisation techniques that breaks traditional barriers in sampling theory. Since its introduction in 2004 the field has exploded and is rapidly growing and changing. Thus, we will take the word contemporary quite literally and emphasise the latest developments, however, no previous knowledge of the field is assumed. Although the main focus will be on compressed sensing, it will be presented in the general framework of sampling theory. The course will also present related areas of sampling theory such as generalised sampling and sampling at a finite rate of innovation.

Although the course will be rather mathematical, it will be fairly self contained, and applications will be emphasised (in particular, signal processing and Magnetic Resonance Imaging (MRI)). Students from other disciplines than mathematics are encouraged to participate.

The course will be based on the books: Compressed Sensing (Eldar, Kutyniok), CUP 2012, A Mathematical Introduction to Compressive Sensing (Foucart, Rauhut), Springer 2014+
We will roughly cover: Ch1 and Ch4 in EK and Ch1, Ch4, Ch5, Ch7 and Ch12 in FH + separate notes for Generalized Sampling.

Week 1: Introduction to compressed sensing. Jan 14 - Jan 18

Only one lecture this week, where an overview of compressed sensing and applications will be provided.

Reading list: (1) Ch1 in FH
Introduction slides
LMS lecture series by Emmanuel Candes

Week 2: The Restricted Isometry Property and friends. Jan 21 - Jan 25

Mon: Spark of a matrix, k-term approximation, Null Space Property, Restricted Isometry Propery.
Wed: More on the RIP and the k log(n/k) lower bounds.
Fri: The RIP implies the Null Space Property. Applications: Test of l1 recovery with the DFT and DFT inv(DWT). Why does the latter fail when the subsampling is done uniformly at random?

Reading list: Ch1 in EK

Week 3: The RIP and basis pursuit. Jan 28 - Feb 1

Mon: The RIP and basis pursuit.
Wed: More on the RIP and basis pursuit with noise.
Fri: Applications: Test of l1 recovery with the DFT inv(DWT), why does "half-half" sampling do so well? Tests of the RIP in applications. Application slides I

Reading list: Ch1 in EK
Exercises: Set 1
Example class (Clarice Poon) with solutions : 3-4.30pm, Fri Feb 8, MR 5.

Week 4: The RIP-less theory. Feb 4 - Feb 8

Mon: Intro to probability.
Wed: Inexact dual certificate and basis pursuit.
Fri: Constructing the dual certificate, probability bounds using Bernstein's inequality. Applications: The success of compressed sensing is resolution dependent. Application slides II


Reading list: Ch7 in FR, Ch4 in FR (p. 81-86), Ch12 in FR (p.335-342, 358-360)

Week 5: Building an inexact dual certificate. Feb 11 - Feb 15

Mon: Probability bounds using "Matrix Bernstein".
Wed: Probability bounds using "Matrix BernsteinII".
Fri: Building an inexact dual certificateI. Applications: Resolution dependence and compression.


Reading list: Ch12 in FR (p.351-352), (p.362-366)
Exercises: Set 2
Example class (Clarice Poon) with solutions : 4-5.30pm, Fri Feb 22, MR 14.

Week 6: Building an inexact dual certificate. Feb 18 - Feb 22

Mon: Building an inexact dual certificateII.
Wed: Building an inexact dual certificateIII.
Fri: Building an inexact dual certificateIV. Applications: Optimal sampling strategies.


Reading list: Ch12 in FR (p.363-368)

Week 7: Generalized Sampling. Feb 25 - March 1

Mon: The Shannon Sampling Theorem and consistent sampling.
Wed: Subpsace angles, condition number of abstract algorithms and oblique projections .
Fri: Intro to reduced consistency sampling. Applications: Generalized sampling in practise.


Reading list: Class notes
Additional reading: A great summary of sampling theory up to 2000 is M. Unser's Sampling 50 years after Shannon

Week 8: Generalized Sampling. March 4 - March 8

Mon: Proofs of sharp bounds for consistent and reduced consistency sampling I.
Wed: Proofs of sharp bounds for consistent and reduced consistency sampling II.
Fri: Optimality of generalised sampling. Applications: Generalized sampling combined with compressed sensing.


Reading list: Class notes (complete tex notes will be provided at the end of the term)
Additional reading: For an example of generalised sampling and l1 optimisation used in MRI see A Fast Wavelet-Based Reconstruction Method for Magnetic Resonance Imaging

Week 9: Return to compressed sensing. March 11 - March 13

Mon: Coherence of matrices and coherence between bases.
Wed: Summary of compressed sensing and discussion of the RIP in applications. Applications: Real life MRI experiments.


Reading list: Ch1 in EK
Exercises: Set 3