Random version of Dvoretzky's theorem in ${\ell }_p^n$

Abstract

We study the dependence on $\epsilon$ in the critical dimension $k(n,p,\epsilon )$ for which one can find random sections of the ${\ell }_p^n$-ball which are $(1+\epsilon )$-spherical. We give lower (and upper) estimates for $k(n,p,\epsilon )$ for all eligible values $p$ and $\epsilon$ as $n\to \infty$, which agree with the sharp estimates for the extreme values $p=1$ and $p=\infty$. Toward this end, we provide tight bounds for the Gaussian concentration of the ${\ell }_p$-norm.

45 pages; final revision; to appear in Stochastic Processes and their Applications

References in corpus (1)

• Some superconcentration inequalities for extrema of stationary Gaussian Processes

Cited by in corpus (4)

• A law of robustness for two-layers neural networks
• On ${\ell }_p$-Gaussian-Grothendieck problem
• On Dvoretzky's theorem for subspaces of $L_p$
• Non-PSD Matrix Sketching with Applications to Regression and Optimization