Department of Mathematics

Applied Mathematics

  •  Shahar Mendelson, Australian National University
  •  Approximating L_p balls via sampling
  •  04/22/2021
  •  4:30 AM - 5:30 AM
  •  Online (virtual meeting) (Virtual Meeting Link)
  •  Olga Turanova (

Let X be a centred random vector in R^n. The L_p norms that X endows on R^n are defined by \|v\|_{L_p}= (E|<X,v>|^p)^{1/p}. The goal is to approximate those L_p norms, and the given data consists of N independent sample points X_1,...,X_N distributed as X. More accurately, one would like to construct data-dependent functionals \phi_{p,\epsilon} which satisfy with (very) high probability, that for every v in R^n, (1-\epsilon) \phi_{p,\epsilon} \leq E|<X,v>|^p \leq (1+\epsilon) \phi_{p,\epsilon}. I will show that the functionals \frac{1}{N}\sum_{j \in J} |<X_j,v>|^p are a good choice, where the set of indices J is obtained from \{1,...,N\} by removing the c\eps^2 N largest values of |<X_j,v>|. Under mild assumptions on X, only N=(c^p)\epsilon^{-2} n measurements are required, and the probability that the functional performs well is at least 1-2\exp(-c\epsilon^2 N).



Department of Mathematics
Michigan State University
619 Red Cedar Road
C212 Wells Hall
East Lansing, MI 48824

Phone: (517) 353-0844
Fax: (517) 432-1562

College of Natural Science