# Probabilistic Johnson-Lindenstrauss Lemma for arbitrary points

Consider the following standard formulation of the Johnson-Lindenstrauss lemma:

Lemma (JL).
For any $0<\epsilon < 1$ and any integer $n$, let $k$ be a positive integer such that $k\geq C\cdot \epsilon^{-2}\log n$ (for some explicit constant $C$ which we omit here). Then, for any set $X$ of $n$ points in $\mathbb{R}^d$, there is a linear map $f:\mathbb{R}^d\rightarrow \mathbb{R}^k$ such that for all $u,v\in X$, it holds;

$||u-v||^2(1-\epsilon) \leq ||f(u)- f(v)||^2 \leq ||u-v||^2(1+\epsilon)$.

Moreover, $f$ can be found in randomized polynomial time.

Now, what can be said about probabilistic $(1+\epsilon)$ distortion of arbitrary vectors in $\mathbb{R}^d$, that are not necessarily drawn from $X$ ?

In particular, suppose $X$ is fixed and $f$ is randomly computed as in JL, then we pick an arbitrary $z\in \mathbb{R}^d$ at random, with independent normally distributed coordinates, i.e. $z_i\sim N(0,1)$, not necessarily in $X$, and we look at the distortion between $z$ and $x$, for every $x\in X$: can we appropriately bound the probability to get $(1+\epsilon)$ distortion w.r.t. $z,x$ ?

I guess it is possible to appropriately bound, and then amplify, the probability $\delta$ that an arbitrary (random) $z\in \mathbb{R}^d$ will be distorted by at most $(1+\epsilon)$ relative error w.r.t $X$, as above. Is this guess true ?

• What is your question exactly? – Dustin G. Mixon Dec 28 '13 at 14:44
• Hi D., my question would be: how would one treat arbitrary vectors ? Is the guess true ? – Xorwell Dec 28 '13 at 15:36
• Don't get me wrong - I read what you already wrote, but it is not clear what you are asking. Consider rephrasing the question. – Dustin G. Mixon Dec 28 '13 at 15:44
• I tried rephrasing. Hope this clarify. If not, what is more obscure? – Xorwell Dec 28 '13 at 16:05
• Let $f$ be a random projection. Then it will be JL with high probability, regardless of $X$. If I make $X$ a little larger (by including $z$), $f$ will still be JL with high probability. Is this useful to you, or do you want to fix $f$ and only use the randomness in $z$? – Dustin G. Mixon Dec 28 '13 at 16:17

Let's assume $f$ is a $k\times d$ matrix with orthogonal rows, each with norm $\sqrt{d/k}$ (random $f$'s of this form are known to satisfy JL). Consider the function on the sphere $\sigma\colon S^{d-1}\rightarrow\mathbb{R}$ defined by $\sigma(v)=\|f(v)\|$. This function is maximized at vectors in the rowspace of $f$, and minimized at vectors in the nullspace, and somewhere in between is the inverse image of $[1-\epsilon,1+\epsilon]$. This can be viewed as a thickened version of $\sigma^{-1}(\{1\})$, which should be a $(d-2)$-dimensional algebraic variety.
Now draw $z$ at random (according to some distribution). We succeed if
$$v_x:=\frac{x-z}{\|x-z\|}\in \sigma^{-1}\big([1-\epsilon,1+\epsilon]\big)\quad \forall x\in X.$$
Unfortunately, the $v_x$'s are dependent, so you should probably focus on $v_x$ for a single $x$, and then perform a union bound. To do this, you first need to define a distribution for $z$.
• Thank you for answer. Well, we can assume $z$ to be drawn with normal gaussian distribution, i.e. each coordinate is drawn according to $N(0,1)$. – Xorwell Dec 28 '13 at 17:06
• I added $N(0,1)$ hypothesis to the original question. – Xorwell Dec 28 '13 at 17:24