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 R, and N. We show that with high probability, any which is close to the data vector will be a good approximation of R, 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 n/k. 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.