# Exact Limits of Random Projections for Preserving Geometry: Distance Recovery, Nearest-Neighbor Rankings, and Covariance Shape in Gaussian Models

arXiv: https://arxiv.org/abs/2609.02155 · HTML: https://mlsanity.com/paper/2609.02155/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 51 references that are in the map.
- First posted on arXiv 2 Sep 2026.

## Builds on (most cited first, 8 of 8)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [Products of Many Large Random Matrices and Gradients in Deep Neural Networks](https://mlsanity.com/paper/1812.05994/) (2018)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Random-projection ensemble classification](https://mlsanity.com/paper/1504.04595/) (2015)
- [Experiments with Random Projection](https://mlsanity.com/paper/1301.3849/) (2013)
- [On the Non-asymptotic and Sharp Lower Tail Bounds of Random Variables](https://mlsanity.com/paper/1810.09006/) (2018)
- [Fast k-Nearest Neighbour Search via Dynamic Continuous Indexing](https://mlsanity.com/paper/1512.00442/) (2015)

## Abstract (arXiv)

The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of n points to m=O(varepsilon-2log n) dimensions preserves pairwise squared distances within relative error varepsilon with high probability, and this dimension order is asymptotically optimal. In high dimensions, however, distances concentrate around a baseline while key geometric information lies in much smaller fluctuations. We show that the JL bound can therefore be uninformative about retained geometry: an independent Gaussian replacement map can satisfy it even though the replacement cloud is independent of the original data. We then ask how well any decoder can recover a feature f(D) of a squared distance D from a linear sketch. Under squared-error loss, the optimal decoder is conditional expectation, so recovery defines a linear operator whose singular values quantify feature recovery. For isotropic Gaussian data (Sigma=σ2 Id), we diagonalize this operator in closed form. For fixed k with m,d-m→∞, its kth singular value satisfies ℓk≈(m/ d)k/2. This yields three sharp consequences. A rank-m sketch retains at most an m/d fraction of the variance of any feature of one squared distance. If m→∞ and m/d→0, the expected Kendall correlation is frac2π√m/d(1+o(1)); for fixed q, nearest- neighbor agreement tends to 1/q. Yet one projection can satisfy the JL bound while mean Kendall correlation vanishes when log nll mll d. After removing scale, Haar-averaged retained covariance-shape information is (m/d)2. Thus JL distance preservation does not quantify the geometry available for comparison or inference.