Reconstruction and subgaussian operators

We present a randomized method to approximate any vector $v$ from some set $T \subset \R^n$\mathrm{.}Thedataoneisgivenistheset$T$,and$k$scalarproducts$(\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 $(\text{inr}{X}_i,y{)}_{i=1}^k$ is close to the data vector $(\text{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’ n/k)}$. The proofs are based on new estimates on the behavior of the empirical process ${\sup }_{f\in F}\mathrm{\mid }{k}^{-1}{\sum }_{i=1}^k{f}^2(X_i)-\text{E}{f}^2\mathrm{\mid }$ 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.