A+ CATEGORY SCIENTIFIC UNIT

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

Volume 195 / 2009

Alon Dmitriyuk, Yehoram Gordon Studia Mathematica 195 (2009), 227-241 MSC: 46B09, 46B07. DOI: 10.4064/sm195-3-3

Abstract

Let $\varepsilon>0$ and $1\leq k\leq n$ and let $\{W_l\}_{l=1}^{p}$ be affine subspaces of $\mathbb{R}^n$, each of dimension at most $k$. Let $m=O(\varepsilon^{-2}(k+\log{p}))$ if $\varepsilon< 1$, and $m=O(k+{\log{p}}/{\!\log(1+\varepsilon)})$ if $\varepsilon\geq1$. We prove that there is a linear map $H:\mathbb{R}^n\rightarrow\mathbb{R}^m$ such that for all $1\leq l\leq p$ and $x,y\in W_l$ we have $\|x-y\|_2\leq\|H(x)-H(y)\|_2\leq(1+\varepsilon)\|x-y\|_2$, i.e. the distance distortion is at most $1+\varepsilon$. The estimate on $m$ is tight in terms of $k$ and $p$ whenever $\varepsilon<1$, and is tight on $\varepsilon,k,p$ whenever $\varepsilon\geq1$. We extend these results to embeddings into general normed spaces $Y$.

Authors

  • Alon DmitriyukDepartment of Mathematics
    Technion
    Haifa 32000, Israel
    e-mail
  • Yehoram GordonDepartment of Mathematics
    Technion
    Haifa 32000, Israel
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image