Probabilistic Johnson-Lindenstrauss Lemma for arbitrary points

Question

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 ?

Answer 1

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