Reconstruction and Subgaussian Operators in Asymptotic Geometric Analysis

Abstract.

We present a randomized method to approximate any vector $\upsilon$ from a set $T \subset {\mathbb{R}}^n$. The data one is given is the set T, vectors $(X_i)^{k}_{i=1}$ of ${\mathbb{R}}^n$ and k scalar products $(\langle X_i, \upsilon\rangle)^{k}_{i=1}$, where $(X_i)^k_{i=1}$ 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 $(\langle X_i, y\rangle)^k_{i=1}$ is close to the data vector $(\langle X_i, \upsilon\rangle)^k_{i=1}$ will be a good approximation of $\upsilon$, 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 a random {−1, 1}-polytope; we show that a k- dimensional random {−1, 1}-polytope with n vertices is m-neighborly for $m \leq ck/ log(c^{\prime}n/k).$

The proofs are based on new estimates on the behavior of the empirical process $\text{sup}_{f \in F}\vert k^{-1}\sum^{k}_{i=1} f^{2}(X_{i}) - \mathbb{E} f^{2}\vert$ when F is a subset of the L ₂ sphere. The estimates are given in terms of the γ ₂ functional with respect to the ψ ₂ metric on F, and hold both in exponential probability and in expectation.