Johnson Lindenstrauss Lemma

The Johnson-Lindenstrauss (JL) Lemma is a important result in mathematics that provides a way to reduce the dimensionality of data points while preserving the pairwise distances between them, up to a certain distortion. In this blog post, we introduce the JL Lemma and present a proof of the theorem.

The proof is based on the work of Dasgupta et al.’s paper An elementary proof of a theorem of Johnson and Lindenstrauss.. For a more detailed explanation, please refer to the original paper.

JL Lemma

For any set $\mathcal{O}$ of $n$ points in ${\mathbb{R}}^d$, there exists a map $f:{\mathbb{R}}^d\to {\mathbb{R}}^k$, such that for all ${\mathit{o}}_{\mathit{i}},{\mathit{o}}_{\mathit{j}}\in \mathcal{P}$:

$$(1-ϵ)\Vert {\mathit{o}}_{\mathit{i}}-{\mathit{o}}_{\mathit{j}}{\Vert }_2^2\le \Vert \mathit{f}\mathbf{(}{\mathit{o}}_{\mathit{i}}\mathbf{)}\mathbf{-}\mathit{f}\mathbf{(}{\mathit{o}}_{\mathit{j}}\mathbf{)}{\Vert }_2^2\le (1+ϵ)\Vert {\mathit{o}}_{\mathit{i}}-{\mathit{o}}_{\mathit{j}}{\Vert }_2^2$$

where $0<ϵ<1$ and $k$ is a positive integer satisfying:

$$k>\frac{24}{3{ϵ}^2-2{ϵ}^3}\log n$$

Let $A$ be a random matrix of size $k\times d$, where each entry is independently drawn from the standard normal distribution $\mathcal{N}(0,1)$. Using this random matrix, we can construct a mapping that satisfies the JL Lemma. For any point $\mathit{p}\in {\mathbb{R}}^d$, the mapping is defined as:

$$\mathit{f}\mathbf{(}\mathit{p}\mathbf{)}=\frac{A}{\sqrt{k}}\cdot \mathit{p}$$

Proof of JL Lemma

To prove the JL Lemma, we first establish some auxiliary lemmas and inequalities. For convenience, we will omit the subscript $2$ in the norm, so $\Vert \cdot {\Vert }^2$ refers to the $2$-norm by default.

Lemma 1

For any point $\mathit{p}\in {\mathbb{R}}^d$, let $\mathit{Y}=\frac{A}{\sqrt{k}}\cdot \mathit{p}$. Then, we have:

$$\mathrm{E}[\Vert \mathit{Y}{\Vert }^2]=\Vert \mathit{p}{\Vert }^2$$

Proof of Lemma 1

From the definition of $Y_i$, we have:

$$Y_i=\frac{1}{\sqrt{k}}\sum _{j=1}^d{A}_{ij}{p}_j$$

Now, we compute $\text{E}[\Vert \mathit{Y}{\Vert }^2]$:

$$\begin{array}{rl}\text{E}[\Vert \mathit{Y}{\Vert }^2]& =\text{E}\left[\sum _{i=1}^k\frac{1}{k}{\left(\sum _{j=1}^d{A}_{ij}{p}_j\right)}^2\right]\\ & =\text{E}\left[\sum _{i=1}^k\frac{1}{k}\sum _{j=1}^d\sum _{t=1}^d{A}_{ij}{A}_{it}{p}_j{p}_t\right]\\ & =\sum _{i=1}^k\frac{1}{k}\sum _{j=1}^d\sum _{t=1}^d{p}_j{p}_t\text{E}\left[A_{ij}{A}_{it}\right]\end{array}$$

• if $i\ne t$, then: $$\text{E}\left[A_{ij}{A}_{it}\right]=\text{E}\left[A_{ij}\right]\text{E}\left[A_{it}\right]=0$$
• if $i=t$, then: $$\text{E}\left[A_{ij}{A}_{it}\right]=\text{E}\left[A_{ij}^2\right]=\text{Var}(A_{ij})+{\text{E}}^2\left[A_{ij}\right]=1$$

Thus, we get:

$$\text{E}[\Vert \mathit{Y}{\Vert }^2]=\sum _{i=1}^k\frac{1}{k}\sum _{j=1}^d{p}_j^2=\sum _{i=1}^k\frac{1}{k}\Vert \mathit{p}{\Vert }^2=\Vert \mathit{p}{\Vert }^2$$

Lemma 2

Let $X$ be a random variable distributed as $\mathcal{N}(0,1)$. For a constant $\lambda \le \frac{1}{2}$, we have: $$\text{E}\left[e^{\lambda X^2}\right]=\frac{1}{\sqrt{1-2\lambda }}$$

Proof of Lemma 2

The PDF of the standard normal distribution is:

$$f(x)=\frac{1}{\sqrt{2\pi }}{e}^{-\frac{x^2}{2}}$$

We now compute $\text{E}\left[e^{\lambda x^2}\right]$:

$$\text{E}\left[e^{\lambda x^2}\right]={\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}\frac{1}{\sqrt{2\pi }}{e}^{\lambda x^2}{e}^{-\frac{x^2}{2}}\mathrm{d}x=\frac{1}{\sqrt{2\pi }}{\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}{e}^{-(1-2\lambda )\frac{x^2}{2}}\mathrm{d}x$$

Next, let $y=x\sqrt{1-2\lambda }$, so that $\mathrm{d}y=\sqrt{1-2\lambda }\mathrm{d}x$. Substituting this into the integral, we get:

$$\text{E}\left[e^{\lambda x^2}\right]=\frac{1}{\sqrt{1-2\lambda }}\frac{1}{\sqrt{2\pi }}{\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}{e}^{-\frac{y^2}{2}}\mathrm{d}y$$

Using the well-known result for the standard normal distribution:

$$\frac{1}{\sqrt{2\pi }}{\int }_{-\mathrm{\infty }}^{+\mathrm{\infty }}{e}^{-\frac{y^2}{2}}\mathrm{d}y=1$$

Therefore:

$$\text{E}\left[e^{\lambda x^2}\right]=\frac{1}{\sqrt{1-2\lambda }}$$

Lemma 3

For any point $\mathit{p}\in {\mathbb{R}}^d$, let $\mathit{Y}=\frac{A}{\sqrt{k}}\cdot \mathit{p}$. The following inequalities hold:

$$\begin{array}{rl}Pr[\Vert \mathit{Y}{\Vert }^2\ge (1+ϵ)\Vert \mathit{p}{\Vert }^2]& \le \frac{1}{n^2}\\ Pr[\Vert \mathit{Y}{\Vert }^2\le (1-ϵ)\Vert \mathit{p}{\Vert }^2]& \le \frac{1}{n^2}\end{array}$$

Proof of Lemma 3

We begin by simplifying the inequalities. From the definition of $\mathit{Y}$, we have:

$$Y_i=\frac{1}{\sqrt{k}}\sum _{j=1}^d{A}_{ij}{p}_j$$

We now compute $\Vert \mathit{Y}{\Vert }^2$:

$$\Vert \mathit{Y}{\Vert }^2=\sum _{i=1}^k{\left(\frac{1}{\sqrt{k}}\sum _{j=1}^d{A}_{ij}{p}_j\right)}^2=\sum _{i=1}^k\frac{1}{k}{\left(\sum _{j=1}^d{A}_{ij}{p}_j\right)}^2$$

Since the standard normal distribution is a $2$-stable distribution, using the will-known property, we have:

$$\Vert \mathit{Y}{\Vert }^2=\sum _{i=1}^k\frac{1}{k}\Vert p{\Vert }^2{X}_i^2=\frac{\Vert p{\Vert }^2}{k}\sum _{i=1}^k{X}_i^2$$

where $X_i$ is a random variable distributed as the standard normal distribution. Substituting this back, the inequalities we need to prove reduce to:

$$\begin{array}{rl}Pr[\sum _{i=1}^k{X}_i^2\ge k(1+ϵ)]& \le \frac{1}{n^2}\\ Pr[\sum _{i=1}^k{X}_i^2\le k(1-ϵ)]& \le \frac{1}{n^2}\end{array}$$

For the first inequality, let $\lambda >0$, then:

$$Pr[\sum _{i=1}^k{X}_i^2\ge k(1+ϵ)]=Pr[e^{\lambda \sum _{i=1}^k{X}_i^2}\ge e^{\lambda k(1+ϵ)}]$$

Using the Markov’s inequality, we have:

$$Pr[e^{\lambda \sum _{i=1}^k{X}_i^2}\ge e^{\lambda k(1+ϵ)}]\le \frac{\text{E}\left[e^{\lambda \sum _{i=1}^k{X}_i^2}\right]}{e^{\lambda k(1+ϵ)}}=\frac{{\text{E}}^k\left[e^{\lambda X_1^2}\right]}{e^{\lambda k(1+ϵ)}}$$

Let $\lambda =\frac{ϵ}{2(1+ϵ)}\le \frac{1}{2}$. By Lemma 2, we have:

$$\frac{{\text{E}}^k\left[e^{\lambda X_1^2}\right]}{e^{\lambda k(1+ϵ)}}={\left(\frac{1}{\sqrt{1-2\lambda }}\right)}^k{e}^{-\lambda k(1+ϵ)}={[(1+ϵ)e^{-ϵ}]}^{\frac{k}{2}}$$

Using the Taylor expansion for $\ln (1+ϵ)$:

$$\ln (1+ϵ)=ϵ-\frac{{ϵ}^2}{2}+\frac{{ϵ}^3}{3}-\frac{{ϵ}^4}{4}+\cdots$$

We have:

$$1+ϵ\le e^{ϵ-\frac{{ϵ}^2}{2}+\frac{{ϵ}^3}{3}}$$

Thus:

$${[(1+ϵ)e^{-ϵ}]}^{\frac{k}{2}}\le {\left(e^{ϵ-\frac{{ϵ}^2}{2}+\frac{{ϵ}^3}{3}}{e}^{-ϵ}\right)}^{\frac{k}{2}}=e^{-\frac{k(3{ϵ}^2-2{ϵ}^3)}{12}}$$

If $k$ satisfies:

$$k>\frac{24}{3{ϵ}^2-2{ϵ}^3}\log n$$

then:

$$e^{-\frac{k(3{ϵ}^2-2{ϵ}^3)}{12}}\le e^{-2\log n}=\frac{1}{n^2}$$

Therefore:

$$Pr[\sum _{i=1}^k{X}_i^2\ge k(1+ϵ)]\le \frac{1}{n^2}$$

Similarly, for the second inequality, let $\lambda >0$, then:

$$\begin{array}{rl}Pr[\sum _{i=1}^k{X}_i^2\le k(1-ϵ)]& =Pr[e^{-\lambda \sum _{i=1}^k{X}_i^2}\ge e^{-\lambda k(1-ϵ)}]\\ & \le \frac{\text{E}\left[e^{-\lambda \sum _{i=1}^k{X}_i^2}\right]}{e^{-\lambda k(1-ϵ)}}\\ & =\frac{{\text{E}}^k\left[e^{-\lambda X_1^2}\right]}{e^{-\lambda k(1-ϵ)}}\end{array}$$

Let $\lambda =\frac{ϵ}{2(1-ϵ)}$, so that $-\lambda =\frac{ϵ}{2(ϵ-1)}<0<\frac{1}{2}$. We have:

$$\frac{{\text{E}}^k\left[e^{-\lambda X_1^2}\right]}{e^{-\lambda k(1-ϵ)}}={\left(\frac{1}{\sqrt{1+2\lambda }}\right)}^k{e}^{\lambda k(1-ϵ)}={[(1-ϵ)e^{ϵ}]}^{\frac{k}{2}}$$

Similarly, using the Taylor expansion for $\ln (1-ϵ)$:

$$\ln (1-ϵ)=-ϵ-\frac{{ϵ}^2}{2}-\frac{{ϵ}^3}{3}\cdots$$

we have:

$$1-ϵ\le e^{-ϵ-\frac{{ϵ}^2}{2}}$$

Thus:

$${[(1-ϵ)e^{ϵ}]}^{\frac{k}{2}}\le e^{-\frac{k{ϵ}^2}{4}}<e^{-\frac{6{ϵ}^2}{3{ϵ}^2-2{ϵ}^3}\log n}<e^{-2\log n}=\frac{1}{n^2}$$

Therefore:

$$Pr[\sum _{i=1}^k{X}_i^2\le k(1-ϵ)]\le \frac{1}{n^2}$$

Proof of the JL Lemma

Given any point $\mathit{p}\in {\mathbb{R}}^d$, we will use Lemma 3 and Boole’s inequality to show that the JL Lemma holds.

From Lemma 3, for any point $\mathit{p}\in {\mathbb{R}}^d$, the following holds:

$$Pr[\Vert \mathit{f}\mathbf{(}\mathit{p}\mathbf{)}{\Vert }^2\notin [(1-ϵ)\Vert \mathit{p}{\Vert }^2,(1+ϵ)\Vert \mathit{p}{\Vert }^2]]\le \frac{2}{n^2}$$

Since this probability holds for any point $\mathit{p}\in {\mathbb{R}}^d$, it also holds for any pair of points $\mathit{u}={\mathit{o}}_{\mathit{i}}-{\mathit{o}}_{\mathit{j}}$, where ${\mathit{o}}_{\mathit{i}},{\mathit{o}}_{\mathit{j}}\in \mathcal{O}$.

Furthermore, using the linearity of the projection, we have:

$$\mathit{f}\mathbf{(}{\mathit{o}}_{\mathbf{1}}\mathbf{-}{\mathit{o}}_{\mathbf{2}}\mathbf{)}=\mathit{f}\mathbf{(}{\mathit{o}}_{\mathbf{1}}\mathbf{)}-\mathit{f}\mathbf{(}{\mathit{o}}_{\mathbf{2}}\mathbf{)}$$

Therefore, applying Lemma 3 to the difference between two points ${\mathit{o}}_{\mathit{i}}$ and ${\mathit{o}}_{\mathit{j}}$, we obtain:

$$Pr[\Vert \mathit{f}\mathbf{(}{\mathit{o}}_{\mathit{i}}\mathbf{)}-\mathit{f}\mathbf{(}{\mathit{o}}_{\mathit{j}}\mathbf{)}{\Vert }^2\notin [(1-ϵ)\Vert {\mathit{o}}_{\mathit{i}}-{\mathit{o}}_{\mathit{j}}{\Vert }^2,(1+ϵ)\Vert {\mathit{o}}_{\mathit{i}}-{\mathit{o}}_{\mathit{j}}{\Vert }^2]]\le \frac{2}{n^2}$$

The number of pairs of points ${\mathit{o}}_{\mathit{i}},{\mathit{o}}_{\mathit{j}}\in \mathcal{O}$ is $(\genfrac{}{}{0ex}{}{n}{2})$. Thus, using Boole’s inequality, the probability that at least one pair of points falls outside the desired error bound is at most:

$$\frac{n(n-1)}{2}\frac{2}{n^2}=1-\frac{1}{n}$$

Thus, with probability at least $\frac{1}{n}>0$, all pairs of points in $\mathcal{O}$ will fall within the desired error bounds, completing the proof of the JL Lemma.