The JL Lemma

This post walks through an unconvential proof that the Johnson-Lindenstrauss Lemma preserves angles between vectors. I came up with this proof for a HW problem in EECS 498, and I’m not actually sure if it’s completely correct, but I think the idea is pretty cool.

Suppose we have independently chosen vectors $x_1,\dots ,x_n\in {\mathbb{R}}^d$. We want to reduce these vectors to dimension ${\mathbb{R}}^{d^{\prime }}$ while retaining important information. Specifically, we want to preserve the distance between arbitrary vectors. Let’s select a matrix $A\in {\mathbb{R}}^{d^{\prime }\times d}$ where each $A_{ij}$ is sampled independently from $N(0,\frac{1}{d^{\prime }})$. Then, $A{x}_i$ is our vector in reduced dimension $d^{\prime }$. Multiplication by $A$ is a simple but surprisingly effective dimensionality reduction technique. We want to show that $⟨A{x}_i,A{x}_j⟩\stackrel{ϵ}{\approx }⟨x_i,x_j⟩$ with probability at least $1-\frac{1}{n}$. Note that we are just dealing with the standard inner product here. In order to reach this result, we want to first show that $\mathbb{E}[⟨A{x}_i,A{x}_j⟩]=⟨x_i,x_j⟩$. Then, there is a simple variation of the Hoeffding bound that we can apply to bound our probability that $⟨A{x}_i,A{x}_j⟩$ is within $ϵ$ of $⟨x_i,x_j⟩$. The latter step is mostly plug and chug and not really interesting, so I’m just going to show the first part and leave the second as an exercise for the reader (always wanted to say that).

First, $\mathbb{E}[⟨A{x}_i,A{x}_j⟩]=\mathbb{E}[(A{x}_j{)}^{T}A{x}_i]=\mathbb{E}[x_j^T{A}^{T}A{x}_i]=x_j^T\mathbb{E}[A^{T}A]x_i$. Now, I will show that $\mathbb{E}[A^{T}A]={\mathbb{I}}_d$

$$A^{T}A=\left[\begin{array}{ccc}{a}_{11}& \dots & a_{d^{\prime }1}\\ ⋮& \ddots & \\ a_{1d}& \dots & a_{d^{\prime }d}\end{array}\right]\left[\begin{array}{ccc}{a}_{11}& \dots & a_{1d}\\ ⋮& \ddots & \\ a_{d^{\prime }1}& \dots & a_{d^{\prime }d}\end{array}\right]$$

Consider the diagonal elements in $A^{T}A$. For any $i\in [d]$, $(A^{T}A{)}_{ii}=\sum _{j=1}^{d^{\prime }}{a}_{ij}^2$. But recall that each $a_{ij}\sim N(0,\frac{1}{d^{\prime }})$, so $\mathbb{E}[a_{ij}^2]=\frac{1}{d^{\prime }}$. Then, in expectation, $\mathbb{E}[\sum _{j=1}^{d^{\prime }}{a}_{ij}^2]=\sum _{j=1}^{d^{\prime }}\mathbb{E}[a_{ij}^2]=1$. Now consider any of the non-diagonal elements in $A^{T}A$. For any distinct $i,j\in [d]$, $(A^{T}A{)}_{ij}=\sum _{k=1}^{d^{\prime }}{a}_{ik}\cdot a_{kj}$. The key thing to notice here is that every element in the sum is two distinct cells being multiplied. For fixed $k$, $\mathbb{E}[a_{ik}\cdot a_{kj}]=\mathbb{E}[a_{ik}]\cdot \mathbb{E}[a_{kj}]$ because each cell is sampled independently. And each entry $a_{ij}\sim N(0,\frac{1}{d^{\prime }})$ so $\mathbb{E}[a_{ik}]=\mathbb{E}[a_{kj}]=0$, so in expectation, each non-diagonal entry will end up being $0$. This shows $\mathbb{E}[A^{T}A]$ is precisely the identity matrix and thus $\mathbb{E}[⟨A{x}_i,A{x}_j⟩]=x_j^T{I}_d{x}_i=⟨x_i,x_j⟩$

From there, we do some boring concentration bound stuff to complete the proof. Though this proof probably skipped over some important nuances, I thought its structure was really elegant and overall it just felt super satisfying to come up with.