Compressive Sensing and Structured Random Matrices


COURSE - The recent theory of compressive sensing predicts that sparse vectors can be recovered from vastly incomplete linear measurements using efficient algorithms.  Optimal measurement matrices known so far are random  matrices. While often Gaussian or Bernoulli random are considered, such matrices are of limited practical interest because of the lack of any structure. In fact, applications demand for certain structure and there is only limited freedom to inject randomness. Therefore, one considers structured random matrices. We will study their usefulness for sparse recovery using $\ell_1$-minimization. In particular, we present results for partial random Fourier matrices, i.e., the random row sub-matrices of the discrete Fourier matrix.  Moreover, applications in radar motivate us to consider various other types of structured random matrices, such as partial random circulant matrices, time-frequency structured random matrices, and random scattering matrices. We will also review recent extensions of compressive sensing for recovering matrices of low rank from incomplete information via efficient algorithms such as nuclear norm minimization. It is planned to introduce to the mathematical tools in order to establish corresponding bounds for structured random matrices.

REFERENCES - This course will mainly be based on the lecture notes ‘Compressive Sensing and Structured Random Matrices, extended with new results of the authors.


Lecturer: Prof. Dr. Holger Rauhut

Credits: 6 ECTS

Date: 15-19 Oct. 2012


Assistant: Liang Dai.


            1. KTH, Automatic Control

                Osquldas väg 10

                Stockholm SE-100 44 



  1.         2. UU - Systems and Control


                Uppsala SE-751 05,



  1. 1. KTH - 15e Oct. 2012,

        time 10-12am, B23.

  1. 2. KTH - 16e Oct. 2012,

        time: 10-12am, L31.

  1. 3. KTH - 17e Oct. 2012,

        time: 10-12am, B22.    

  1. 4. UU - 18e Oct. 2012,                            

        time: 10-12am, room 2247.

  1. 5. UU - 19e Oct. 2012,

        time: 10-12am, room 2347.