論文の概要: Reconstruction of Manifold Distances from Noisy Observations

• arxiv url: http://arxiv.org/abs/2511.13025v1
• Date: Mon, 17 Nov 2025 06:24:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-18 14:36:24.718387
• Title: Reconstruction of Manifold Distances from Noisy Observations
• Title（参考訳）: ノイズ観測によるマニフォールド距離の再構成
• Authors: Charles Fefferman, Jonathan Marty, Kevin Ren,
• Abstract要約: 雑音の対距離観測から多様体の内在幾何学を再構築する問題を考察する。 十分密集した$M$のサブサンプルにおいて、点間のすべての距離を復元する新しい枠組みを開発する。 サンプリング確率の定量的な下限は、最初のアルゴリズムでクラスタ構造を変更し、すべてのリカバリ保証を拡張するのに十分であることを示す。
• 参考スコア（独自算出の注目度）: 0.745554610293091
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We consider the problem of reconstructing the intrinsic geometry of a manifold from noisy pairwise distance observations. Specifically, let $M$ denote a diameter 1 d-dimensional manifold and $μ$ a probability measure on $M$ that is mutually absolutely continuous with the volume measure. Suppose $X_1,\dots,X_N$ are i.i.d. samples of $μ$ and we observe noisy-distance random variables $d'(X_j, X_k)$ that are related to the true geodesic distances $d(X_j,X_k)$. With mild assumptions on the distributions and independence of the noisy distances, we develop a new framework for recovering all distances between points in a sufficiently dense subsample of $M$. Our framework improves on previous work which assumed i.i.d. additive noise with known moments. Our method is based on a new way to estimate $L_2$-norms of certain expectation-functions $f_x(y)=\mathbb{E}d'(x,y)$ and use them to build robust clusters centered at points of our sample. Using a new geometric argument, we establish that, under mild geometric assumptions--bounded curvature and positive injectivity radius--these clusters allow one to recover the true distances between points in the sample up to an additive error of $O(\varepsilon \log \varepsilon^{-1})$. We develop two distinct algorithms for producing these clusters. The first achieves a sample complexity $N \asymp \varepsilon^{-2d-2}\log(1/\varepsilon)$ and runtime $o(N^3)$. The second introduces novel geometric ideas that warrant further investigation. In the presence of missing observations, 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. Our main technical result also elucidates which properties of a manifold are necessary for the distance recovery, which suggests further extension of our techniques to a broader class of metric probability spaces.
• Abstract（参考訳）: 雑音の対距離観測から多様体の内在幾何学を再構築する問題を考察する。 具体的には、$M$ は直径 1 d-次元多様体を表し、$μ$ は体積測度と相互に絶対連続な $M$ 上の確率測度を表す。 X_1,\dots,X_N$ を $μ$ のサンプルとし、真測地線距離 $d(X_j, X_k)$ に関連するノイズ依存確率変数 $d'(X_j, X_k)$ を観測する。 雑音距離の分布と独立性を軽度に仮定し、十分密集した$M$のサブサンプルにおいて点間のすべての距離を復元する新しい枠組みを開発する。 我々の枠組みは、既知モーメントを持つ付加音を仮定する以前の作業を改善する。 提案手法は,特定の期待関数の$L_2$-normsを$f_x(y)=\mathbb{E}d'(x,y)$で推定し,サンプルの点を中心にロバストなクラスタを構築する方法に基づいている。 新しい幾何論法を用いて、緩やかな幾何学的仮定の下で、有界曲率と正の射影半径-これらのクラスターはサンプル内の点間の真の距離を$O(\varepsilon \log \varepsilon^{-1})$の加法誤差まで回復させる。 我々はこれらのクラスタを生成するための2つの異なるアルゴリズムを開発した。 最初は、サンプル複雑性$N \asymp \varepsilon^{-2d-2}\log(1/\varepsilon)$とランタイム$o(N^3)$を達成する。 第二に、新たな幾何学的考え方を導入し、さらなる調査を保証している。 欠落した観測が存在する場合,サンプリング確率の定量的な下限は,第1のアルゴリズムでクラスタ構造を修正し,すべてのリカバリ保証を拡張するのに十分であることを示す。 我々の主要な技術的結果は、距離回復に多様体の性質がどの性質を必要とするかも解明し、より広い距離確率空間のクラスへの我々の手法のさらなる拡張を示唆している。

関連論文リスト

• Sublinear Time Quantum Sensitivity Sampling [57.356528942341534]
  本稿では、量子感応サンプリングのための統一的なフレームワークを提案し、量子コンピューティングの利点を古典近似問題の幅広いクラスに拡張する。 我々のフレームワークは、コアセットを構築するための合理化されたアプローチを提供し、クラスタリング、回帰、低ランク近似などのアプリケーションにおいて、大幅なランタイム改善を提供します。
  論文  参考訳（メタデータ） (2025-09-20T20:18:49Z)
• Fundamental Limits of Learning High-dimensional Simplices in Noisy Regimes [0.5892638927736114]
  確率の高いアルゴリズムは、$ell$または総変分(TV)距離を真単純度から最大$varepsilon$で出力する。 雑音のないシナリオでは、我々の下界の$n ge Omega(K/varepsilon)$は既知の上界を定数要素まで一致させる。
  論文  参考訳（メタデータ） (2025-06-11T18:35:38Z)
• Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
  以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。 本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-11-01T17:59:53Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Sample Complexity Bounds for Learning High-dimensional Simplices in Noisy Regimes [5.526935605535376]
  ノイズの多いサンプルから単純さを学習するために、サンプルの複雑さが結びついているのがわかります。 我々は、$mathrmSNRgeOmegaleft(K1/2right)$ である限り、ノイズのないシステムのサンプルの複雑さは、ノイズのないケースのそれと同じ順序であることを示す。
  論文  参考訳（メタデータ） (2022-09-09T23:35:25Z)
• Non-Parametric Estimation of Manifolds from Noisy Data [1.0152838128195467]
  ノイズの多いサンプルの有限集合から$mathbbRD$の$d$次元部分多様体を推定する問題を検討する。 点推定では$n-frack2k + d$、接空間の推定では$n-frack-12k + d$の収束率を推定する。
  論文  参考訳（メタデータ） (2021-05-11T02:29:33Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。 Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
  論文  参考訳（メタデータ） (2020-06-04T17:51:00Z)
• Randomized Bregman Coordinate Descent Methods for Non-Lipschitz Optimization [31.474280642125734]
  そこで本研究では,新しいテクステンラン化ブレグマン座標降下法(CD)を提案する。 提案手法は$O(epsilon-2n)$であり,$n$は座標のブロック数であることを示す。
  論文  参考訳（メタデータ） (2020-01-15T09:57:38Z)

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

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