Shahar Mendelson

Approximating Lₚ balls via sampling

Let X be a centred random vector in Rⁿ. The Lₚ norms that X endows on Rⁿ are defined by ‖v‖_L__ₚ= (E||ᵖ)¹/ᵖ. The goal is to approximate those Lₚ norms, and the given data consists of N independent sample points X₁,...,X_N distributed as X. More accurately, one would like to construct data−dependent functionals ϕₚ,ε which satisfy with (very) high probability, that for every v in Rⁿ, (1−ε) ϕₚ,ε ≤ E||ᵖ ≤ (1+ε) ϕₚ,ε. I will show that the functionals \frac{1}{N}∑ⱼ∈J ||ᵖ are a good choice, where the set of indices J is obtained from {1,...,N} by removing the cε²N largest values of ||. Under mild assumptions on X, only N=(cᵖ)ε⁻²n measurements are required, and the probability that the functional performs well is at least 1−2\exp(−cε² N).