Two Lectures on Compressive Sensing: Structured Random Matrices in Compressive Sensing

Thursday, March 8, 2012 - 3:30pm - 4:30pm
Vincent 16
Holger Rauhut (Rheinische Friedrich-Wilhelms-Universität Bonn)
Compressive sensing is concerned with the recovery of sparse vectors from incomplete linear information via efficient algorithms. It is well-known that Gaussian random matrices provide optimal measurement matrices in this context. From an application point of view such completely unstructured matrices are, however, of limited use. Indeed, structure allows to model physically meaningful information acquisition processes, and also allows fast matrix-vector multiplication which helps in speeding up recovery algorithms such as l1-minimization. In this talk I will report on two types of structured random matrices. Partial random circulant matrices describe subsampled random convolutions. I will present sparse recovery results for these, and in particular, recent estimates for their restricted isometry constants. The corresponding analysis uses a new generic chaining type bound for chaos processes. Furthermore, I will discuss a structured random matrix arising in radar imaging. The randomness comes from placing antenna elements at random locations on a square aperture. The difficulty in the corresponding analysis lies in the fact that neither the columns nor the rows of this matrix are independent.