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

Abstract:The Johnson-Lindenstrauss (JL) lemma guarantees that a random projection of $n$ points to
$m=O(\varepsilon^{-2}\log 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=\sigma^2 I_d$), we diagonalize this operator in closed form.
For fixed $k$ with $m,d-m\to\infty$, its $k$th singular value satisfies $\ell_k\approx(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\to\infty$ and $m/d\to0$, 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 n\ll m\ll 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.

Bookmark

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools