## 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.