Johnson-Lindenstrauss lemma

Type: Concept

As of November 2026, Johnson-Lindenstrauss lemma has been mentioned in one podcast episode on Institute for Advanced Study (Jan 2026). Classic result in dimensionality reduction that serves as a foundational example for applying trapdoor matrix families.

In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved. In the classical proof of the lemma, the embedding is a random orthogonal projection.