Compressed Sensing

Summary

This course will discuss the theoretical, numerical, and practical foundations of Compressed Sensing (CS) which has become a very important concept in recent years in information and signal processing. It allowed an alternative approach to conventional techniques for acquiring and reconstructing sensor input signals. CS is also known as Compressive Sampling because it allows sampling of compressible analog signals with sampling rates well below the Nyquist rate. This analog setting of CS allows significant performance  improvements of analog-to-digital converters for a broad class of time  continuous signals. It is therefore possible to design universal CS based data acquisition systems with compressive sensors for analog and digital sensor input signals, even if these signals are noisy.

The compressibility of certain signals can be exploited by developing novel CS methods which, in comparison to traditional approaches like the transform coding, involve far less processing effort for data compression. On the other hand, CS requires far more effort in order to reconstruct a sensor input signal. Accordingly, CS can help to resolve data deluge in complex sensing networks, where the number and resolution of the sensors grow to a point where the performance bottleneck moves to data processing in sensors. To avoid this raw data accumulation, new designs of data acquisition systems are proposed. They combine sensing and compression in one simple operation, replacing conventional sensors with compressive sensors. Instead of acquiring a massive amount of raw data and extracting the information afterwards, compressive sensors attempt to acquire the information directly.

Data compression using CS is performed by means of a simple linear superposition, while the decompression is based on optimization algorithms for finding the unique sparse solution of an underdetermined system of linear equations. There are multiple approaches for solving this searching problem, e.g. the generic Basis Pursuit method. This fundamental CS decompression method is based on the optimization technique related to the L1-norm.

The principles of compressed sensing are difficult to comprehend from the available literature without prior special knowledge, since they encompass specific aspects and languages of many mathematical fields. The most relevant subjects to CS are high-dimensional geometries of Euclidean and Banach spaces, random matrices, information and approximation theory, linear and convex programming, harmonic analysis, and combinatorics.

This highly challenging abstract approach to compressed sensing will be in  these lectures replaced by a simpler, expressive and application-oriented approach easy understandable for engineers. The underlying principle of this new research field will be systematically explained. The lectures and exercises will illuminate the basic principles of CS using the elementary language of signal processing, linear algebra and geometry only.

Topics

The main topics of the course include:

  • Big data research and development
  • Signal representation using bases and frames
  • Traditional and generalized sampling of analog signals
  • Overview of sparse recovery - discrete and analog setting
  • Recap of the necessary concepts from linear algebra
  • Sparsity and measurement basis and frames (dictionaries)
  • Sensing matrices and recovery equations
  • Geometric interpretation of linear systems of equations
  • Some terms of functional analysis and inner product spaces
  • Basics of multidimensional Euclidean geometry
  • Linear and affine subspaces, convex polytopes
  • Arrangements of hyperplanes
  • Configurations of sparse solutions
  • Robustness of CS
  • Recap of linear optimization methods
  • Types of reconstruction algorithms in CS
  • L1-minimization
  • Basic pursuit
  • Orthogonal matching pursuit
  • Theoretical limits of CS
  • Mutual incoherence property
  • Null space property
  • Random matrices and the restricted isometry property
  • Stochastic geometry, the polytope model and face survival
  • Weak and strong phase transitions
  • Sensing matrix design, deterministic sensing matrices
  • CS using antipodal best spherical codes
  • CS for A/D converters and other RF applications
  • Application of CS to image processing and to medical imaging
  • Application of CS to channel coding and cryptography
  • Application of CS to radar technology
  • Application of CS to genetics: DNA-micro-arrays and DNA-sequencing
  • CS in femto photography
  • Perspectives of compressed sensing

In addition to the lecture slides, the following overview articles are recommended:

Literature
  1. Understanding and using linear programming / Jiří Matoušek und Bernd Gärtner / Springer Verlag
  2. Mathematik / Tilo Arens, Frank Hettlich, Christian Karpfinger, Ulrich Kockelkorn, Klaus Lichtenegger und Hellmuth Stachel / Spektrum Akademischer Verlag
  3. Website about Compressed Sensing
  4. IEEE Signal Processing Magazine (Special Issue on Compressive Sampling), March 2008.
  5. M.A. Davenport, M.F. Duarte, Y.C. Eldar, and G. Kutyniok, "Introduction to Compressed Sensing," in Compressed Sensing: Theory and Applications, Cambridge University Press, 2012.
Lecture Slides
Downloads for the exercises
Examplary questions

Here, you can find exemplary questions regarding the exercises.

Important News

Please check this site regularly for any last-minute changes and announcements!

Dates

The first lecture will be on 23 April 2014.

The first exercise will be on 30 April 2014. Due to the welcome reception of the new CT students, this exercise will end at 15:30.

Oral Exam Dates

The first day for oral exams is the 15th of August starting from 14:00.

Please contact our secretary in order to arrange the exact time for the oral exam.

The oral exams will take place in 43.2.227.

Summer Term 2014

Lecture:Wednesday 14:00 - 16:30,
Room 43.2.102
Exercise:every 3rd week

Contact

Lecturers:
Dr.-Ing. Dejan Lazich
Supervisors:
Dipl.-Ing. Henning Zörlein

Language

English

Requirements

Basic knowledge in signal processing, linear algebra and stochastics

Exams

oral exam

More Informations

Hours per Week:  2L + 1E
5 ECTS Credits
LSF - ENGJ 8027