Suprema of Chaos Processes and the Restricted Isometry Property

Friday, March 30, 2012 - 1:30pm - 2:30pm
Lind 305
Felix Krahmer (Georg-August-Universität zu Göttingen)
The theory of compressed sensing considers the following problem: Let A ∈ C mxn and let x ∈ Cn be s-sparse, i.e., xi = 0 for all but s indices i. One seeks to recover x uniquely and effciently from linear measurements y = Ax, although m ‹‹ n. A sufficient condition to ensure that this is possible is the Restricted Isometry Property (RIP). A is said to have the RIP, if its restriction to any small subset of the columns acts almost like an isometry.

In this talk, we study two classes of matrices with respect to the RIP: First, we consider matrices A which represent the convolution with a random vector followed by a restriction to an arbitrary fixed set of entries. We focus on the scenario that ∈is a Rademacher vector, i.e., a vector whose entries are independent random signs. Second, we study Gabor synthesis matrices, that is, matrices consisting of time-frequency shifts of a Rademacher vector.

This is joint work with Shahar Mendelson and Holger Rauhut.