The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

What the math gives to ML

The paper establishes the sharp target dimension for preserving all pairwise Euclidean distances among an n-point set, including finite-sample and ambient-dimension regimes hidden by the usual O(epsilon^{-2} log n) statement. The transferable asset is a principled feature-width rule: a linear projection need not use more than the smaller of the intrinsic ambient dimension, n-1, and log(2+epsilon^2 n)/epsilon^2, while preserving geometry up to 1+epsilon distortion. This suggests replacing uniformly wide hidden representations with calibrated linear bottlenecks whose width is selected from the number of objects being jointly processed and the tolerated distortion. Because the extraction gives no explicit optimized projection beyond the standard Gaussian example, the theorem should be tested as a width-selection hypothesis using randomized or learned projections.