PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2009 | 195 | 3 | 227-241
Tytuł artykułu

Generalizing the Johnson-Lindenstrauss lemma to k-dimensional affine subspaces

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Let ε > 0 and 1 ≤ k ≤ n and let ${W_{l}}_{l=1}^{p}$ be affine subspaces of ℝⁿ, each of dimension at most k. Let $m = O(ε^{-2}(k + log p))$ if ε < 1, and m = O(k + log p/log(1 + ε)) if ε ≥ 1. We prove that there is a linear map $H: ℝⁿ → ℝ^{m}$ such that for all 1 ≤ l ≤ p and $x,y ∈ W_{l}$ we have ||x-y||₂ ≤ ||H(x)-H(y)||₂ ≤ (1+ε)||x-y||₂, i.e. the distance distortion is at most 1 + ε. The estimate on m is tight in terms of k and p whenever ε < 1, and is tight on ε,k,p whenever ε ≥ 1. We extend these results to embeddings into general normed spaces Y.
Słowa kluczowe
Czasopismo
Rocznik
Tom
195
Numer
3
Strony
227-241
Opis fizyczny
Daty
wydano
2009
Twórcy
  • Department of Mathematics, Technion, Haifa 32000, Israel
  • Department of Mathematics, Technion, Haifa 32000, Israel
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_4064-sm195-3-3
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ć.