An Elementary Proof of a Theorem of Johnson and Lindenstrauss
📜 Abstract
A result of Johnson and Lindenstrauss [13] shows that a set of n points in high dimensional Euclidean space can be mapped into an O(log n/ε²)-dimensional Euclidean space such that the distance between any two points changes by only a factor of (1 ± ε). In this note, we prove this theorem using elementary probabilistic techniques.
✨ Summary
The paper gives an elementary probabilistic proof of the Johnson–Lindenstrauss dimension-reduction theorem. It analyzes the projection of a uniformly random point on a high-dimensional sphere onto a fixed k-dimensional subspace, representing the spherical point using normalized independent Gaussian variables. A Chernoff-style moment-generating-function argument establishes concentration bounds for the projected squared length around its expectation. Applying these bounds to the difference vector of each pair of input points and then using a union bound yields a k-dimensional embedding with k = O(ε⁻² log n) that preserves all pairwise squared Euclidean distances within factors of 1 − ε and 1 + ε. The construction is randomized and can be found in randomized polynomial time by repeatedly sampling projections.
The paper’s documented research influence is primarily methodological and pedagogical. Ailon and Chazelle later identified Dasgupta and Gupta’s work as one of the major simplifications of the original Johnson–Lindenstrauss proof, while developing the Fast Johnson–Lindenstrauss Transform to reduce the computational cost of random projections and accelerate approximate-nearest-neighbor search. (cs.princeton.edu) The paper is also used as instructional material in courses covering dimensionality reduction, random projections, and high-dimensional geometry. (cseweb.ucsd.edu) The search found no specific industry deployment attributable directly to this proof; its concrete role is as a concise proof and reference underlying later work on randomized embeddings and fast projection methods.