Empirical approximation of $L^p$ norms for $p\in (1,2)$

Abstract

For $p\in [1,2]$, we prove uniform moment estimates for weighted sums \[ \sum_{j=1}^mζ_jw_j|\langle{\bf v}_j,y\rangle|^p \] of independent subgaussian random variables ${\zeta }_j$, where the unit vectors $\{{\mathbf{v}}_j{\}}_{j=1}^m$ and nonnegative weights $\{w_j{\}}_{j=1}^m$ form an isotropic frame. This allows us to obtain optimal sampling discretization of $L_p$ norms for each fixed $p\in [1,2]$. Namely, for an $N$-dimensional space $X_N$ of bounded functions satisfying $\Vert f{\Vert }_{\infty }\le \sqrt{KN}\Vert f{\Vert }_{L_2}$ for every $f\in X_N$, we show that $m\ge C{\epsilon }^{-2}KN\log (2N)$ independent samples ${\xi }^1,\dots ,{\xi }^m$ provide the discretization \[ (1-\varepsilon)\|f\|_{L_p}^p \le\frac1m\sum_{j=1}^m|f(ξ^j)|^p \le(1+\varepsilon)\|f\|_{L_p}^p \quad\forall f\in X_N \] with probability at least $1-\exp (-c\frac{m{\epsilon }^2}{KN})$. This implies a corresponding weighted discretization result that, for $1<p<2$, improves Talagrand's bound on the dimension $m$ needed to embed $N$-dimensional subspaces of $L_p$ into ${\ell }_p^m$ with distortion at most $1+\epsilon$, giving $m\le C{\epsilon }^{-2}N\log (2N)$.