Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider a set of points $\{\mathbf{x}_i\}_{i=1}^N$ in a $d$-dimensional linear subspace of $\mathbb{R}^n$ (assume $\{\mathbf{x}_i\}$ span the subspace). The points are projected to a $k$-dimensional space ($k > d$, let's call it target space) using a random matrix $\mathbf{\Phi}$, i.e. $\mathbf{x}_i' = \mathbf{\Phi}\mathbf{x}_i$. From the Johnson-Lindenstrauss lemma we know that the pairwise distances between the points are (for appropriate choice of $\mathbf{\Phi}$) up to $\pm \epsilon$ with high probability.

Is it possible to model the points in the target space as $\mathbf{x}_i'= \mathbf{x}''_i+\mathbf{e}_i$ with $\lVert\mathbf{e}_i\rVert_2 \leq \delta = O(\epsilon)$ and $\lVert\mathbf{x}''_i-\mathbf{x}''_j\rVert_2 = \lVert \mathbf{x}_i-\mathbf{x}_j\rVert_2$ for all pairs $(i,j)$? In other words, are subspaces preserved up to a small, bounded perturbation?

share|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.