Random Projections and the Johnson–Lindenstrauss Lemma

Overview & motivation

The previous topic reduced an embedding cloud’s dimension by reading the cloud’s own covariance: principal component analysis finds the directions the data actually varies along and projects onto the top $k$ of them. It is variance-optimal, but it pays a price that is easy to overlook — it must see the data first, eigendecompose a $d \times d$ covariance, and recompute when the corpus changes. This topic asks a question that sounds too good to be true: can we shrink $d$ with a map that never looks at the data at all?

The answer is the Johnson–Lindenstrauss lemma, and it is yes. Draw a random matrix $A \in \mathbb{R}^{k \times d}$ — Gaussian entries will do — and the map $f(x) = \tfrac{1}{\sqrt{k}} A x$ preserves every pairwise distance in a set of $n$ points to within a factor of $1 \pm \varepsilon$, provided $k$ is on the order of $\varepsilon^{-2}\log n$. The headline is the dimension that does not appear: the target $k$ depends on $\log n$ and the tolerance $\varepsilon$, but not on the ambient dimension $d$. A million points embed into the same target dimension whether they started in $\mathbb{R}^{768}$ or $\mathbb{R}^{100000}$.

Before the algebra, drag the target-dimension slider and watch the distortion concentrate:

The first panel is the histogram of pairwise distortions: at small $k$ the projected distances scatter wildly, and as $k$ grows they pull into the $\pm\varepsilon$ band around $1$ — the visual signature of the chi-squared law tightening. The second separates the typical pair from the worst pair, which is the difference between an average and a guarantee. The third shows that the dense Gaussian matrix is a luxury: Rademacher and sparse variants concentrate just as tightly. The fourth marks the edge of the job: a random projection is a distance sketch, so it preserves distances rather than exact rankings — which is why it belongs at the front of an approximate-search pipeline, not in place of the retriever.

What we cover

1. The random map, and the unbiasedness that every Johnson–Lindenstrauss proof begins from.
2. The chi-squared law of the squared norm, and the concentration that makes it useful.
3. The lemma itself: a union bound over the difference vectors, and the dimension-independent target $k$.
4. Why the bound is worst-case, and how far the typical pair beats it.
5. Database-friendly projections: binary and sparse matrices with the same guarantee.
6. Optimality of the bound, and the division of labor with PCA: what a data-oblivious distance sketch is for.
7. A finance case study and the tested code.

The random map, and why it preserves norm in expectation

Fix a target dimension $k < d$ and draw $A \in \mathbb{R}^{k \times d}$ with independent standard-normal entries $A_{ij} \sim \mathcal{N}(0,1)$. The random projection of a vector $x \in \mathbb{R}^d$ is

The scaling $1/\sqrt{k}$ is the only piece of design in the whole construction, and it is there to make the map preserve length on average. Write $a_i^{\top}$ for the $i$-th row of $A$, so the $i$-th coordinate of $Ax$ is the inner product $a_i \cdot x$.

Two things are worth reading off this. The map is unbiased — on average it neither stretches nor shrinks — and its fluctuation, with variance $2/k$, shrinks as the target dimension grows. The standard deviation $\sqrt{2/k}$ is the single number the histogram panel is tracking: at $k = 64$ it is about $0.18$, at $k = 512$ about $0.06$. Unbiasedness alone is useless — a map can be right on average and wrong every time. What rescues the construction is that this fluctuation does not merely shrink, it concentrates exponentially.

Concentration: the chi-squared tail

The variance $2/k$ tells us the typical deviation, but the lemma needs a statement about rare deviations: how unlikely is it that a single vector’s squared norm strays from $1$ by more than $\varepsilon$? The answer is the chi-squared tail, and it decays exponentially in $k\varepsilon^2$.

This is the load-bearing estimate. The probability that a fixed vector’s length is mangled by more than $\varepsilon$ decays like $e^{-c k \varepsilon^2}$, so we can drive it as low as we like by spending dimensions: doubling $k$ squares the failure probability. The next step spends exactly enough of them to cover not one vector but every pairwise difference in a data set at once.

The Johnson–Lindenstrauss lemma

A distance is the norm of a difference: $\lVert x_a - x_b\rVert$. Because $f$ is linear, $f(x_a) - f(x_b) = f(x_a - x_b)$, so preserving the distance between two points is exactly preserving the norm of their difference vector. Theorem 2 controls one such vector; to control all of them we apply it to every difference and add up the failure probabilities — the union bound.

Look at what the target dimension depends on. The denominator is a function of $\varepsilon$ alone; the numerator is $\ln n$. The ambient dimension $d$ has vanished. This is the sense in which random projection beats the curse of dimensionality at its own game: the cost of preserving the geometry of $n$ points is set by how many points there are, not by how many coordinates they arrived with. The companion harness confirms the lemma directly — at the guaranteed $k$, a single Gaussian projection holds all $\binom{n}{2}$ pairs inside the band across every random seed it tries.

The bound is worst-case: typical versus worst

The lemma is a guarantee, and a guarantee must hold for the worst pair, not the average one — which is why its constant is pessimistic. Set $n = 500$ and $\varepsilon = 0.2$, the finance configuration: the formula demands

larger than many ambient dimensions one would actually project from. Yet project the same cloud to a practical $k = 128$ and the typical pair distorts by only about $9\%$. The gap is the difference between an average and a maximum: with $124{,}750$ pairs, the worst of them still distorts by about $51\%$ at $k = 128$, and pulling that worst pair inside $\pm\varepsilon$ is what the large guaranteed $k$ buys. The “Typical vs worst” panel makes this concrete — the $p_{01}$–$p_{99}$ band slips inside $\pm\varepsilon$ while the worst-pair envelope is still well outside it.

Two honest consequences follow. The constant $4$ is loose, and in practice one uses a far smaller $k$ than the lemma demands, accepting that a handful of pairs are badly distorted — random projection is a tool for approximate geometry. And the dimension independence is a statement about the worst case over arbitrary point sets; a structured, near-low-rank cloud of real embeddings is far easier than the worst case, which is exactly the slack the next sections exploit and measure.

Database-friendly projections

The dense Gaussian matrix is expensive: projecting one vector costs $kd$ multiplications, and storing $A$ costs $kd$ floats. Achlioptas (2003) showed that neither the Gaussian entries nor the density is necessary. Replace $A_{ij}$ with random signs, or with a matrix that is mostly zero, and the guarantee survives.

Unbiasedness is the easy half; what makes these valid Johnson–Lindenstrauss maps is that their squared norm concentrates at the same $\sqrt{2/k}$ rate as the Gaussian one. Both families are sub-Gaussian, and Achlioptas proves a tail of the same exponential form — we cite that result rather than re-prove it, and the harness verifies it numerically: at $k = 64$ the Gaussian, Rademacher, and sparse distortion spreads are $0.154$, $0.166$, and $0.162$, all hugging the predicted $\sqrt{2/64} \approx 0.177$. The “Projection families” panel shows the three side by side. The sparse map is the practical winner: it preserves distances for a third of the arithmetic, the property that makes random projection a cheap front end for large indexes.

There is an honest footnote, which the code surfaces: on a low-rank cloud, where the signal lives in a few coordinates, the very sparse map has a heavier-tailed per-matrix fluctuation than the Gaussian one — zeroing two-thirds of the matrix occasionally under-samples the signal directions. The concentration rate is unchanged, but the constant is a little worse, which is the kind of trade the sparsity buys.

Optimality, and the division of labor with PCA

Could a cleverer map do better than $k = \Theta(\varepsilon^{-2}\log n)$? For a data-oblivious map asked to preserve all pairwise distances, no.

We cite this rather than prove it; the construction takes a near-orthogonal point set on which no projection can do better. So within its remit — preserving all pairwise distances without ever looking at the data — Johnson–Lindenstrauss is not merely serviceable but optimal: no data-oblivious map reaches a smaller target dimension. That is the achievement to keep in view. What the bound does not claim is optimality on a particular, structured cloud, and that is where PCA divides the labor rather than competing. PCA is data-dependent: it reads the covariance and spends every kept dimension on a direction the cloud actually varies along, so on a structured corpus it captures, per dimension, geometry that a map asking nothing of the data does not. The two are built for different jobs — JL for a fixed, dimension-independent guarantee over any point set with no training; PCA for the most it can wring from this one.

That division of labor has one sharp edge worth stating plainly, because it decides where each tool belongs. Johnson–Lindenstrauss preserves distances — which is exactly the currency an approximate-nearest-neighbor index trades in — but preserving every distance to $\pm\varepsilon$ does not preserve the order of distances when neighbors sit closer together than $\varepsilon$. On a tightly clustered cloud the tenth and eleventh nearest neighbors are nearly equidistant, so a $\pm\varepsilon$ wobble can swap them, and exact recall@10 falls — about $23\%$ for the random projection at $k = 128$ against about $96\%$ for the data-dependent PCA of the same width (the “Recall after projection” panel). That is not the sketch underperforming; it is the sketch being a distance sketch rather than a retriever. Its role, by design, is the front end of an approximate-search pipeline — the dimensionality-reduction step before locality-sensitive hashing, the forthcoming topic — where a cheap, distance-preserving sketch is precisely what the next stage consumes, and the exact ordering is restored downstream by a rerank.

Finance case study

Honest caveats

Implementation

The companion module johnson_lindenstrauss.py owns every number this page and the laboratory cite. It builds the three projection families through a single generator stream — a deliberate choice, since drawing each random matrix from a freshly seeded generator over consecutive integers leaves their opening values weakly correlated and inflates the sampled variance with $d$, a real and easily-missed NumPy pitfall. Its eight assertions encode the claims in order: unbiasedness for all three families; the chi-squared mean, variance, and Laurent–Massart tail; the lemma holding at the guaranteed $k$; dimension independence (a fixed vector’s distortion spread is $\sqrt{2/k}$ for every $d$, while the worst pairwise distortion grows with $n$); the three families concentrating alike; the recall gap between oblivious and data-dependent projection; a cross-check of the target dimension and distortion against scikit-learn’s random_projection; and the finance headline. The narrative notebook walks the same path section by section. Both run in about seven seconds and must exit cleanly before the topic ships.