Random $\varepsilon$-nets and embeddings in $\ell^N_{\infty}$
Volume 178 / 2007
Studia Mathematica 178 (2007), 91-98
DOI: 10.4064/sm178-1-6
Abstract
We show that, given an $n$-dimensional normed space $X$, a sequence of $N = (8/\varepsilon)^{2n}$ independent random vectors $(X _i)_{i=1}^N$, uniformly distributed in the unit ball of $X^*$, with high probability forms an $\varepsilon$-net for this unit ball. Thus the random linear map $\varGamma:\mathbb R \rightarrow \mathbb{R}^N$ defined by $\varGamma x = (\langle x, X_i\rangle)_{i=1}^N$ embeds $X$ in $\ell^N_\infty$ with at most $1+\varepsilon$ norm distortion. In the case $X = \ell_2^n$ we obtain a random $1+\varepsilon$-embedding into $\ell_\infty^N$ with asymptotically best possible relation between $N$, $n$, and $\varepsilon$.
