Question

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?

Answer 1

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$.