Random ε-nets and embeddings in ${\ell }_{\infty }^N$

Y. Gordon, et al. "Random ε-nets and embeddings in $ℓ^{N}_{∞}$." Studia Mathematica 178.1 (2007): 91-98. <http://eudml.org/doc/286510>.

@article{Y2007,
abstract = {We show that, given an n-dimensional normed space X, a sequence of $N = (8/ε)^\{2n\}$ 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 $Γ: ℝ → ℝ^\{N\}$ defined by $Γx = (⟨x,X_\{i\}⟩)_\{i=1\}^\{N\}$ embeds X in $ℓ^\{N\}_\{∞\}$ with at most 1 + ε norm distortion. In the case X = ℓ₂ⁿ we obtain a random 1+ε-embedding into $ℓ_\{∞\}^\{N\}$ with asymptotically best possible relation between N, n, and ε.},
author = {Y. Gordon, A. E. Litvak, A. Pajor, N. Tomczak-Jaegermann},
journal = {Studia Mathematica},
keywords = {Dvoretzky's theorem; random embeddings into ; random -nets},
language = {eng},
number = {1},
pages = {91-98},
title = {Random ε-nets and embeddings in $ℓ^\{N\}_\{∞\}$},
url = {http://eudml.org/doc/286510},
volume = {178},
year = {2007},
}

TY - JOUR
AU - Y. Gordon
AU - A. E. Litvak
AU - A. Pajor
AU - N. Tomczak-Jaegermann
TI - Random ε-nets and embeddings in $ℓ^{N}_{∞}$
JO - Studia Mathematica
PY - 2007
VL - 178
IS - 1
SP - 91
EP - 98
AB - We show that, given an n-dimensional normed space X, a sequence of $N = (8/ε)^{2n}$ 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 $Γ: ℝ → ℝ^{N}$ defined by $Γx = (⟨x,X_{i}⟩)_{i=1}^{N}$ embeds X in $ℓ^{N}_{∞}$ with at most 1 + ε norm distortion. In the case X = ℓ₂ⁿ we obtain a random 1+ε-embedding into $ℓ_{∞}^{N}$ with asymptotically best possible relation between N, n, and ε.
LA - eng
KW - Dvoretzky's theorem; random embeddings into ; random -nets
UR - http://eudml.org/doc/286510
ER -