Imaging and Computing Seminar

Felix Krahmer, Institute for Numerical and Applied Mathematics, Georg-August-Universität Göttingen, Germany

Title:
Compressed sensing bounds via improved estimates for Rademacher chaos

Abstract:
The theory of compressed sensing considers the following problem: Let A be a m x n matrix and let x  be a vector of length n that is s-sparse, 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 smaller 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. For the random vector, we focus on Rademacher vectors, i.e., vectors whose entries are independent random signs. Second, we study Gabor synthesis matrices, that is, matrices consisting of time-frequency shifts of a Rademacher vector. In both cases, this question can be reduced to estimating random variables of the form D_B:=sup_(A\in B) | || A \epsilon\|^2 - \E ||A \epsilon||^2| where the supremum is taken over an arbitrary 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 the expectation of such variables in terms of the Talagrand γ2-functional. 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(n)4 . 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.