Reconstruction and Subgaussian Operators in Asymptotic Geometric Analysis

Research paper by Shahar Mendelson, Alain Pajor, Nicole Tomczak-Jaegermann

Indexed on: 30 Aug '07Published on: 30 Aug '07Published in: Geometric and Functional Analysis


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 L2 sphere. The estimates are given in terms of the γ2 functional with respect to the ψ2 metric on F, and hold both in exponential probability and in expectation.