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?