Principles of Compressed Sensing

Seminar in Winter Term 2020/21

Description

Compressed sensing (or compressive sensing) is a technique in signal processing. It is based on the assumption that the signal is sparse, and aims to reconstruct the signal using underdetermined linear systems. Besides a plethora of applications in imaging, including photography, astronomy, electron microscopy and facial recognition, it can be used to recover signals from noise in magnetic resonance imaging and acoustic imaging as well.

The aim of this seminar is to cover the basic principles of compressed sensing, as well as dwell into the basic results and techniques used in the field.

Requirements

We are looking for enthusiastic students who have an interest in the mathematics of compressive sensing. The material to be covered requires basic knowledge of linear algebra and physics.

Tasks

The seminar will cover 10 topics from the area of compressive sensing. Each topic will be covered by one student, via a 30-minute presentation and a written report of 5-10 pages.

Setup

All presentations will be scheduled on a one-day session on the last academic week of December (14-18 December), where each 30-minute talk is followed by up to 15 minutes discussion. There is a maximum number of 10 participants.

There will be an introductory meeting at 14:00 on 12th November, when the exact date of the presentation session will be decided. Participation in both occasions is mandatory.

Topics

The material is from the following book:

Foucart, Simon; Rauhut, Holger. A mathematical introduction to compressive sensing. Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York, 2013. xviii+625 pp. ISBN: 978-0-8176-4947-0; 978-0-8176-4948-7

The topics will be assigned to students by taking into account their preferences:

  • An Invitation to Compressive Sensing
  • Sparse Solutions of Underdetermined Systems
  • Basic Algorithms
  • Basis Pursuit
  • Coherence
  • Restricted Isometry Property, Greedy Algorithms
  • Sparse Recovery with Random Matrices, Johnson-Lindenstrauss lemma, (Sub-)Gaussian Matrices
  • Gelfand Widths of l1-Balls
  • Recovery of Random Signals using Deterministic Matrices
  • Algorithms for l1-minimization: The Homotopy Method, Chambolle and Pock’s Primal-Dual Algorithm, Iteratively Reweighted Least Squares