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

Understanding and using linear programming / Jiří Matoušek und Bernd Gärtner / Springer Verlag
Mathematik / Tilo Arens, Frank Hettlich, Christian Karpfinger, Ulrich Kockelkorn, Klaus Lichtenegger und Hellmuth Stachel / Spektrum Akademischer Verlag
Website about Compressed Sensing
IEEE Signal Processing Magazine (Special Issue on Compressive Sampling), March 2008.
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.