Johnson–Lindenstrauss lemma

The Johnson–Lindenstrauss lemma states that any finite set of points in Euclidean space can be mapped into dimension proportional to the logarithm of its size while approximately preserving all pairwise distances.

Random projection: A linear map that projects vectors onto a lower-dimensional subspace, often using randomly chosen directions. Randomly chosen projection matrices provide a standard construction of the lemma’s distance-preserving maps.
Dimensionality reduction: The transformation of data into a representation with fewer dimensions. The lemma gives a formal distance-preserving guarantee for a widely used form of this task.
William B. Johnson: An American mathematician known for work in functional analysis and Banach space theory. He coauthored the 1984 paper establishing the finite-dimensional embedding result.
Johnson–Lindenstrauss flattening lemma: A related theorem that embeds finite-dimensional normed spaces into lower-dimensional spaces with controlled distortion. Unlike the classical lemma, it addresses entire finite-dimensional normed spaces rather than finite point sets.
Subgaussian random variable: A random variable whose tail probabilities decay at least as fast as those of a Gaussian with comparable variance. Subgaussian tails bound the chance that a projected pair’s distance deviates substantially.
Locality-sensitive hashing: A family of hash functions designed to map nearby points to the same bucket more often than distant points. Low-dimensional projections can precede hashing to reduce the cost of similarity search.
Joram Lindenstrauss: An Israeli mathematician known for contributions to functional analysis and convex geometry. He coauthored the theorem’s original paper with William B. Johnson.
Bourgain embedding theorem: A theorem stating that every finite metric space embeds into Hilbert space with logarithmic distortion. It covers arbitrary finite metrics, while the Johnson–Lindenstrauss lemma preserves Euclidean distances with small distortion.
Concentration of measure: The tendency of a function of many random variables to remain close to its expected value. Concentration keeps the projected length of each fixed vector near its original length.
Nearest neighbor search: The problem of finding data points closest to a query under a chosen distance measure. Preserving pairwise distances can retain useful nearest-neighbor structure after compression.

Linked from 1 page

Concentration inequalityRelated: Concentration of random projections supplies the distance-preservation guarantee.