Description:

The lecture will introduce basic concepts of the theory of compressed sensing ? an area founded in 2006 in the works of D. Donoho, E. Candes, and T. Tao. This theory studies the search for sparse solutions of underdetermined systems of linear equations. Due to the applications of sparse representations in electric engeneering and signal processing, this theory was quickly used in many different fields.

After the first survey lecture, we will study the mathematical foundations of the theory. We prove general NP-completeness of the search for sparse solutions of systems of linear equations. We introduce conditions which ensure also existence of more effective solvers and show, that these are satisfied for example for Gaussian random matrices. As an effective solution method, we will analyze l1-minimization and Orthogonal Matching Pursuit. We will also study stability and robustness of the obtained results with respect to the corruption of measurements and the optimality of the results.

Recommended literature:

Compulsory literature:
S. Foucart and H. Rauhut: A Mathematical Introduction to Compressive Sensing, Springer, 2013
H. Boche, R. Calderbank, G. Kutyniok, J. Vybíral: A Survey of Compressed Sensing, in: Compressed Sensing and its Applications, Springer, 2015

Optional literature:
D.L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), 1289-1306
E.J. Candes, J. Romberg, and T. Tao, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2) (2006), 489-509

Keywords:

Sparsity and solution of underdetermined systems of linear equations, basis pursuit, null space property, coherence a restricted isometry property, l1-minimization, Gaussian random matrices and Johnson-Lindenstrauss imbedding

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar