Compressive Sensing (CompSense)5 ECTS
(englische Bezeichnung: Compressive Sensing)
(Prüfungsordnungsmodul: Compressive Sensing)

Lehrveranstaltungen:

• • Compressive Sensing
    (Vorlesung mit Übung, 4 SWS, Ali Bereyhi, Mo, Fr, 10:15 - 11:45, Zoom-Meeting)

Empfohlene Voraussetzungen:

Es wird empfohlen, folgende Module zu absolvieren, bevor dieses Modul belegt wird:

Information Theory and Coding (WS 2020/2021)

Inhalt:

This lecture aims to provide a good background on the concept of compressive sensing and its applications in communications and signal processing.

Part I: Compressive Sensing from the Classical Viewpoint
In the first part, the classic problem of compressive sensing is explained. Important algorithms for sparse recovery in cases with noise-free underdetermined measurements are studied. These algorithms are then modified to address sparse recovery from noisy measurements.
Once basic concepts and algorithms are studied, we start with typical analyses in compressive sensing. In this respect, the null space property, restricted isometry property (RIP) and the coherence of a matrix are introduced. Based on these definitions, the concept of recovery guarantee for a sparse recovery algorithm is explained. We then study important recovery guarantees and give some examples of detailed analyses.
Finally, we give an introduction to compressive sensing via random matrices and present some key results in this respect.

Part II: Compressive Sensing from a Bayesian Viewpoint
In the second part of the course, we show that compressive sensing can be observed as a Bayesian inference problem. This new viewpoint lets us define the optimal recovery algorithm. We further show that well-known recovery algorithms such as LASSO are interpreted as sub-optimal Bayesian estimators.
The key benefit of the Bayesian viewpoint is that it enables us to illustrate approximate message passing (AMP) algorithms: We start with the implementation of a sparse recovery algorithm via the sum-product algorithm and then explain how an AMP algorithm is derived from the sum-product algorithm.

The detailed list of contents is as follows:

• Introduction to Compressive Sensing

• Part I: Compressive Sensing from the Classical Viewpoint

• Zero-norm minimization

• Basis pursuit

• Iterative Algorithms

• The method of regularized least-squares

• Regularization options for sparse recovery

• Dantzig selector

• Null space property

• Coherence of a matrix

• Restricted isometry property

• Some notes on random matrices

• Generic form of a performance guarantee

• Some examples of performance guarantee

• Part II: Compressive Sensing from a Bayesian Viewpoint

• Posterior distribution

• Likelihood in a noisy setting

• Sparse prior

• Recovery algorithm with minimum mean squared error

• Computational complexity of the optimal recovery algorithm

• Mismatched prior of LASSO algorithm

• Mismatched prior of zero-norm regularization

• Implementing a Bayesian algorithm via message passing

• Approximating a message passing algorithm for large problems

• A sample approximate message passing algorithm
  

Lernziele und Kompetenzen:

• The students understand the concept of sparse recovery.

• The students apply sparse recovery to model problems in several applications, such as communication and signal processing systems and machine learning.

• The students apply classic approaches to recover sparse signal samples from underdetermined observations.

• The students implement most important recovery algorithms in compressive sensing, namely basis pursuit, orthogonal matching pursuit, Lasso and Dantzig algorithm.

• The students understand how to regularize the method of least-squares in order perform sparse recovery with it.

• The students understand under which condition sparse recovery is successful.

• The students understand important properties of sensing matrices, namely null space property, coherence of a matrix and restricted isometry property.

• They apply the mentioned properties of sensing matrices to determine the effectiveness of a given sensing matrix.

• The students understand the analysis of the success probability of a sparse recovery algorithm and the necessary and sufficient conditions for different algorithms.

• The students derive the components of a typical sparse recovery algorithm in a Bayesian inference framework.

• In the shadow of the Bayesian interpretation, the students understand the behaviour of different sparse recovery algorithms.

• The students understand the theoretically optimal minimum mean square bound for compressive sensing.

• The students apply the sum-product algorithm to implement a typical sparse recovery algorithm.

• Starting from the sum-product algorithm, the students determine an approximate message passing algorithm via large-system analysis.

• The students understand the state-evolution of the approximate message passing algorithm.

Literatur:

For the first part of the course, we mainly follow the discussions from

• Foucart, Simon, and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhäuser, NewYork, NY, 2013.

For the second part, we collect discussions mainly from the following references:

• Bereyhi, Ali. Statistical Mechanics of Regularized Least Squares. PhD Dissertation, Friedrich-Alexander University of Erlangen (2020).

• Rangan, Sundeep, Alyson K. Fletcher, and Vivek K. Goyal. “Asymptotic analysis of MAP estimation via the replica method and applications to compressed sensing.” IEEE Transactions on Information Theory 58, no. 3 (2012): 1902-1923.

• Kschischang, Frank R., Brendan J. Frey, and H-A. Loeliger. “Factor graphs and the sum-product algorithm.” IEEE Transactions on Information Theory 47, no. 2 (2001): 498-519.

• Maleki, Arian. Approximate message passing algorithms for compressed sensing. PhD Dissertation, Stanford University (2011).
  

Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan:

1. Advanced Signal Processing & Communications Engineering (Master of Science)
   (Po-Vers. 2020w | TechFak | Advanced Signal Processing & Communications Engineering (Master of Science) | Gesamtkonto | Technical Electives | Compressive Sensing)

Studien-/Prüfungsleistungen:

Compressive Sensing (Prüfungsnummer: 84471)

Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet, 5 ECTS

Anteil an der Berechnung der Modulnote: 100.0 %

Prüfungssprache: Englisch

Erstablegung: SS 2021, 1. Wdh.: WS 2021/2022

1. Prüfer:

Ralf Müller