Let $x\_1,\ldots,x\_k \in \mathbb{R}^d$ be $k$ unit vectors in $d$ dimensional Euclidean space, and let $S = \mathrm{span}(x\_1,\ldots,x\_k)$ be a linear subspace defined by these points. Let $P \in \mathbb{R}^{\ell\times d}$ be a $\ell\times d$ random projection matrix as specified by the Johnson-Lindenstrauss lemma, for $\ell \approx O(\log k/\epsilon^2)$. Let $y \in \mathbb{R}^d$ be an arbitrary unit vector, and define $d(y, S) = \min\_{x \in S}||x-y||$ to be the distance between $y$ to the subspace $S$. 


Let $PS = \mathrm{span}(Px\_1,\ldots,Px\_k)$ be the projection of the subspace $S$, and let $Py \in \mathbb{R}^\ell$ be the projection of $y$. 


My question is, what is the best bound on $|d(y, S) - d(Py, PS)|$? 


The Johnson Lindenstrauss lemma promises that with high probability, for all $i$, $|||y - x\_i|| - ||Py - Px\_i||| \leq \epsilon$, and an easy calculation shows that therefore $|d(y, S) - d(Py, PS)| \leq k\epsilon$. However, is a better (e.g. logarithmic) dependence on $k$ possible? 



How well do random projections preserve the distance between a point and a linear subspace?
Gideon Schechtman and I thought through this. First, you need to multiply the random projection $P$ by a factor that is of order $(d/\ell)^{1/2}$ to have the distances preserved; i.e., where you wrote $P$ you should have written this constant times $P$. Secondly, you need $\ell \ge k$ else the image of the $k$ dimensional subspace will be onto the range of $P$ with probability one. Thirdly, to almost preserve the distance of $y$ to the $k$ dimensional subspace you only need to almost preserve the distance to an $\epsilon$ net of the unit sphere of the subspace, which has cardinality like $\epsilon^{-k}$, which JL says you can do by taking $\ell$ larger than some constant times $k$. 


