Reconstruction and subgaussian operators

Original · EN

We present a randomized method to approximate any vector v from some set T ⊂ ⁿ. The data one is given is the set T, and k scalar products (Xᵢ,v)ᵢ₌₁ᵏ, where (Xᵢ)ᵢ₌₁ᵏ are i.i.d. isotropic subgaussian random vectors in ⁿ, and k ≪ n. We show that with high probability, any y ∈ T for which (Xᵢ,y)ᵢ₌₁ᵏ is close to the data vector (Xᵢ,v)ᵢ₌₁ᵏ 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≤ ck/ (c' n/k). The proofs are based on new estimates on the behavior of the empirical process ∈ F |k⁻¹∑ᵢ₌₁ᵏ f²(Xᵢ) - f² | 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.