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

Alon Dmitriyuk¹ ; Yehoram Gordon¹

¹ Department of Mathematics Technion Haifa 32000, Israel

Studia Mathematica, Tome 195 (2009) no. 3, pp. 227-241

Résumé

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 $\varepsilon1$, and is tight on $\varepsilon,k,p$ whenever $\varepsilon\geq1$. We extend these results to embeddings into general normed spaces $Y$.

Détail

DOI : 10.4064/sm195-3-3

Keywords: varepsilon leq leq affine subspaces mathbb each dimension varepsilon log varepsilon log log varepsilon varepsilon geq prove there linear map mathbb rightarrow mathbb leq leq have x y leq h leq varepsilon x y distance distortion varepsilon estimate tight terms whenever varepsilon tight varepsilon whenever varepsilon geq extend these results embeddings general normed spaces