stat.MLJul 24, 2025

Recovering the Euclidean Geometry of High-Dimensional Data Under Heterogeneous Noise

Authors: Keyi Li, Yuval Kluger, Boris Landa

Organizations: Department of Applied & Computational Mathematics, Yale University · Department of Pathology, Yale University · Department of Electrical and Computer Engineering, Yale University

Abstract

Pairwise Euclidean distances provide a simple geometric representation of high-dimensional data and underlie many data analysis methods, including clustering, visualization, and manifold learning. However, in real-world applications, these distances can be severely corrupted by heterogeneous noise, where different data points are subject to different, and potentially large, noise levels. Such noise distorts the distances inhomogeneously, leading to a misrepresentation of the underlying data geometry. In this work, we ask whether the underlying clean Euclidean geometry can nevertheless be recovered from the corrupted pairwise distances. We answer this question affirmatively, showing that, perhaps surprisingly, such recovery is possible across a broad class of high-dimensional settings with underlying low-dimensional geometry, even when the noise magnitudes vary substantially across observations. We develop a principled approach for recovering the clean pairwise distances, without prior knowledge of either the clean data structure or the noise distribution, and establish probabilistic recovery guarantees. In particular, the recovery error converges to zero at polynomial rates as the feature dimension and dataset size increase simultaneously. Experiments on synthetic datasets demonstrate accurate recovery of the Euclidean geometry in challenging regimes and improved robustness of downstream methods that rely on pairwise distances. When applied to real single-cell RNA sequencing data, our method reliably recovers local neighborhood structure, enabling accurate nearest-neighbor identification used in many downstream analyses.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Apr 1, 2026

Denoising distances beyond the volumetric barrier

We study the problem of reconstructing the latent geometry of a dd-dimensional Riemannian manifold from a random geometric graph. While recent works have made significant progress in manifold recovery from random geometric graphs, and more generally from noisy distances, the precision of pairwise distance estimation has been fundamentally constrained by the volumetric barrier, namely the natural sample-spacing scale n−1/dn^{-1/d} coming from the fact that a generic point of the manifold typically lies at distance of order n−1/dn^{-1/d} from the nearest sampled point. In this paper, we introduce a novel approach, Orthogonal Ring Distance Estimation Routine (ORDER), which achieves a pointwise distance estimation precision of order n−2/(d+5)n^{-2/(d+5)} up to polylogarithmic factors in nn in polynomial time. This strictly beats the volumetric barrier for dimensions d>5d > 5. As a consequence of obtaining pointwise precision better than n−1/dn^{-1/d}, we prove that the Gromov--Wasserstein distance between the reconstructed metric measure space and the true latent manifold is of order n−1/dn^{-1/d}. This matches the Wasserstein convergence rate of empirical measures, demonstrating that our reconstructed graph metric is asymptotically as good as having access to the full pairwise distance matrix of the sampled points. Our results are proven in a very general setting which includes general models of noisy pairwise distances, sparse random geometric graphs, and unknown connection probability functions.
Nov 17, 2025

Recovering Geodesic Distances from Noisy Observations

Let (M,d,μ)(M,d,μ) be a nice geodesic probability space (such as a manifold) and X={xi}i∈[N]⊂MX=\{x_i\}_{i\in [N]} \subset M a finite μμ-i.i.d. sample. Suppose we observe noisy distance random variables d′(xi,xj)d'(x_i,x_j). When can the true distances be recovered to small additive error? This question has attracted interest in two disparate fields: latent-space graph models and boundary-value inverse problems. We first show that, taking N≍ε−2d−2∣log⁡ε∣N \asymp ε^{-2d-2}|\logε| and using runtime O(N2.5+od(1))O(N^{2.5+o_d (1)}), we can recover all distances in XX to additive error O(ε∣log⁡ε∣)O(ε|\logε|) with high probability, assuming Ed′(xi,xj)=F(d(xi,xj))\mathbb{E} d'(x_i, x_j) = F(d(x_i,x_j)) for an unknown, increasing bilipschitz FF and with the d′(xi,xj)d'(x_i,x_j) allowed to be arbitrarily heterogeneous in their distribution as long as they are bounded in subgaussian norm. This generalizes existing work, which required FF to be known and made strict assumptions on the distribution of d′(xi,xj)d'(x_i, x_j). Achieving this generalization required a novel ``ruler-building'' procedure to learn FF. We extend our results to a missing data case where we randomly lose access to noisy distances. Our second result uses ideas from the first to tackle a partial observability case: X=Y∪ZX = Y \cup Z with ZZ sampled from MM and YY sampled from an observer subset satisfying visibility conditions that model the assumptions made on the boundary in boundary-value inverse problems. In this setting, we recover all pairwise distances in ZZ to additive error O(ε)O(ε) with ∣Z∣≍ε−2d−2∣log⁡ε∣|Z| \asymp ε^{-2d-2}|\logε|, ∣Y∣≍ε−max⁡{dν,4}|Y| \asymp ε^{-\max\{d_ν,4\}} with dνd_ν determined by the volume-growth properties of the probability measure on the observer set, and runtime O(∣Z∣3)O(|Z|^3). This is, to our knowledge, the first quantitative guarantee for this observer/observed split under noise, which complements existing stability results for boundary data.
Jun 12, 2026

Riemannian Metric Matching for Scalable Geometric Modeling of Distributions

High-dimensional datasets often concentrate near low-dimensional structures, but estimating their geometry from samples typically relies on graphs and kernels that scale poorly with dataset size and dimension. We propose Riemannian metric matching: a denoising probabilistic framework for learning the Riemannian geometry of data using neural networks. Specifically, we learn the carré du champ operator, which, using diffusion geometry, gives us access to the Riemannian geometry toolkit for downstream machine learning and statistical tasks. Our key observation is that the carré du champ operator can be formulated as a conditional expectation over random perturbations of the data, which can be exploited for sample-wise training and constant cost, amortized inference without explicit kernel construction. Empirically, metric matching rivals or improves the accuracy of kk-NN-based diffusion geometry estimators, while enabling amortized inference that is up to 400×400\times faster, and supports graph-free geometric analysis on high-dimensional images where nearest neighbors break down.