Skip to Main content Skip to Navigation
Journal articles

Random epsilon-nets and embeddings in l(infinity)(N)

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00693709
Contributor : Admin Lama <>
Submitted on : Wednesday, May 2, 2012 - 10:46:30 PM
Last modification on : Thursday, March 19, 2020 - 12:26:02 PM

Links full text

Identifiers

Citation

Y. Gordon, A. E. Litvak, Alain Pajor, N. Tomczak-Jaegermann. Random epsilon-nets and embeddings in l(infinity)(N). Studia Mathematica, INSTYTUT MATEMATYCZNY * POLSKA AKADEMIA NAUK, 2007, 178 (1), pp.91--98. ⟨10.4064/sm178-1-6⟩. ⟨hal-00693709⟩

Share

Metrics

Record views

397