Denoising distances beyond the volumetric barrier

• URL: http://arxiv.org/abs/2604.00432v1
• Date: Wed, 01 Apr 2026 03:20:16 GMT
• Title: Denoising distances beyond the volumetric barrier
• Abstract summary: ORDER achieves pointwise distance estimation of order $n-ari(d+5)$ up to polylogthmic factors in $n$ in time.<n>We prove that the Gromov-Wasserstein distance between the reconstructed metric measure space and the true latent manifold is of order $n-1/d$.<n>Our results are proven in a very general setting which includes general models of noisy pairwise distances, random geometric graphs, and unknown connection probability functions.
• Score: 13.045166411221539
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of reconstructing the latent geometry of a $d$-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/d}$ coming from the fact that a generic point of the manifold typically lies at distance of order $n^{-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)}$ up to polylogarithmic factors in $n$ in polynomial time. This strictly beats the volumetric barrier for dimensions $d > 5$. As a consequence of obtaining pointwise precision better than $n^{-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/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.

Related papers

• Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
  We revisit random projections for reducing the dimension of high-dimensional polygonal curves.<n>We give a simplified proof of the known $O(varepsilon-2log(nm))$ bound on the target dimension of a random projection.<n>Our proof is based on the concept of sparse oblivious subspace embeddings.
  arXiv  Detail & Related papers  (2026-07-03T08:48:35Z)
• Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
  We show that Score-based generative models are trained in high-dimensional ambient spaces.<n>We use a ReLU implementation of nearest-projection coordinates via finite intrinsic anchors and Gauss Newton.
  arXiv  Detail & Related papers  (2026-05-15T10:20:05Z)
• $K-$means with learned metrics [2.339080046284584]
  We study the Fréchet $k-$means of a metric measure space when both the measure and the distance are unknown and have to be estimated.<n>We prove a general result that states that the $k-$means are continuous with respect to the measured Gromov-Hausdorff topology.
  arXiv  Detail & Related papers  (2026-03-15T20:50:59Z)
• Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds [57.179679246370114]
  We construct metrics that are geodesically complete while ensuring that every stationary point under the new metric remains stationary under the original one.<n>An $$-stationary point under the constructed metric $g'$ also corresponds to an $$-stationary point under the original metric $g'$.<n>Experiments on a practical mesh optimization task demonstrate that our framework maintains stable convergence even in the absence of geodesic completeness.
  arXiv  Detail & Related papers  (2026-01-12T22:08:03Z)
• Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach [53.66196601631798]
  We study the recently introduced Cantor-Kantorovich (or CK) distance.<n>In particular we show that the latter can be framed as a discounted sum of finite-horizon Total Variation distances.<n>More precisely, we show that the exact computation of the CK distance is #P-hard.
  arXiv  Detail & Related papers  (2025-11-22T16:02:56Z)
• Reconstruction of Manifold Distances from Noisy Observations [0.745554610293091]
  We consider the problem of reconstructing the intrinsic geometry of a manifold from noisy pairwise distance observations.<n>We develop a new framework for recovering all distances between points in a sufficiently dense subsample of $M$.<n>We show that a quantitative lower bound on sampling probabilities suffices to modify the cluster construction in the first algorithm and extend all recovery guarantees.
  arXiv  Detail & Related papers  (2025-11-17T06:24:31Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• Reconstructing the Geometry of Random Geometric Graphs [9.004991291124096]
  Random geometric graphs are random graph models defined on metric spaces. We show how to efficiently reconstruct the geometry of the underlying space from the sampled graph.
  arXiv  Detail & Related papers  (2024-02-14T21:34:44Z)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $epsilon$ in Wasserstein-1 distance. No algorithm can compute an $epsilon$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability.
  arXiv  Detail & Related papers  (2023-07-02T05:03:38Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  We present a first-order method that admits near-optimal convergence rates for convex/concave min-max problems. Our work is based on the fact that the update rule of the Proximal Point method can be approximated up to accuracy.
  arXiv  Detail & Related papers  (2023-01-10T12:18:47Z)
• Convergence of the Riemannian Langevin Algorithm [10.279748604797911]
  We study the problem of sampling from a distribution with density $nu$ with respect to the natural measure on a manifold with metric $g$. A special case of our approach is sampling isoperimetric densities restricted to polytopes defined by the logarithmic barrier.
  arXiv  Detail & Related papers  (2022-04-22T16:56:00Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  We show a non-asymptotic bound of the order $t_mathrmmix tfracdn$ on the squared error of the last iterate of a standard scheme. We derive corollaries of these results for policy evaluation with Markov noise.
  arXiv  Detail & Related papers  (2021-12-23T18:47:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.