Mathematics Colloquium

Felix Krahmer

(Universität Göttingen)

"Suprema of chaos processes and the restricted isometry property"


Date: Mon, April 27, 2015
Time: 17:15
Place: Research II Lecture Hall

Abstract: Variants of the restricted isometry property (RIP) are important tools for the mathematical analysis of various problems in signal processing. In this talk, we consider applications in compressed sensing and blind deconvolution. The theory of compressed sensing considers the following problem: Let \(A\in \mathbb{C}^{m\times n}\) and let \(x \in \mathbb{C}^n\) be \(s\)-sparse, i.e., \(x_i = 0\) for all but \(s\) indices \(i\). One seeks to recover \(x\) uniquely and efficiently from linear measurements \(y = Ax\), although \(m\ll n\). In such problem, the RIP provides a sufficient condition to ensure that this is possible. \(A\) is said to have the RIP, if its restriction to any small subset of the columns acts almost like an isometry.

We study two classes of matrices with respect to the RIP: First, we consider matrices \(A\) which represent the convolution with a random vector \(\epsilon\) followed by a restriction to an arbitrary fixed set of entries. We focus on the scenario that \(\epsilon\) is 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 certain blind deconvolution problems, a variant of the RIP also plays an important role, but the (reformulated) measurement operation needs to be an approximate isometry on matrices that are sparse and low rank rather than just sparse vectors.

All these problems under appropriate randomizations that are closely related to suprema of chaos processes. For the compressed sensing problems, for example, one needs to estimate random variables of the form \[ D_{\mathcal{A}}:=\sup\limits_{A\in\mathcal{A}} \left|\| A \epsilon\|^2 - \mathbb{E} \|A \epsilon\|^2 \right|, \] where \(\mathcal{A}\) is a set of matrices. For the blind deconvolution problem, one obtains related expressions. Using generic chaining techniques, we derive a bound for the moments of \(D_{\mathcal{A}}\) in terms of the Talagrand \(\gamma_2\)-functional. As a consequence, we obtain that the two classes of matrices mentioned above have the RIP with high probability if the embedding dimension satisfies \(m \geq Cs \log(n)^4\). This bound exhibits optimal dependence on \(s\), while previous works had only obtained a suboptimal scaling of \(s^{3/2}\). Also the blind deconvolution problem can be analysed in a related way.

This talk is based on joint works with Shahar Mendelson and Holger Rauhut, and with Ali Ahmed and Justin Romberg.

The colloquium is preceded by tea from 16:45 in the Resnikoff Mathematics Common Room, Research I, 127.