Empirical approximation of the gaussian distribution in Rd

Abstract

Let G1,…,Gm be independent copies of the standard gaussian random vector in Rd. We show that there is an absolute constant c such that for any A⊂Sd−1, with probability at least 1−2exp⁡(−cΔm), for every t∈R, supx∈A⁡|[Formula presented]∑i=1m1{〈Gi,x〉≤t}−P(〈G,x〉≤t)|≤Δ+σ(t)Δ. Here σ(t) is the variance of 1{〈G,x〉≤t} and Δ≥Δ0, where Δ0 is determined by an unexpected complexity parameter of A that captures the set's geometry (Talagrand's γ1 functional). The bound, the probability estimate, and the value of Δ0 are all (almost) optimal. We use this fact to show that if Γ=∑i=1m〈Gi,x〉ei is the random matrix that has G1,…,Gm as its rows, then the structure of Γ(A)={Γx:x∈A} is far more rigid and well-prescribed than was previously expected. Show more