論文の概要: Denoising distances beyond the volumetric barrier

• arxiv url: http://arxiv.org/abs/2604.00432v1
• Date: Wed, 01 Apr 2026 03:20:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-02 16:44:31.814688
• Title: Denoising distances beyond the volumetric barrier
• Title（参考訳）: 体積障壁を越えての距離を測る
• Authors: Han Huang, Pakawut Jiradilok, Elchanan Mossel,
• Abstract要約: ORDER は、次数 $n-ari(d+5)$ のポイントワイド距離推定を、時間内に$n$のポリロジミック因子まで達成する。 我々は、再構成された計量測度空間と真の潜在多様体の間のグロモフ=ワッサーシュタイン距離が位数$n-1/d$であることを証明する。 我々の結果は、雑音の対距離、ランダムな幾何グラフ、未知の接続確率関数の一般モデルを含む非常に一般的な設定で証明されている。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: ランダムな幾何学グラフから$d$次元リーマン多様体の潜在幾何学を再構築する問題を考察する。 最近の研究は、ランダムな幾何グラフから多様体の回復において顕著な進歩を遂げ、より一般的にはノイズ距離からもたらされるが、対距離推定の精度は、体積障壁、すなわち、自然サンプルスポーキングスケール $n^{-1/d}$ によって根本的に制限されている。 本稿では,次数$n^{-2/(d+5)} の点方向距離推定精度を多項式時間で$n$ の多元対数因子まで向上する新しい手法である Orthogonal Ring Distance Estimation Routine (ORDER) を提案する。 これは、次元$d > 5$の体積障壁を厳密に破る。 点精度が$n^{-1/d}$よりも高い結果、再構成された計量測度空間と真の潜在多様体の間のグロモフ=ワッサーシュタイン距離が$n^{-1/d}$であることを示す。 これは経験的測度のワッサーシュタイン収束率と一致し、再構成されたグラフ計量が、サンプリングされた点の完全な対距離行列にアクセスできるのと同じくらい漸近的であることを示す。 我々の結果は、雑音の対距離、スパースなランダムな幾何グラフ、未知の接続確率関数の一般モデルを含む非常に一般的な設定で証明されている。

関連論文リスト

• Riemannian Zeroth-Order Gradient Estimation with Structure-Preserving Metrics for Geodesically Incomplete Manifolds [57.179679246370114]
  測地的に完備な測度を構築し、新しい測度の下での静止点が元の測度の下で定常であることを保証する。 構成された計量$g'$の下の$-固定点もまた、元の計量$g'$の下の$-定常点に対応する。 実用的なメッシュ最適化タスクの実験は、測地的完全性がない場合でも、我々のフレームワークが安定した収束を維持することを示した。
  論文  参考訳（メタデータ） (2026-01-12T22:08:03Z)
• Comparing Labeled Markov Chains: A Cantor-Kantorovich Approach [53.66196601631798]
  最近導入されたカントール・カントロビッチ距離(CK)について検討した。 特に、後者は有限水平全変動距離の割引和として表すことができる。 より正確には、CK距離の正確な計算は#P-hardである。
  論文  参考訳（メタデータ） (2025-11-22T16:02:56Z)
• Reconstruction of Manifold Distances from Noisy Observations [0.745554610293091]
  雑音の対距離観測から多様体の内在幾何学を再構築する問題を考察する。 十分密集した$M$のサブサンプルにおいて、点間のすべての距離を復元する新しい枠組みを開発する。 サンプリング確率の定量的な下限は、最初のアルゴリズムでクラスタ構造を変更し、すべてのリカバリ保証を拡張するのに十分であることを示す。
  論文  参考訳（メタデータ） (2025-11-17T06:24:31Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Reconstructing the Geometry of Random Geometric Graphs [9.004991291124096]
  ランダム幾何学グラフは、距離空間上で定義されたランダムグラフモデルである。 サンプルグラフから基底空間の幾何を効率的に再構成する方法を示す。
  論文  参考訳（メタデータ） (2024-02-14T21:34:44Z)
• Moments, Random Walks, and Limits for Spectrum Approximation [40.43008834125277]
  我々は、ワッサーシュタイン1距離において精度$epsilon$に近似できない$[-1,1]$に分布が存在することを示す。 正規化グラフ隣接行列のスペクトルに対する$epsilon$-accurate近似を一定の確率で計算することはできない。
  論文  参考訳（メタデータ） (2023-07-02T05:03:38Z)
• Min-Max Optimization Made Simple: Approximating the Proximal Point Method via Contraction Maps [77.8999425439444]
  本稿では,凸/凹凸 min-max 問題に対して,ほぼ最適収束率を許容する一階法を提案する。 我々の研究は、近点法の更新規則を精度良く近似できるという事実に基づいている。
  論文  参考訳（メタデータ） (2023-01-10T12:18:47Z)
• Convergence of the Riemannian Langevin Algorithm [10.279748604797911]
  計量$g$の多様体上の自然測度に関して、密度$nu$の分布からサンプリングする問題を研究する。 対数障壁によって定義されるポリトープに制限された等尺的密度をサンプリングする手法が,本手法の特例である。
  論文  参考訳（メタデータ） (2022-04-22T16:56:00Z)
• Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
  標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。 マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
  論文  参考訳（メタデータ） (2021-12-23T18:47:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。