Random ε-nets and embeddings in $ℓ^{N}_{∞}$

Y. Gordon; A. E. Litvak; A. Pajor; N. Tomczak-Jaegermann

Random ε-nets and embeddings in

ℓ_{\infty}^{N}

Y. Gordon ; A. E. Litvak ; A. Pajor ; N. Tomczak-Jaegermann

Studia Mathematica, Tome 178 (2007), p. 91-98 / Harvested from The Polish Digital Mathematics Library

Access to full text
Full (PDF)

Résumé

We show that, given an n-dimensional normed space X, a sequence of $N = {(8 / ε)}^{2 n}$ independent random vectors ${(X_{i})}_{i = 1}^{N}$ , uniformly distributed in the unit ball of X*, with high probability forms an ε-net for this unit ball. Thus the random linear map $Γ : ℝ \to ℝ^{N}$ defined by $Γ x = {(⟨ x, X_{i} ⟩)}_{i = 1}^{N}$ embeds X in $ℓ_{\infty}^{N}$ with at most 1 + ε norm distortion. In the case X = ℓ₂ⁿ we obtain a random 1+ε-embedding into $ℓ_{\infty}^{N}$ with asymptotically best possible relation between N, n, and ε.

Publié le : 2007-01-01

Zbl 1126.46006

EUDML-ID : urn:eudml:doc:286510

@article{bwmeta1.element.bwnjournal-article-doi-10_4064-sm178-1-6,
     author = {Y. Gordon and A. E. Litvak and A. Pajor and N. Tomczak-Jaegermann},
     title = {Random e-nets and embeddings in $l^{N}\_{[?]}$
            },
     journal = {Studia Mathematica},
     volume = {178},
     year = {2007},
     pages = {91-98},
     zbl = {1126.46006},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-sm178-1-6}
}

Y. Gordon; A. E. Litvak; A. Pajor; N. Tomczak-Jaegermann. Random ε-nets and embeddings in $ℓ^{N}_{∞}$
            . Studia Mathematica, Tome 178 (2007) pp. 91-98. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-sm178-1-6/