Johnson–Lindenstrauss lemma

Template:Short description In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved. In the classical proof of the lemma, the embedding is a random orthogonal projection.

The lemma has applications in compressed sensing, manifold learning, dimensionality reduction, graph embedding, and natural language processing. Much of the data stored and manipulated on computers, including text and images, can be represented as points in a high-dimensional space (see vector space model for the case of text). However, the essential algorithms for working with such data tend to become bogged down very quickly as dimension increases. It is therefore desirable to reduce the dimensionality of the data in a way that preserves its relevant structure.

Statement

Given $0<\epsilon <1$, a set $X$ of $N$ points in ${ℝ}^n$ , and an integer $k>8(\ln N)/{\epsilon }^2$, there is a linear map $f:{ℝ}^n\to {ℝ}^k$ such that

$(1-\epsilon )\Vert u-v{\Vert }^2\le \Vert f(u)-f(v){\Vert }^2\le (1+\epsilon )\Vert u-v{\Vert }^2$

for all $u,v\in X$.

The formula can be rearranged:$$(1+\epsilon {)}^{-1}\Vert f(u)-f(v){\Vert }^2\le \Vert u-v{\Vert }^2\le (1-\epsilon {)}^{-1}\Vert f(u)-f(v){\Vert }^2$$

Alternatively, for any $\epsilon \in (0,1)$ and any integer $k\ge 15(\ln N)/{\epsilon }^2$ there exists a linear function $f:{ℝ}^n\to {ℝ}^k$ such that the restriction $f{|}_X$ is $(1+\epsilon )$-bi-Lipschitz.

Also, the lemma is tight up to a constant factor, i.e. there exists a set of points of size N that needs dimension

$\mathrm{\Omega }\left(\frac{\log (N)}{{\epsilon }^2}\right)$

in order to preserve the distances between all pairs of points within a factor of $(1\pm \epsilon )$.

The classical proof of the lemma takes $f$ to be a scalar multiple of an orthogonal projection $P$ onto a random subspace of dimension $k$ in ${ℝ}^n$. An orthogonal projection collapses some dimensions of the space it is applied to, which reduces the length of all vectors, as well as distance between vectors in the space. Under the conditions of the lemma, concentration of measure ensures there is a nonzero chance that a random orthogonal projection reduces pairwise distances between all points in $X$ by roughly a constant factor $c$. Since the chance is nonzero, such projections must exist, so we can choose one $P$ and set $f(v)=Pv/c$.

To obtain the projection algorithmically, it suffices with high probability to repeatedly sample orthogonal projection matrices at random. If you keep rolling the dice, you will eventually obtain one in polynomial random time.

Proof

The proof below is based on the course notes of Afonso Bandeira that can be found at the following link.

Construct a random matrix $A\sim 𝒩(0,1{)}^{k\times n}$, obtained by sampling each entry from the standard normal distribution. Define $P:=\frac{A}{\sqrt{k}}$, then for any nonzero vector $x\in {ℝ}^n$, let the projected vector be $\hat{x}:=Ax$. Standard geometric arguments show that $r:=\frac{\Vert \hat{x}{\Vert }^2}{\Vert x{\Vert }^2}$ is chi-square distributed, that is, $r\sim {\chi }^2(k)$. Thus, it satisfies a concentration inequality for the chi-squared distribution:$$Pr(r\in (1\pm ϵ)k)\ge 1-2e^{-\frac{k}{2}(\frac{1}{2}{ϵ}^2-\frac{1}{3}{ϵ}^3)}$$

By the union bound, the probability that this relation is true for all of $x_1,\dots ,x_N$ is greater than $1-2N{e}^{-\frac{k}{2}(\frac{1}{2}{ϵ}^2-\frac{1}{3}{ϵ}^3)}$.

When $k\ge \frac{4\ln 2N}{{ϵ}^2(1-2ϵ/3)}$, the probability is nonzero.

More generally, when $k\ge \frac{4(d+1)\ln 2N}{{ϵ}^2(1-\frac{2ϵ}{3})}$, the probability is greater than, or equal to $1-\frac{1}{(2N{)}^d}$, allowing arbitrarily high probability of success per sample, and a fortiori polynomial random time.

Alternate statement

A related lemma is the distributional JL lemma. This lemma states that for any $0<\epsilon ,\delta <1/2$ and positive integer $d$, there exists a distribution over ${ℝ}^{k\times d}$ from which the matrix $A$ is drawn such that for $k=O({\epsilon }^{-2}\log (1/\delta ))$ and for any unit-length vector $x\in {ℝ}^d$, the claim below holds.

$P(|\Vert Ax{\Vert }_2^2-1|>\epsilon )<\delta$

One can obtain the JL lemma from the distributional version by setting $x=(u-v)/\Vert u-v{\Vert }_2$ and $\delta <1/n^2$ for some pair u,v both in X. Then the JL lemma follows by a union bound over all such pairs.

Sparse JL transform

Database-friendly JL transform

(Achlioptas, 2003) proposed "database-friendly" JL transform, using matrices with only entries from (-1, 0, +1).

Fix some unit vector $v\in {ℝ}^n$. Define $Q_i:={\sum }_j{R}_{ij}{v}_j$. We have $\Vert f(v){\Vert }_2^2=\frac{1}{k}{\sum }_i{Q}_i^2$.

Now, since the $Q_1,\dots ,Q_k$ are IID, we want to apply a Chernoff concentration bound for $\frac{1}{k}{\sum }_i{Q}_i^2$ around 1. This requires upper-bounding the cumulant generating function (CGF).

Now that $Q_i$ is stochastically dominated by the standard gaussian, and $E[Q_i^2]=1$, it remains to perform a Chernoff bound for $Q_i^2$, which requires bounding the cumulant generating function on both ends.

Sparser JL transform on well-spread vectors

(Matoušek, 2008) proposed a variant of the above JL transform that is even more sparsified, though it only works on "well-spread" vectors.

Template:Math theoremThe above cases are generalized to the case for matrices with independent, mean-zero, unit variance, subgaussian entries in (Dirksen, 2016).

Speeding up the JL transform

Given A, computing the matrix vector product takes $O(kd)$ time. There has been some work in deriving distributions for which the matrix vector product can be computed in less than $O(kd)$ time.

There are two major lines of work. The first, Fast Johnson Lindenstrauss Transform (FJLT), was introduced by Ailon and Chazelle in 2006. This method allows the computation of the matrix vector product in just $d\log d+k^{2+\gamma }$ for any constant $\gamma >0$.

Another approach is to build a distribution supported over matrices that are sparse. This method allows keeping only an $\epsilon$ fraction of the entries in the matrix, which means the computation can be done in just $kd\epsilon$ time. Furthermore, if the vector has only $b$ non-zero entries, the Sparse JL takes time $kb\epsilon$, which may be much less than the $d\log d$ time used by Fast JL.

Tensorized random projections

It is possible to combine two JL matrices by taking the so-called face-splitting product, which is defined as the tensor products of the rows (was proposed by V. Slyusar in 1996 for radar and digital antenna array applications). More directly, let $C\in {ℝ}^{3\times 3}$ and $D\in {ℝ}^{3\times 3}$ be two matrices. Then the face-splitting product $C\bullet D$ is

$C\bullet D=\left[\begin{array}{c}{C}_1\otimes D_1\\ C_2\otimes D_2\\ C_3\otimes D_3\end{array}\right].$

This idea of tensorization was used by Kasiviswanathan et al. for differential privacy.

JL matrices defined like this use fewer random bits, and can be applied quickly to vectors that have tensor structure, due to the following identity:

$(𝐂\bullet 𝐃)(x\otimes y)=𝐂x\circ 𝐃y=\left[\begin{array}{c}(𝐂x{)}_1(𝐃y{)}_1\\ (𝐂x{)}_2(𝐃y{)}_2\\ ⋮\end{array}\right]$,

where $\circ$ is the element-wise (Hadamard) product. Such computations have been used to efficiently compute polynomial kernels and many other Template:Clarify.

In 2020 it was shown that if the matrices $C_1,C_2,\dots ,C_c$ are independent $\pm 1$ or Gaussian matrices, the combined matrix $C_1\bullet \dots \bullet C_c$ satisfies the distributional JL lemma if the number of rows is at least

$O({ϵ}^{-2}\log 1/\delta +{ϵ}^{-1}(\frac{1}{c}\log 1/\delta {)}^c)$.

For large $ϵ$ this is as good as the completely random Johnson-Lindenstrauss, but a matching lower bound in the same paper shows that this exponential dependency on $(\log 1/\delta {)}^c$ is necessary. Alternative JL constructions are suggested to circumvent this.

See also

• Random projection
• Restricted isometry property
• Word embeddings

Further reading

• Template:Citation. Journal version of a paper previously appearing at PODC 2001.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation
• Template:Citation.
• Template:Citation