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

• Autorzy: Y. Gordon , A. E. Litvak , A. Pajor , N. Tomczak-Jaegermann
• Języki publikacji: EN

Abstrakty

EN

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 ε.

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Studia Mathematica
• Rocznik: 2007
• Tom: 178
• Numer: 1
• Strony: 91-98

Daty

wydano

2007

Twórcy

autor

Y. Gordon

• Department of Mathematics, Technion, Haifa 32000, Israel

autor

A. E. Litvak

• Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, AB, Canada T6G 2G1

autor

A. Pajor

• Équipe d'Analyse et Mathématiques Appliquées, Université de Marne-la-Vallée, 5, boulevard Descartes, Champs sur Marne, 77454 Marne-la-Vallée, Cedex 2, France

autor

N. Tomczak-Jaegermann

• Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, AB, Canada T6G 2G1

Identyfikatory

DOI

10.4064/sm178-1-6