Department of Image Processing

Compressed Sensing is a new technique of signal processing, which allows to exploit sparsity or compressibility of a signal with respect to some known basis or dictionary and which allows to design extremely effective non-adaptive sampling algorithms. This breakthrough led to a shift in a traditional view of signal acquisition in electrical engineering.

In its most simple form, Compressed Sensing studies underdetermined linear equations Ax=y, and the expected solution x is sparse, i.e. most of its coordinates are zero. The mathematical theory of Compressed Sensing discusses especially the
following fundamental questions:
(i) How to find the sparse solution x in an efficient way, suitable also for large scale problems and Big Data analysis;
(ii) For which matrices is this possible?
(iii) Are the methods stable - i.e. do they work also if x is only nearly sparse with most of the coefficients small, but not exactly equal to zero;
(iv) Is the method robust - i.e. do we recover a good approximation of x also from noisy measurements y=Ax+e?

This survey talk will provide an overview of the most important mathematical ideas behind this new sampling theory, including the notions of null space property, restricted isometry property, and sparse recovery by l_1-minimization. We will also discuss connections of this field with other disciplines like stochastic, numerics, linear algebra, and functional analysis.

In the second part of the talk, we present an overview of applications of Compressed Sensing. These include
(i) Matrix Completion problem: Filling up unknown entries of a matrix, such that the matrix produced has some special properties - typically low rank;
(ii) Phase Retrieval problem: Recovering a signal x from the magnitude of its Fourier transform;
(iii) Separating different features in video, i.e. background and movements;
(iv) Sparse classification: Separating two classes of signals (i.e. blood samples of healthy and sick patients) based on a small number of descriptors.
(v) MRI: Speed up of Magnetic Resonance Imaging;
(vi) Radar technology.