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

The Johnson–Lindenstrauss (JL) lemma is a foundational result in high-dimensional geometry: a suitable random map into m = O(ε⁻² log n) dimensions preserves all pairwise distances among n points within a factor of 1 ± ε. Yet this relative-error guarantee does not separately control the fine-scale information needed to rank neighbors or estimate covariance shape. We quantify how much information linear sketches retain beyond preserving distances. We first show how JL bounds limit fine-scale geometric recovery. For Gaussian data, pairwise distances concentrate around a common baseline, while centered fluctuations carry comparative geometry. We show that, to certify these fluctuations, the projection dimension must scale with the ambient dimension itself, eliminating compression. We then prove that an independent Gaussian cloud in ℝᵐ, matched only to the mean distance, can satisfy the JL bounds while remaining independent of the data. Consequently, JL bounds alone cannot certify the geometric information that a linear sketch retains. We next establish exact recovery limits for distance features, neighbor rankings, and covariance shape. For isotropic data, the squared distance splits into independent retained and discarded components. We prove an estimator-independent limit: no square-integrable distance feature retains more than a fraction m/d of its variance, corresponding to correlation √(m/d). Using a Laguerre expansion, we resolve the recoverable variance of each fluctuation mode. For general covariance, optimal distance-value recovery equals the leading-m share of squared-eigenvalue mass, though nonlinear features can exceed this share under uneven spectral retention. Rankings inherit the correlation scale. Pairwise agreement is only Θ(√(m/d)) above chance, and fixed-candidate nearest-neighbor overlap approaches chance as m/d → 0. We also prove that a single sampled projection can satisfy a uniform JL bound even as its mean Kendall correlation vanishes when log n ≪ m ≪ d. Averaged over Haar projections, mean and scale information retain a fraction m/d, whereas diffuse traceless shape retains exactly (m−1)(m+2)/((d−1)(d+2)) ∼ (m/d)² once overall scale is removed. For a general known map, its rank governs optimal inference, its spectral spread limits uncorrected norm estimation, and its small singular values control noisy inversion.