PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2007 | 178 | 1 | 91-98
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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 ε.
Słowa kluczowe
Czasopismo
Rocznik
Tom
178
Numer
1
Strony
91-98
Opis fizyczny
Daty
wydano
2007
Twórcy
autor
  • Department of Mathematics, Technion, Haifa 32000, Israel
autor
  • Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, AB, Canada T6G 2G1
autor
  • É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
  • Department of Mathematical and Statistical Sciences, University of Alberta, Edmonton, AB, Canada T6G 2G1
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_4064-sm178-1-6
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.