Mathematics of Information and Applications Seminar: Felix Krahmer

The theory of compressed sensing considers the following problem: Let A be an m x n matrix and let x be an s-sparse vector in n dimensions, i.e., all but s of its entries vanish. One seeks to recover x uniquely and efficiently from linear measurements y = Ax, although m is much less than 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 of a Rademacher vector, i.e., a vector whose entries are independent random signs, but also discuss the case of independent subgaussian entries. Second, we study Gabor synthesis matrices, that is, matrices consisting of time-frequency shifts of a such vectors.
 
In both cases, this question can be reduced to estimating a supremum of random variables taken over an indexing set of matrices. Random variables of this type are closely related to suprema of chaos processes. Using generic chaining techniques, we derive a bound for its moments in terms of concepts from the theory of empirical processes. As a consequence, we obtain that matrices from both classes under consideration have the RIP with high probability if the embedding dimension satisfies m > Cs log^4(n). This bound exhibits optimal dependence on s, while previous works had only obtained a suboptimal scaling of s^(3/2).
 
This is joint work with Shahar Mendelson and Holger Rauhut.