Reconstruction and Subgaussian Operators in Asymptotic Geometric Analysis

We present a randomized method to approximate any vector from a set . The data one is given is the set T, vectors of and k scalar products , where are i.i.d. isotropic subgaussian random vectors in , and . We show that with high probability, any for which is close to the data vector will be a good approximation of , 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 The proofs are based on new estimates on the behavior of the empirical process 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. Received: November 2005, Revision: May 2006, Accepted: June 2006