Reconstruction and subgaussian operators

Abstract

We present a randomized method to approximate any vector $v$ from some set $T\subset {\mathbb{R}}^n$. The data one is given is the set $T$, and $k$ scalar products $(\inr{X_i,v})_{i=1}^k$, where $(X_i{)}_{i=1}^k$ are i.i.d. isotropic subgaussian random vectors in ${\mathbb{R}}^n$, and $k\ll n$. We show that with high probability, any $y\in T$ for which $(\inr{X_i,y})_{i=1}^k$ is close to the data vector $(\inr{X_i,v})_{i=1}^k$ will be a good approximation of $v$, and that the degree of approximation is determined by a natural geometric parameter associated with the set $T$. We also investigate a random method to identify exactly any vector which has a relatively short support using linear subgaussian measurements as above. It turns out that our analysis, when applied to $\{-1,1\}$-valued vectors with i.i.d, symmetric entries, yields new information on the geometry of faces of random $\{-1,1\}$-polytope; we show that a $k$-dimensional random $\{-1,1\}$-polytope with $n$ vertices is $m$-neighborly for very large $m\le ck/\log (c^{\prime }n/k)$. The proofs are based on new estimates on the behavior of the empirical process $\sup_{f \in F} |k^{-1}\sum_{i=1}^k f^2(X_i) -\E f^2 |$ when $F$ is a subset of the $L_2$ sphere. The estimates are given in terms of the ${\gamma }_2$ functional with respect to the ${\psi }_2$ metric on $F$, and hold both in exponential probability and in expectation.

31 pages; no figures; submitted

References in corpus (1)

• Decoding by Linear Programming