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 ?

  • $\begingroup$ What is your question exactly? $\endgroup$ – Dustin G. Mixon Dec 28 '13 at 14:44
  • $\begingroup$ Hi D., my question would be: how would one treat arbitrary vectors ? Is the guess true ? $\endgroup$ – Xorwell Dec 28 '13 at 15:36
  • $\begingroup$ Don't get me wrong - I read what you already wrote, but it is not clear what you are asking. Consider rephrasing the question. $\endgroup$ – Dustin G. Mixon Dec 28 '13 at 15:44
  • $\begingroup$ I tried rephrasing. Hope this clarify. If not, what is more obscure? $\endgroup$ – Xorwell Dec 28 '13 at 16:05
  • $\begingroup$ 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$? $\endgroup$ – Dustin G. Mixon Dec 28 '13 at 16:17

This is more of a long comment than an answer:

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

  • $\begingroup$ 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)$. $\endgroup$ – Xorwell Dec 28 '13 at 17:06
  • $\begingroup$ I added $N(0,1)$ hypothesis to the original question. $\endgroup$ – Xorwell Dec 28 '13 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.