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

Alon Dmitriyuk, and Yehoram Gordon. "Generalizing the Johnson-Lindenstrauss lemma to k-dimensional affine subspaces." Studia Mathematica 195.3 (2009): 227-241. <http://eudml.org/doc/285147>.

@article{AlonDmitriyuk2009,
abstract = {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.},
author = {Alon Dmitriyuk, Yehoram Gordon},
journal = {Studia Mathematica},
keywords = {local theory; Gaussian processes; high dimensional geometry; convexity; normed linear spaces; Gaussian operators},
language = {eng},
number = {3},
pages = {227-241},
title = {Generalizing the Johnson-Lindenstrauss lemma to k-dimensional affine subspaces},
url = {http://eudml.org/doc/285147},
volume = {195},
year = {2009},
}

TY - JOUR
AU - Alon Dmitriyuk
AU - Yehoram Gordon
TI - Generalizing the Johnson-Lindenstrauss lemma to k-dimensional affine subspaces
JO - Studia Mathematica
PY - 2009
VL - 195
IS - 3
SP - 227
EP - 241
AB - 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.
LA - eng
KW - local theory; Gaussian processes; high dimensional geometry; convexity; normed linear spaces; Gaussian operators
UR - http://eudml.org/doc/285147
ER -