The dimension does not appear
Compressing data usually costs something proportional to how much is thrown away. A matrix reduced to its first k singular directions loses exactly , and the best approximation there is checks that as an equality. The loss is the tail of the spectrum, and it is what it is.
Random projection does not behave like that, and the way it fails to is the reason an entire field exists.
Take sixty vectors, each with four hundred coordinates. Multiply each by the same random 200×400 matrix, so each becomes a vector of two hundred numbers. Four hundred coordinates reduced to two hundred — half the data discarded, chosen with no reference whatever to what the data contains.
Every length is preserved to within about twelve per cent.
Now do the same with vectors of one hundred coordinates instead of four hundred, using a 200×100 sketch. The distortion is about thirteen per cent — slightly worse in the lower dimension.
The dimension the vectors live in barely enters. That is the Johnson–Lindenstrauss lemma, and it is the least intuitive true statement in this subject.
What the lemma says
For any set of m points and any ε, there is a projection into O(log m / ε²) dimensions that preserves every pairwise distance to within a factor of 1 ± ε.
Three things in that statement are worth separating.
The target dimension depends on log m. Not on m, and not on the dimension the points came from. Doubling the number of points adds a constant to the target dimension; multiplying the original dimension by a hundred adds nothing at all.
It depends on ε⁻². Which is a harsh dependence: halving the distortion costs four times the dimension. This is the parameter that makes the technique expensive when high accuracy is wanted, and it is why sketching is used where an approximation is acceptable rather than where precision is required.
And a random projection works with high probability. The proof is not a construction — it does not build the good projection, it shows that a random one is good with probability close to 1, and that the probability improves fast enough that some projection must exist. This is the probabilistic method, and it is why the result arrives with the same kind of guarantee as everything else in a bound that holds with probability.
Why the dimension does not appear
The mechanism is worth having, because stated without it the result sounds like a trick.
The sketch of a vector is a set of independent inner products with random Gaussian directions. Each one is a random variable whose variance is proportional to the vector’s length and — this is the step — whose distribution does not depend on the dimension at all. A unit vector in four hundred dimensions and a unit vector in one hundred both produce, against a normalised Gaussian direction, a standard normal number.
So the sketched length is an average of l such quantities, its concentration around the true length is governed by l alone, and the dimension has dropped out before any counting begins.
What the number of vectors does is set how many chances there are for one of them to be unlucky. The distortion drawn here is the worst over the set, so preserving more vectors means taking a maximum over more samples, and the tail of a Gaussian is thin enough that the cost of that maximum grows only logarithmically.
That is the whole shape of it: the dimension is averaged over and the count is maximised over, and those two operations have very different costs.
The number of vectors is the slider, and it moves slowly
Since the dimension does nothing and the width does everything, the remaining question is what the count actually costs — and the slider is there to answer it.
The lemma says the target dimension grows like log m. Logarithmic dependences are easy to state and hard to feel, so the figure makes it concrete: dragging from twenty vectors to a hundred and twenty — a factor of six — moves the curves, and moves them by very little. The distortion rises, because the worst of a hundred and twenty samples is worse than the worst of twenty, and it rises by far less than the count does.
That is the property which makes the technique usable at scale. Preserving a million vectors rather than a thousand costs a factor of two in the target dimension, not a factor of a thousand, and a sketch sized for a large collection is not much wider than one sized for a small one.
It is also where the guarantee is doing its most surprising work. A statement about every vector in a large set, with no assumption about how the vectors are arranged, would normally require a dimension that grows with the set. It does not, because the failure probability for any one vector falls exponentially in the sketch width, and an exponential beats the union bound over m vectors as soon as the width passes log m.
The rate, fitted
The lemma’s ε⁻² dependence, read the other way, says the distortion falls like the inverse square root of the sketch width. The figure checks it rather than citing it.
Across sketch widths from 25 rows to 400 — a factor of 16 — the median distortion falls by a factor measured on every build, against a predicted √16 = 4. The assertion brackets the measurement between half and twice the prediction, which is the right looseness for a claim about an exponent when the constant is not known.
The practical reading is unwelcome and worth stating plainly. Sixteen times the rows buys four times the accuracy. A sketch that gets to 12% distortion at 200 rows needs 20,000 rows to reach 1.2%, and at that point it is no longer a sketch of anything. This is the technique’s real boundary: it is excellent at reducing dimension by a large factor at moderate accuracy, and useless for reducing it at high accuracy.
What the two curves being on top of each other rules out
The figure’s central claim is drawn as an absence — two curves that do not separate — and an absence is easy to produce by accident. So it is asserted at every point rather than observed at one.
At each of the five sketch widths, the median distortion at dimension 64 and at dimension 256 must agree within a factor of two. Not “the curves look similar”: a bounded ratio, at every width, at every position of the slider.
The complementary assertion is that the width does control it — a wider sketch distorts less, by at least a factor of two across the range. Together they say the figure has one active variable and one inactive one, which is the claim, and either assertion alone would pass on a plot where nothing depended on anything.
Why the projection can be worse than random
A detail that sounds like an optimisation and is closer to the point of the field.
A dense Gaussian sketch costs l·d multiplications per vector, which for a large d is not obviously cheaper than whatever it was avoiding. The lemma does not require Gaussians, and the practical constructions exploit that.
Sub-sampled randomised Hadamard transforms apply a fast orthogonal transform and then select rows, costing d log d rather than l·d. Sparse sketches — CountSketch and its relatives — put a single nonzero in each column, so applying the sketch costs one operation per nonzero of the input and can be done in a single streaming pass.
The distortion guarantees are slightly worse and the cost is dramatically lower, and for the applications sketching is used in that trade is always taken. The site draws the Gaussian case because it is the one where the mechanism is visible; nothing in production uses it.
What is asserted here
The distortion barely notices a fourfold change of dimension, at every sketch width and every slider position, as a bounded ratio.
A wider sketch distorts less, by at least a factor of two across the range drawn.
And it falls at the inverse-square-root rate, bracketed against the prediction.
The band is the spread across seeds, drawn rather than summarised, for the reason a bound that holds with probability gives: a single line here would represent the one number a deterministic method would also produce.
Where the mechanism stops being about vectors
There is a step in the reasoning that is easy to miss and is doing a great deal of work in every application below.
The lemma is a statement about a finite set of vectors. Its proof takes a union bound over the set, and a union bound needs something to sum over. So it says nothing directly about preserving the lengths of all vectors in a subspace, which is uncountable.
That stronger statement is true and is a separate theorem — a subspace embedding — and it is the one the least-squares and range-finding applications actually need. Solving a sketched least-squares problem requires that ‖SAx‖ ≈ ‖Ax‖ for every x, not for sixty particular ones, and the width required scales with the subspace’s dimension rather than with the logarithm of a count.
The proof route is a net argument: cover the unit sphere of the subspace with a finite set of points fine enough that preserving those preserves everything between, then apply the finite lemma to the net. The cost is that the target dimension becomes O(d/ε²) for a d-dimensional subspace rather than O(log m/ε²) — linear in the dimension of the subspace being embedded, though still independent of the ambient dimension the subspace sits in.
The figure measures the finite version, which is the one whose statement can be checked directly by sketching sixty vectors and looking at sixty lengths. The subspace version is what makes the applications work, and it is worth knowing that they are different theorems with different costs.
What this is used for
Three families, and the third is the one that connects back to this site’s subject.
Nearest neighbours and similarity search. If distances are preserved, a search in the sketched space returns approximately the right answers at a fraction of the cost. This is the lemma’s original application and the distortion translates directly into a relevance loss.
Least squares. Sketch the rows of an overdetermined system and solve the smaller problem — which is what randomisation does not create structure measures: a 400×12 problem sketched to 60 rows gives a residual within 10% of the exact one, and never below it.
And range finding, which is the randomised SVD. Multiplying A by a random matrix is exactly sketching the columns of A, and the reason the sample captures the range is the reason the lengths survive. A bound that holds with probability is this essay’s lemma applied to a matrix rather than to a set of vectors.
Why it holds at all: what a high-dimensional space is like
The result stops feeling like a trick once one fact about high-dimensional geometry is in hand, and it is worth stating because it explains several other things on this site as well.
In a space of dimension d, two independently chosen random directions are nearly orthogonal, and the higher d is the more nearly. Their inner product concentrates around zero with a spread of about 1/√d, so in four hundred dimensions two random unit vectors have an inner product of roughly 0.05. Not occasionally — essentially always.
That is why a random projection can afford to be careless. It is projecting onto l directions that are very nearly mutually orthogonal and very nearly unrelated to the data, and a projection onto near-orthogonal directions is close to being an isometry on the part of the space it keeps. The higher the dimension, the better the random directions behave — which is the same phenomenon read from the other end, and the reason the dimension helps rather than hurts.
The same fact turns up in the site’s own machinery. randomOrthogonal builds an orthogonal matrix by
orthogonalising a Gaussian one, and it works well precisely because the columns start out nearly
orthogonal and the Gram–Schmidt has little to remove. And it is the counterpoint to
the condition number is an amplifier’s finding that
a random perturbation direction reaches 0.29κ of the worst case at the median: in high dimensions,
random directions are reliably typical, which is bad news when the typical case is bad and good news
here.
The honest limit
The lemma preserves lengths, and length is not everything.
It does not preserve angles well at small distortion, because an angle is a ratio of quantities each carrying its own error. Two nearly parallel vectors can come out of a sketch measurably less parallel, and any computation whose answer depends on a small angle is one the sketch has damaged.
It does not preserve the spectrum. A sketched matrix has different singular values from the original, and the range finder works not because the spectrum survives but because the space approximately does.
And it says nothing about a matrix with no low-rank structure. The distortion bound holds for any set of vectors, so the sketch is always a faithful-ish projection — and being faithfully projected does not make a matrix approximable. That is the boundary the next essay is about, and it is the one place where this field’s enthusiasm most needs a number attached to it.
What the figure had to give up to be drawn
A note on the measurement, since the sizes here are smaller than the ones the opening paragraph describes and the reason is worth recording.
The first version of this figure used dimensions of 100 and 400 — the pair quoted in the opening paragraph, and the pair the library’s own check still runs at — sketch widths up to 800, and eight seeds per point. It is the right experiment and it took sixty-three seconds to generate across the slider’s positions — every one of which is produced at build time by the same function that draws the static figure, because a frame a reader can reach that was never generated is a frame whose assertions were never run.
The cost is unavoidable arithmetic: applying an 800×400 sketch to two hundred and forty vectors is seventy-seven million multiply-adds, and there are twelve slider positions and two dimensions and eight seeds.
So the drawn version uses 64 and 256 — still a factor of four, which is the comparison the figure
exists to make — widths to 400, and five seeds. The claim is unchanged, and the numbers in the opening
paragraph come from the wider experiment that assertSketchPreservesLengths still runs on every
build, which is why they do not match this figure’s axis labels.
Recording the reduction matters because it is the kind of change that silently weakens an argument. Five seeds is a thinner band than eight, and a factor of four in dimension is a weaker test than a factor of sixteen would be. Neither affects what is asserted, and both are the sort of thing that would be invisible afterwards if the figure did not say so.