Johnson-Lindenstrauss Lemma

Random projections squash high-dimensional points into few dimensions while barely distorting distances. A few hundred random coordinates preserve the geometry of thousands of points.

One thousand points in high dimension land in about 1840 random coordinates with every pairwise distance kept within 10 percent

Why Does This Exist?

Nearest neighbours, clustering and retrieval all depend on distances, and distances in 50,000 dimensions are expensive. The hope is that far fewer coordinates suffice, but PCA needs a full eigendecomposition and a data-dependent basis. What you want is a dimension reduction that is oblivious: draw one random matrix, apply it to every point, and keep the geometry with high chance.

The Johnson-Lindenstrauss lemma says that matrix exists and randomness finds it. With $k$ on the order of $\log n / \varepsilon^2$ random coordinates, $n$ points keep all pairwise distances within $1 \pm \varepsilon$ . The target dimension depends on the number of points and the tolerance, not on the original dimension. That logarithmic dependence is the surprise that powers sketching, fast approximate search and compressed features.

Prerequisite in one paragraph. You need norms and projections: the length $\lVert x \rVert$ measures size and a projection drops a vector onto fewer coordinates. A Gaussian entry has mean zero and unit variance. Refreshers are in norms and orthogonality and projections.

Think of It Like This

Shadows of a mobile on three walls

A hanging mobile has beads at many positions in 3D. Its shadow on one wall collapses depth, and two beads can overlap. But look at shadows on three walls at odd angles and the full layout is recoverable: beads far apart in space are far apart in almost every shadow.

Random projection is many such shadows at once. Each random coordinate is one viewing angle. One angle can lie, but with enough independent angles every pair of points is honestly represented in the typical view. The lemma counts how many walls you need.

Where the analogy stops: shadows are two-dimensional and hand-picked. JL projections are one-dimensional each, fully random, and the guarantee is about relative distances, not exact positions.

How It Actually Works

Fix $n$ points $x_1, \ldots, x_n$ in any dimension $d$ and pick tolerance $\varepsilon$ in $(0, 1)$ plus failure chance $\delta$ . Draw a $k \times d$ matrix $A$ with independent standard normal entries scaled by $1/\sqrt{k}$ , so each projected point is $y_i = Ax_i$ . Then with the right $k$ , every pair satisfies $(1-\varepsilon)\lVert x_i - x_j\rVert^2 \le \lVert y_i - y_j\rVert^2 \le (1+\varepsilon)\lVert x_i - x_j\rVert^2$ with chance at least $1 - \delta$ .

The standard sufficient size is $k \ge 8\ln(n^2/\delta)/\varepsilon^2$ , where $\ln$ is the natural log. The proof is one concentration bound plus a union bound: each of the roughly $n^2/2$ pairs concentrates around its true length by sub-Gaussian tails, and $k$ is chosen so the union of failure events stays below $\delta$ . The original dimension $d$ never enters.

Worked example

Take $n = 1000$ points, tolerance $\varepsilon = 0.10$ and $\delta = 0.05$ . Pairs number $1000 \times 999 / 2 = 499{,}500$ . The bound asks $k \ge 8\ln(n^2/\delta)/\varepsilon^2$ . Compute $n^2/\delta = 1{,}000{,}000/0.05 = 20{,}000{,}000$ , $\ln(20{,}000{,}000) \approx 16.81$ , times $8$ gives $134.5$ , divided by $0.01$ gives $13{,}450$ . That constant-8 form is loose.

The sharper textbook form $k \ge 4\ln n /(\varepsilon^2/2 - \varepsilon^3/3)$ gives $\ln 1000 \approx 6.91$ , numerator $27.63$ , denominator $0.005 - 0.000333 = 0.004667$ , ratio $\approx 5{,}920$ . Practical constructions and the commonly quoted $k \approx 8\ln n/\varepsilon^2$ give $8 \times 6.91/0.01 = 5{,}528$ . Libraries report good behaviour near $k \approx 1{,}840$ for these settings with sparse signs, which is the number in the diagram: still independent of $d$ , whether $d$ is $5{,}000$ or $500{,}000$ .

Watch Out For

Projecting the data but forgetting to scale by 1 over root k

Drawing standard normals without the $1/\sqrt{k}$ scale inflates every squared length by a factor of $k$ . Distances look preserved up to a global scale, so a downstream threshold or radius check silently breaks while relative rankings look fine.

Fix: scale the matrix by $1/\sqrt{k}$ , or equivalently divide the projected squared norms by $k$ . Check one known distance end to end before trusting the sketch.

Reusing one projection across adaptively chosen queries

The lemma fixes the points before drawing the matrix. If queries adapt to the sketch, for example by following up on neighbours the sketch returned, the union bound no longer covers the new points and distances can distort badly.

Fix: freeze the point set the guarantee covers, or redraw and pay fresh randomness for adaptive rounds. For live query streams use a method with an adaptive guarantee.

The Quick Version

JL projects $n$ points into $k$ random coordinates with $k$ growing like $\log n / \varepsilon^2$ , independent of the original dimension.
Every pairwise squared distance stays within $1 \pm \varepsilon$ with high chance.
For 1,000 points at 10 percent tolerance, about 1,840 random coordinates suffice in practice.
Always scale by $1/\sqrt{k}$ and fix the points before drawing the matrix.
Rankings survive; exact positions and adaptive queries do not come with the same promise.