Johnson–Lindenstrauss lemma

Given ${\displaystyle 0<\varepsilon <1}$, a set ${\displaystyle X}$ of ${\displaystyle m\in \mathbb {Z} _{\geq 1}}$ points in ${\displaystyle \mathbb {R} ^{N}}$ (${\displaystyle N\in \mathbb {Z} _{\geq 0}}$), and an integer ${\displaystyle n>8(\ln m)/\varepsilon ^{2}}$, there is a linear map ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}}$ such that

${\displaystyle (1-\varepsilon )\|u-v\|^{2}\leq \|f(u)-f(v)\|^{2}\leq (1+\varepsilon )\|u-v\|^{2}}$

for all ${\displaystyle u,v\in X}$.

The formula can be rearranged:

$${\displaystyle (1+\varepsilon )^{-1}\|f(u)-f(v)\|^{2}\leq \|u-v\|^{2}\leq (1-\varepsilon )^{-1}\|f(u)-f(v)\|^{2}}$$

Alternatively, for any ${\displaystyle \epsilon \in (0,1)}$ and any integer ${\displaystyle n\geq 15(\ln m)/\varepsilon ^{2}}$[Note 1] there exists a linear function ${\displaystyle f:\mathbb {R} ^{N}\rightarrow \mathbb {R} ^{n}}$ such that the restriction ${\displaystyle f|_{X}}$ is ${\displaystyle (1+\varepsilon )}$-bi-Lipschitz.[Note 2]

One proof of the lemma takes ƒ to be a suitable multiple of the orthogonal projection onto a random subspace of dimension ${\displaystyle n}$ in ${\displaystyle \mathbb {R} ^{N}}$, and exploits the phenomenon of concentration of measure.

An orthogonal projection will, in general, reduce the average distance between points, but the lemma can be viewed as dealing with relative distances, which do not change under scaling. In a nutshell, you roll the dice and obtain a random projection, which will reduce the average distance, and then you scale up the distances so that the average distance returns to its previous value. If you keep rolling the dice, you will, in polynomial random time, find a projection for which the (scaled) distances satisfy the lemma.

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

${\displaystyle P(|\Vert Ax\Vert _{2}^{2}-1|>\varepsilon )<\delta }$

One can obtain the JL lemma from the distributional version by setting ${\displaystyle x=(u-v)/\|u-v\|_{2}}$ and ${\displaystyle \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.

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

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

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

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[7] in 1996[8][9][10][11][12] for radar and digital antenna array applications). More directly, let ${\displaystyle {C}\in \mathbb {R} ^{3\times 3}}$ and ${\displaystyle {D}\in \mathbb {R} ^{3\times 3}}$ be two matrices. Then the face-splitting product ${\displaystyle {C}\bullet {D}}$ is[8][9][10][11][12]

${\displaystyle {C}\bullet {D}=\left[{\begin{array}{c }{C}_{1}\otimes {D}_{1}\\\hline {C}_{2}\otimes {D}_{2}\\\hline {C}_{3}\otimes {D}_{3}\\\end{array}}\right].}$

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

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:[10]

${\displaystyle (\mathbf {C} \bullet \mathbf {D} )(x\otimes y)=\mathbf {C} x\circ \mathbf {D} y=\left[{\begin{array}{c }(\mathbf {C} x)_{1}(\mathbf {D} y)_{1}\\(\mathbf {C} x)_{2}(\mathbf {D} y)_{2}\\\vdots \end{array}}\right]}$,

where ${\displaystyle \circ }$ is the element-wise (Hadamard) product. Such computations have been used to efficiently compute polynomial kernels and many other linear-algebra algorithms.[14]

In 2020[15] it was shown that if the matrices ${\displaystyle C_{1},C_{2},\dots ,C_{c}}$ are independent ${\displaystyle \pm 1}$ or Gaussian matrices, the combined matrix ${\displaystyle C_{1}\bullet \dots \bullet C_{c}}$ satisfies the distributional JL lemma if the number of rows is at least

${\displaystyle O(\epsilon ^{-2}\log 1/\delta +\epsilon ^{-1}({\tfrac {1}{c}}\log 1/\delta )^{c})}$.

For large ${\displaystyle \epsilon }$ 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 ${\displaystyle (\log 1/\delta )^{c}}$ is necessary. Alternative JL constructions are suggested to circumvent this.

• Random projection
• Restricted isometry property

• Achlioptas, Dimitris (2003), "Database-friendly random projections: Johnson–Lindenstrauss with binary coins", Journal of Computer and System Sciences, 66 (4): 671–687, doi:10.1016/S0022-0000(03)00025-4, MR 2005771. Journal version of a paper previously appearing at PODC 2001.
• Baraniuk, Richard; Davenport, Mark; DeVore, Ronald; Wakin, Michael (2008), "A simple proof of the restricted isometry property for random matrices", Constructive Approximation, 28 (3): 253–263, doi:10.1007/s00365-007-9003-x, hdl:1911/21683, MR 2453366, S2CID 15911073.
• Dasgupta, Sanjoy; Gupta, Anupam (2003), "An elementary proof of a theorem of Johnson and Lindenstrauss" (PDF), Random Structures & Algorithms, 22 (1): 60–65, doi:10.1002/rsa.10073, MR 1943859, S2CID 10327785.
• Landweber, Peter; Lazar, Emanuel A.; Patel, Neel (2016), "On fiber diameters of continuous maps", American Mathematical Monthly, 123 (4): 392–397, arXiv:1503.07597, doi:10.4169/amer.math.monthly.123.4.392, S2CID 51751732
• Slyusar, V. I. (1997-05-20), "Analytical model of the digital antenna array on a basis of face-splitting matrix products." (PDF), Proc. ICATT-97, Kyiv: 108–109
• Slyusar, V. I. (March 13, 1998), "A Family of Face Products of Matrices and its Properties" (PDF), Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999., 35 (3): 379–384, doi:10.1007/BF02733426, S2CID 119661450.
• The Modern Algorithmic Toolbox Lecture #4: Dimensionality Reduction (PDF), 2023