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

arXiv:2609.02155v1 Announce Type: new Abstract: The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of n points to m=O(arepsilon^{-2}log n) dimensions preserves pairwise squared distances within relative error arepsilon 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=sigma^2 I_d), we diagonalize this operator in closed form. For fixed k with m,d-moinfty, its kth singular value satisfies ell_kapprox(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 moinfty and m/do0, the expected Kendall correlation is frac{2}{pi}sqrt{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.

Source: arXiv cs.LG | 2026-09-03