Johnson–Lindenstrauss lemma

A theorem stating that any n points in a high-dimensional Euclidean space can be mapped into a space of dimension k on the order of (log n)/ε² so that every pairwise Euclidean distanceEuclidean distance, n.: How far apart two points are in a straight line, as a ruler would measure it, extended from two or three dimensions to lists of numbers of any length. is preserved within a factor of 1 ± ε — and that a suitably scaled random linear projection achieves this with high probability. Strikingly, k depends only on the number of points and the tolerance, not on the original dimensionalitydimensionality, n.: How many separate numbers are needed to describe something. A point on a map needs two; an AI's description of a single word may use thousands.. The lemma justifies random projections for speeding up approximate nearest neighbor searchapproximate nearest neighbor search, n.: A family of shortcuts for finding the most similar items in a huge collection without checking every one — accepting an occasional miss in exchange for answers thousands of times faster., sketching and streaming algorithms, compressed sensing and randomized linear algebra, and it helps explain why compact embeddingsembedding, n.: A list of numbers that stands for a word, picture or other item, arranged so that similar items get similar lists. It lets a computer measure similarity of meaning as distance. can be faithful. A related fact — that exponentially many nearly orthogonal directions fit in d dimensions — is invoked in interpretabilityinterpretability, n.: The effort to understand how an AI system arrives at its outputs — what information it uses and how it combines it — instead of treating it as a sealed black box. to explain superpositionsuperposition, n.: The way a neural network squeezes more concepts into its internal activity than it has neurons, by letting them overlap — a main reason its insides are hard to read., in which networks represent more featuresfeature (interpretability), n.: A concept or property that a neural network represents internally — such as 'is French', 'mentions a bridge' or 'this code has a bug' — usually corresponding to a direction in its internal activity. than they have neurons.

We used a Johnson–Lindenstrauss random projection to shrink the vectors before clustering, accepting small distance distortions.