Return to 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 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 ?

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 ?

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 computed as in JL, then we pick an arbitrary (random) $z\in \mathbb{R}^d$, 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 ?

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 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 ?

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, how would you treat arbitrary vectors in $\mathbb{R}^d$, that are not necessarily fixed by $X$ ?

In particular, suppose $X$ is fixed, but we also pick any arbitrary (random) $z\in \mathbb{R}^d$ and we look at the distortion between $z$ and $x$, for every $x\in X$.

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

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 computed as in JL, then we pick an arbitrary (random) $z\in \mathbb{R}^d$, 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 ?