Compressed Sensing

Course guarantor:

Jan Vybíral

Lecturer:

Jan Vybíral

Tutor:

Supervisor:

Department of Mathematics

Synopsis:

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.

Requirements:

Syllabus of lectures:

Syllabus of tutorials:

Study Objective:

Acquired knowledge: Students will learn basic aspects of the theory of sparse representations and compressed sensing and their use in data analysis.

Acquired skills: Lecture will help students combine and apply the knowledge about linear algebra, statistics, and mathematical analysis in signal processing and machine learning.

Study materials:

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

Note:

Time-table for winter semester 2024/2025:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon
Tue
Wed
Thu
Fri	roomTR:112 Vybíral J. 08:00–09:50 (lecture parallel1) Trojanova 13 zasedací místnost KM

Time-table for summer semester 2024/2025:

Time-table is not available yet

The course is a part of the following study plans:

• Aplikovaná algebra a analýza (elective course)
• Aplikované matematicko-stochastické metody (elective course)
• Matematické inženýrství (elective course)
• Matematická informatika (elective course)