Random epsilon-nets and embeddings in l(infinity)(N)
Résumé
We show that, given an n-dimensional normed space X, a sequence of N = (8/epsilon)(2n) independent random vectors (X-i)(i=1)(N), uniformly distributed in the unit ball of X*, with high probability forms an epsilon-net for this unit ball. Thus the random linear map Gamma : R-n -> R-N defined by Gamma x = (< x, X-i >)(i=1)(N) embeds X in l(infinity)(N) with at most 1 + epsilon norm distortion. In the case X = l(2)(n) we obtain a random 1 + epsilon-embedding into l(infinity)(N) with asymptotically best possible relation between N, n, and epsilon.