How well do random projections preserve the distance between a point and a linear subspace? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T17:40:37Z http://mathoverflow.net/feeds/question/120611 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120611/how-well-do-random-projections-preserve-the-distance-between-a-point-and-a-linear How well do random projections preserve the distance between a point and a linear subspace? Florian 2013-02-02T20:12:06Z 2013-02-02T22:55:04Z <p>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$. </p> <p>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$. </p> <p>My question is, what is the best bound on $|d(y, S) - d(Py, PS)|$? </p> <p>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? </p> http://mathoverflow.net/questions/120611/how-well-do-random-projections-preserve-the-distance-between-a-point-and-a-linear/120630#120630 Answer by Bill Johnson for How well do random projections preserve the distance between a point and a linear subspace? Bill Johnson 2013-02-02T22:55:04Z 2013-02-02T22:55:04Z <p>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$. </p>