Generalizing the Johnson–Lindenstrauss lemma to $k$-dimensional affine subspaces
Volume 195 / 2009
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$.
