論文の概要: Riemannian Optimization for Distance Geometry: A Study of Convergence, Robustness, and Incoherence

• arxiv url: http://arxiv.org/abs/2508.00091v1
• Date: Thu, 31 Jul 2025 18:40:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-04 18:08:53.62753
• Title: Riemannian Optimization for Distance Geometry: A Study of Convergence, Robustness, and Incoherence
• Title（参考訳）: 距離幾何学のためのリーマン最適化:収束性、ロバスト性、不整合性に関する研究
• Authors: Chandler Smith, HanQin Cai, Abiy Tasissa,
• Abstract要約: ユークリッド距離幾何学(EDG)問題は、センサーネットワークの局在化、分子配座、多様体学習など、幅広い用途で発生する。 本稿では,正の半定値グラム行列の空間上での低ランク行列補完タスクとして定式化することで,EDG問題を解決するためのフレームワークを提案する。 利用可能な距離測定は非直交基底での展開係数として符号化され、グラム行列上の最適化は三角形の不等式を通じて暗黙的に幾何学的整合を強制する。
• 参考スコア（独自算出の注目度）: 6.422262171968397
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of recovering a configuration of points from partial pairwise distances, referred to as the Euclidean Distance Geometry (EDG) problem, arises in a broad range of applications, including sensor network localization, molecular conformation, and manifold learning. In this paper, we propose a Riemannian optimization framework for solving the EDG problem by formulating it as a low-rank matrix completion task over the space of positive semi-definite Gram matrices. The available distance measurements are encoded as expansion coefficients in a non-orthogonal basis, and optimization over the Gram matrix implicitly enforces geometric consistency through the triangle inequality, a structure inherited from classical multidimensional scaling. Under a Bernoulli sampling model for observed distances, we prove that Riemannian gradient descent on the manifold of rank-$r$ matrices locally converges linearly with high probability when the sampling probability satisfies $p \geq \mathcal{O}(\nu^2 r^2 \log(n)/n)$, where $\nu$ is an EDG-specific incoherence parameter. Furthermore, we provide an initialization candidate using a one-step hard thresholding procedure that yields convergence, provided the sampling probability satisfies $p \geq \mathcal{O}(\nu r^{3/2} \log^{3/4}(n)/n^{1/4})$. A key technical contribution of this work is the analysis of a symmetric linear operator arising from a dual basis expansion in the non-orthogonal basis, which requires a novel application of the Hanson--Wright inequality to establish an optimal restricted isometry property in the presence of coupled terms. Empirical evaluations on synthetic data demonstrate that our algorithm achieves competitive performance relative to state-of-the-art methods. Moreover, we propose a novel notion of matrix incoherence tailored to the EDG setting and provide robustness guarantees for our method.
• Abstract（参考訳）: ユークリッド距離幾何学(Euclidean Distance Geometry, EDG)問題と呼ばれる部分対距離から点の配置を復元する問題は、センサーネットワークの局在化、分子配座、多様体学習など幅広い応用で発生する。 本稿では,正半定値グラム行列の空間上の低ランク行列完備化タスクとして定式化することにより,EDG問題を解くためのリーマン最適化フレームワークを提案する。 利用可能な距離の測定は、非直交的に拡張係数として符号化され、グラマー行列の最適化は、古典的な多次元スケーリングから継承された構造である三角形の不等式を通じて暗黙的に幾何学的一貫性を強制する。 観測距離に対するベルヌーイサンプリングモデルの下では、サンプリング確率が$p \geq \mathcal{O}(\nu^2 r^2 \log(n)/n)$を満たすとき、ランク-r$行列の多様体上のリーマン勾配が局所的に高確率に収束することが証明される。 さらに、一段階のハードしきい値計算法を用いて初期化候補を提案し、サンプリング確率が$p \geq \mathcal{O}(\nu r^{3/2} \log^{3/4}(n)/n^{1/4})$を満たすことを仮定する。 この研究の重要な技術的貢献は、非直交基底の双対基底展開から生じる対称線型作用素の解析であり、結合項の存在下で最適に制限された等距離性を確立するためにハンソン-ライト不等式を新しく適用する必要がある。 合成データに対する経験的評価は,本アルゴリズムが最先端手法と比較して競争性能を達成できることを実証している。 さらに,EDG設定に適した行列不整合の新たな概念を提案し,本手法の堅牢性を保証する。

関連論文リスト

• Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent [13.27202712518471]
  本稿では,非対称励起勾配 (APGD) と呼ばれるBurer-Monteiro因子化に基づく勾配型アルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2025-04-28T07:13:23Z)
• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  ユークリッド距離情報点対を埋め込む適切な点を見つける問題は、コアタスクとサブマシン学習の問題の両方として生じる。 本稿では,最小限のサンプル数を考えると,この問題を解決することを目的とする。
  論文  参考訳（メタデータ） (2024-10-22T13:02:12Z)
• Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees [6.422262171968397]
  ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。 第一のアルゴリズムは真の解に線形に収束する。 第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
  論文  参考訳（メタデータ） (2024-10-08T21:19:22Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Sharp detection of low-dimensional structure in probability measures via dimensional logarithmic Sobolev inequalities [0.5592394503914488]
  本稿では、所定の基準測度$mu$の摂動として、目標測度$pi$を同定し、近似する手法を提案する。 我々の主な貢献は、多元対数ソボレフ不等式(LSI)と、このアンザッツとの近似との接続を明らかにすることである。
  論文  参考訳（メタデータ） (2024-06-18T20:02:44Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Low-complexity subspace-descent over symmetric positive definite manifold [9.346050098365648]
  対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。 提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
  論文  参考訳（メタデータ） (2023-05-03T11:11:46Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Nonlinear matrix recovery using optimization on the Grassmann manifold [18.655422834567577]
  本研究では,列が部分空間の結合などの非線形構造に従う部分観測された高階クラスタリング行列の復元問題について検討する。 交代極限はクルディカ・ロジャシ性質を用いて一意点に収束することを示す。
  論文  参考訳（メタデータ） (2021-09-13T16:13:13Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLEは、局所的、計量的項と大域的、位相的項の両方で損失関数を最小化し、初期埋め込みを補正する次元推論後処理ステップである。 DIPOLEは、UMAP、t-SNE、Isomapといった一般的な手法よりも多くの一般的なデータセットで優れています。
  論文  参考訳（メタデータ） (2021-06-14T17:19:44Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

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

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