Compressed Sensing
Code  Completion  Credits  Range  Language 

01KOS  ZK  2  2+0  Czech 
 Garant předmětu:
 Lecturer:
 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 NPcompleteness 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 l1minimization 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), 12891306
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), 489509
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

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