Introduction to Compressed Sensing

Introduction to Compressed Sensing

Instructor: Prof. Heung-No Lee


This course was offered in the Spring semester 2011 at GIST.

Here is the lecture note Book_CS.pdf for this course.Here is the presentation of professor Heung-No Lee presented at PSIVT 2011 Overview of Compressed Sensing



Course Syllabus

1 Introduction to Compressive Sensing, Shannon Nyquist Sampling Theorem

2 Comparison of L0, L1, L2 solutions, application of sparse representation theory in filter array based spectrometers HW#1
3 Compressive Sensing Theory: L0 and L1 equivalence, The Spark = Dmin of parity check matrix, The Singleton bound, Givens Rotation based Matrix Design
4 Compressive Sensing Mathematics: Generalized Uncertainty Principle, Sparse Representation, conditions for the unique ell-0 solution, and the unique ell-1 solution, the Donoho approach

  • 1. D. Donoho and X. Huo, “Uncertainty Principles and Ideal Atomic Decomposition,” IEEE Trans. on Info. Theory, vol.47, no.7, Nov. 2001.
  • 2. M. Elad and A. Bruckstein, “A generalized uncertainty principle and sparse representation in pairs of bases,” IEEE Trans. Info. Theory, vol. 48, no. 9, Sept. 2002.
5 Compressive Sensing Mathematics: conditions for the ell-0 solution, and the unique ell-1 solution, the Candes-Tao approach.

  • 1. Emmanuel Candès and Terence Tao, Decoding by linear programming. (IEEE Trans. on Information Theory, 51(12), pp. 4203 – 4215, December 2005)
  • 2. Emmanuel Candès, Justin Romberg, and Terence Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. (IEEE Trans. on Information Theory, 52(2) pp. 489 – 509, February 2006)
  • 3. Emmanuel Candès and Terence Tao, “Near optimal signal recovery from random projections: Universal encoding strategies” (IEEE Trans. on Information Theory, 52(12), pp. 5406 – 5425, December 2006)
6 Compressive Sensing Mathematics: Sensing matrices and oversampling factors HW#3
7 Stable Recovery
8 Midterm Exam
9 Recovery Algorithm I : Homotopy, LASSO, LARs , OMP. HW#4
10 Recovery Algorithm II : ell-1 minimization , SOCP, Message Passing Algorithm s
11 Class Presentations #1/#2/#3 HW#5
12 Connection to the Shannon TheoryClass Presentations #4/#5/#6
13 The Rate Distortion TheoryClass Presentations #7/8/9 HW#6