jl-lemma-target-dimension-constant-eight
IN premise — summaries/2026/08/24/wiki-JohnsonE28093Lindenstrauss_lemma.md
Created 2026-08-24T17:11:13+00:00
The Johnson–Lindenstrauss lemma states that N points in ℝⁿ can be embedded into ℝᵏ with k > 8(ln N)/ε² such that all pairwise distances are preserved within a factor of (1 ± ε), where k depends only on log(N) and not on the ambient dimension n.
Summary
You can shrink a cloud of points from a very high-dimensional space down to a much smaller one, and the pairwise distances between them will barely change. The target dimension depends only on how many points you have, not on how high-dimensional the original space was, which means the extra dimensions are essentially wasted overhead for preserving the data's geometric structure.