Skip to content

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

Sep 2026 · 0 citations · 51 references
Computer Science Mathematics

TL;DR

It is shown 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.

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.

View source

Similar papers

#machine learning Preprint Oct 2026

On k-nearest-neighbor regression in metric spaces

We study mean squared consistency of k-nearest-neighbor regression for metric space valued features. For a fixed feature distribution mu with atomless distance distributions, we describe how neighbor selection redistributes probability through the density of a uniformly chosen neighbor of an independent query. This giv...

L. Györfi, Vladimir G. Pestov, Harro Walk et al. · 0 citations
Preprint Sep 2026

Low Dimensional Sampling under Reconstructed Constraints

We study sampling from a distribution supported on an unknown compact $d$-dimensional $C^2$ manifold $M\subset\mathbb{R}^D$, observed only through i.i.d. uniform points from $M$. We reconstruct the constraint using an adaptive local-convex-hull estimator and target an ambient distribution penalized by squared distance...

Imon Banerjee, Riddhiman Bhattacharyya · 1 citation
#machine learning Preprint Oct 2026

Sliced Wasserstein Sketches with Error Certificates

Compact representations that support geometrically meaningful comparisons are valuable for learning from probability distributions. We study optimal, free-weight $M$-atom quantization of one-dimensional probability measures in quadratic Wasserstein distance and extend it to higher dimensions via slicing. Using $L$ shar...

Elaheh Akbari, James Liu, Keaton Hamm et al. · 0 citations
Preprint Oct 2026

Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces

A finite metric space with $N$ points admits an exact representation in a pseudo-Euclidean space of dimension at most $N-1$. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for $4...

Nikita Muravya, A. Bespalov, Anna Vozianova · 0 citations
Preprint Oct 2026

Finite-Sample Bounds for Fr\'echet Means of Dependent Data in Metric Spaces with Curvature Bounded Above

We prove finite-sample risk bounds for empirical quadratic and power Fr\'echet means in geodesic metric spaces with curvature bounded above for observations with arbitrary joint law. We compare the sample with exchangeable copies in which one observation is redrawn independently of the original sample and the others mo...

Zoraida F. Rico, C. Schötz · 0 citations
Preprint Sep 2026

Vector balancing in convex order

It is proved that Covariance-matched analytic uniformly log-concave sources can have a greatest useful-data-only private release with infinite information, while no greatest full-data release exists.

E. Ercan · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.