Johnson-Lindenstrauss Lemma

Problem

Let $\mathcal{U} \subseteq \mathbb{R}^d$ be a set of $n$ points. We want to find a linear transformation $A \in \mathbb{R}^{k \times d}$ that embeds the points in $\mathcal{U}$ to $\mathbb{R}^k$ while preserving the pairwise Euclidean distances.

If $k \ge d$, the problem is trivial. There is an isomorphic mapping between $\mathbb{R}^d$ and a $d$-dimensional subspace in $\mathbb{R}^k$. Let $u_1, \ldots, u_d$ be a subset of standard basis vectors in $\mathbb{R}^k$, and $e_1, \ldots, e_d$ be standard basis vectors in $\mathbb{R}^d$. Then one possible isomorphic mapping is given by

If $k < d$, then such an isomorphic embedding is impossible. However, it is feasible, if we aim to preserve the pair-wise distance up to a multiplicative error $\epsilon \in (0, 1)$ with high probability, s.t., $\forall x, y \in \mathcal{U}$,

where $\Vert \cdot \Vert_2$ is the $\ell_2$ distance.

The smaller $k$ is, the less space we need to store the embedded vectors

It remains to study how small $k$ can be?

Theorem. For each set $\mathcal{U} \subseteq \mathbb{R}^d$ of $n$ points, there is a matrix $A \in \mathbb{R}^{k \times d}$, such that $k = O\left( \frac{ \log n }{ \epsilon^2} \right)$ and

$$\forall x, y \in \mathcal{U}, \quad \Vert A x - A y \Vert_2 \in (1 \pm \epsilon) \Vert x - y \Vert_2,$$

Further, there is an algorithm which returns such a matrix $A$ with success probability at least $1 - \frac{1}{n}$

The value of $k$ depends only on $n$ but not $d$.

Column Perspective

On the high level, we try to squeeze $d$ (in expectation) orthonormal vectors into a smaller space $\mathbb{R}^k$. We do this by generating a set of $d$ random vectors $u_1, u_2, \ldots, u_d \in \mathbb{R}^k$, such that:

1. Each coordinate of $u_i$ is generated independently for $i \in [d]$;

and in expectation, they are orthonormal:

2. $\mathbb{E} \left[ \Vert u_i \Vert_2^2 \right] = 1$ for $i \in [d]$;
3. $\mathbb{E} \left[ \langle u_i, u_j \rangle \right] = 0$ for $i, j \in [d], i \neq j$.

Let $e_1, \ldots, e_d \in \mathbb{R}^d$ be unit vectors in $\mathbb{R}^d$ and $e_i$ ($i \in [d]$) has the $i$-th entry equal to 1. Define

For a fixed pair $x, y \in \mathcal{U}$, define $z = x - y$. Then

Taking expectation of both side, and by assumption of $v_t, t \in [d]$, it holds that

Row Perspective

We can also characterize $A$ by the properties of its rows. Let $\tilde A$ be a scaled version of $A$, such that

Denote $v_1, v_2, \ldots, v_k \in \mathbb{R}^d$ the row vectors of $\tilde A$. They are generated randomly and independently. Each vector $v_i$ ($i \in [k]$) satisfies

1. Each entry of $v_i$ is generated independently;
2. $\mathbb{E} \left[v_i [j] \right] = 0, \forall j \in [d]$, i.e., each entry has mean zero;
3. $\mathbb{Var} \left[ v_i [j] \right] = 1, \forall j \in [d]$, i.e., each entry has variance one.

For a fixed pair $x, y \in \mathcal{U}$, define $z = x - y$. Consider

Our assumption on $v_i, i \in [k]$ implies that the $\langle v_i, z \rangle^2, i \in [k]$ are independent random variables. We will verify that each of them has variance $\Vert z \Vert_2^2$. For each $i \in [k]$,

can be view as the sum of $d$ independent random variables. Hence, by our assumption on $v_i$, we have

By linearity of expectation,

It concludes that

Therefore, $\Vert A z \Vert_2^2$ can be viewed as the average of $k$ independent, mean $\Vert z \Vert_2^2$ random variables. By the law of large numbers, the average should concentrate around $\Vert z \Vert_2^2$. The analysis of the concentration phenomenon depends on the detailed implementation of $\tilde A$.

Gaussian

In this section, we discuss a possible implementation of $A$.

Let $\tilde A \in \mathbb{R}^{k \times d}$ be a random matrix, each entry of which is generated independently from standard normal distribution. Let $\tilde u_1, \ldots, \tilde u_d$ be the column vectors, and $\tilde v_1, \ldots, \tilde v_k$ be the row vectors of $\tilde A$. Define $A \doteq \frac{1}{\sqrt k} \tilde{A}$. Hence, for the column and row vectors of $A$, it holds that $u_i = \frac{1}{\sqrt k} \tilde u_i, i \in [d]$ and $v_i = \frac{1}{\sqrt k} \tilde v_i, i \in [k]$.

It is easy to see that $A$ satisfies previous discussed column and row properties.

Define $\sigma^2 = \Vert z \Vert_2^2$, and

Since each $\tilde{v_i} [j] \sim N(0, 1)$, it follows that $X_i \sim N(0, \sigma^2)$. Then

And

Theorem. (Chernoff bound for the $\chi^2$ distribution). Let $X_i \sim N(0, \sigma^2), i \in [k]$ be independent random variables. Then

$$\begin{aligned} \Pr \left[ \frac{1}{k} \sum_{ i \in [k] } X_i^2 \ge (1 + \epsilon) \cdot \sigma^2 \right] &\le \exp \left( - \frac{k}{2} ( \epsilon^2 / 2 - \epsilon^3 / 3) \right), \\ \Pr \left[ \frac{1}{k} \sum_{ i \in [k] } X_i^2 \le (1 - \epsilon) \cdot \sigma^2 \right] &\le \exp \left( - \frac{k}{4} \epsilon^2 \right). \end{aligned}$$

The proof of the theorem is based on the following lemma.

Lemma. It holds that

$$\begin{aligned} \Pr \left( \Vert A z \Vert_2^2 \ge (1 + \epsilon) \Vert z \Vert_2^2 \right) &\le \exp \left( - \frac{k \cdot (\epsilon - \ln (1 + \epsilon) ) }{2} \right), \\ \Pr \left( \Vert A z \Vert_2^2 \le (1 - \epsilon) \Vert z \Vert_2^2 \right) &\le \exp\left( \frac{k \cdot (\epsilon + \ln (1 - \epsilon) ) }{2} \right). \end{aligned}$$

Proof of the Theorem. As $\forall \epsilon \in [0, 1)$,

we get

and

$\square$

To prove the lemma, we have the following fact.

Fact. (Moment Generating Function of Normal Distribution). Let $X \thicksim N(0,\sigma^2)$, then for $\lambda < \frac{1}{2 \sigma^2}$, we have

$$\mathbb{E} \left[ e^{ \lambda X^2 } \right] = \frac{1}{ \sqrt{ 1 - 2 \sigma^2 \lambda} }.$$

Proof of the Fact.

$\square$

Proof of Lemma. Let $\sigma^2 \doteq \Vert z \Vert_2^2$, and $X_i = \langle v_i, z \rangle, \forall i \in [k]$. Then $X_i, \forall i \in [k]$ are independent normal random variables with variance $\sigma^2$. By the previous fact, for each $\lambda < \frac{1}{2 \sigma^2}$, it holds that

We want to find a $\lambda$ that minimizes the RHS. Let

Taking the derivative with respect to $\lambda$,

Hence $f$ increases when $\lambda < \frac{ \epsilon }{ 2 \cdot \sigma^2 \cdot (1 + \epsilon) }$ and decreases afterwards. It follows that

Similarly, we have

Taking $\lambda = \frac{ \epsilon }{ 2 \cdot \sigma^2 \cdot (1 - \epsilon) }$, we get

$\square$

Rademacher

In this implementation, $\tilde A \in \mathbb{R}^{k \times d}$ is a random matrix, each entry of which is independent Rademacher random variables, which equals $1$ and $-1$ with the equal probability.

Let $\tilde u_1, \ldots, \tilde u_d$ be the column vectors, and $\tilde v_1, \ldots, \tilde v_k$ be the row vectors of $\tilde A$. Define $A \doteq \frac{1}{\sqrt k} \tilde{A}$. Hence, for the column and row vectors of $A$, it holds that $u_i = \frac{1}{\sqrt k} \tilde u_i, i \in [d]$ and $v_i = \frac{1}{\sqrt k} \tilde v_i, i \in [k]$.

It is easy to see that $A$ satisfies previous discussed column and row properties.

As before, let $\sigma^2 = \Vert z \Vert_2^2$, and

Since $\mathbb{E} \left[ \tilde{v_i} [j]^2 \right] = 1$, and $\mathbb{E} \left[ \tilde{v_i} [j] \right] = 0$, we have

And

Theorem. (Chernoff bound for the $\chi^2$ distribution). Let $X_i \sim N(0, \sigma^2), i \in [k]$ be independent random variables. Then

$$\begin{aligned} \Pr \left[ \frac{1}{k} \sum_{ i \in [k] } X_i^2 \ge (1 + \epsilon) \cdot \sigma^2 \right] &\le \exp \left( - \frac{k}{2} ( \epsilon^2 / 2 - \epsilon^3 / 3) \right), \\ \Pr \left[ \frac{1}{k} \sum_{ i \in [k] } X_i^2 \le (1 - \epsilon) \cdot \sigma^2 \right] &\le \exp \left( - \frac{k}{4} \epsilon^2 \right). \end{aligned}$$

Upper Bound

To prove the upper bound, it suffices to establish the following theorem. The rest of the proof is the same as the one in the previous section.

Lemma. (Moment Generating Function). Let $X =\sum_{j \in [d]} \tilde{v} [j] \cdot z[j]$, where $\tilde{v} [j], j \in [d]$ are independent Rademacher random variables. Then for $0 \le \lambda < \frac{1}{2 \sigma^2}$, we have

$$\mathbb{E} \left[ e^{ \lambda X^2 } \right] \le \frac{1}{ \sqrt{ 1 - 2 \sigma^2 \lambda} }.$$

Proof. Let $Y =\sum_{j \in [d]} w [j] \cdot z[j]$, where $w [j], j \in [d]$ are independent standard gaussian random variables. Then $Y \sim N(0, \sigma^2)$, and

Our goal is to prove that $\mathbb{E} \left[ e^{ \lambda X^2 } \right] \le \mathbb{E} \left[ e^{ \lambda Y^2 } \right]$.

Since $X^{2m} \ge 0, \lambda \ge 0$, via monotone convergence theorem,

Following similar vein, we have

It suffices to prove that $\mathbb{E} \left[ X^{2m} \right] \le \mathbb{E} \left[ Y^{2m} \right]$ for each $m \in \mathbb{N}$.

Note,

We compare these expansions:

• If $m_j$ is odd, then $\mathbb{E} \left[ \Big( \tilde{v} [j] \Big)^{m_j} \right] = \mathbb{E} \left[ \Big( w [j] \Big)^{m_j} \right] = 0$.

• If $m_j$ is even, then $\Big( z[j] \Big)^{m_j} \ge 0$, and $1 = \mathbb{E} \left[ \Big( \tilde{v} [j] \Big)^{m_j} \right] \le \mathbb{E} \left[ \Big( w [j] \Big)^{m_j} \right] = (m_j - 1)!!$.

This proves that $\mathbb{E} \left[ X^{2m} \right] \le \mathbb{E} \left[ Y^{2m} \right]$.

$\square$

Lower Bound

We need the following facts.

Fact. For $t \ge 0$,

$$e^{-t} \le 1 - t + \frac{t^2}{2}.$$

Further, in the previous section, we prove that

Fact. Let $X \doteq \sum_{j \in [d]} \tilde{v} [j] \cdot z[j]$, where $\tilde{v} [j], j \in [d]$ are independent Rademacher random variables, and $Y \doteq \sum_{j \in [d]} w [j] \cdot z[j]$, where $w [j], j \in [d]$ are independent standard gaussian random variables. Then

$$\mathbb{E}[X^4] \le \mathbb{E} [Y^4].$$

Noting that $Y \sim N(0, \sigma^2)$, we can show $\mathbb{E}[Y^4] = \sigma^2 (4 - 1)!! = 3 \sigma^2$.

Proof. For each $\lambda > 0$,

Choosing $\lambda = \frac{\epsilon}{2 \sigma^2}$, we have

$\square$

Remark. For the proof of the lower bound, we only require the $\tilde{v} [j], j \in [d]$ to be 4-wise independent.

Reference

[1] J. Nelson, “Sketching and Streaming High-Dimensional Vectors,” p. 145.

[2]. D. Achlioptas, “Database-friendly random projections,” in PODS ’01.