論文の概要: Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent

• arxiv url: http://arxiv.org/abs/2504.19530v1
• Date: Mon, 28 Apr 2025 07:13:23 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-02 19:15:54.348025
• Title: Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent
• Title（参考訳）: ユークリッド距離行列の非対称射影勾配線による完備化
• Authors: Yicheng Li, Xinghua Sun,
• Abstract要約: 本稿では,非対称励起勾配 (APGD) と呼ばれるBurer-Monteiro因子化に基づく勾配型アルゴリズムを提案し,解析する。
• 参考スコア（独自算出の注目度）: 13.27202712518471
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper proposes and analyzes a gradient-type algorithm based on Burer-Monteiro factorization, called the Asymmetric Projected Gradient Descent (APGD), for reconstructing the point set configuration from partial Euclidean distance measurements, known as the Euclidean Distance Matrix Completion (EDMC) problem. By paralleling the incoherence matrix completion framework, we show for the first time that global convergence guarantee with exact recovery of this routine can be established given $\mathcal{O}(\mu^2 r^3 \kappa^2 n \log n)$ Bernoulli random observations without any sample splitting. Unlike leveraging the tangent space Restricted Isometry Property (RIP) and local curvature of the low-rank embedding manifold in some very recent works, our proof provides new upper bounds to replace the random graph lemma under EDMC setting. The APGD works surprisingly well and numerical experiments demonstrate exact linear convergence behavior in rich-sample regions yet deteriorates fast when compared with the performance obtained by optimizing the s-stress function, i.e., the standard but unexplained non-convex approach for EDMC, if the sample size is limited. While virtually matching our theoretical prediction, this unusual phenomenon might indicate that: (i) the power of implicit regularization is weakened when specified in the APGD case; (ii) the stabilization of such new gradient direction requires substantially more samples than the information-theoretic limit would suggest.
• Abstract（参考訳）: 本稿では, 部分ユークリッド距離測定(Euclidean Distance Matrix Completion, EDMC)問題から, 点集合構成を再構成するための非対称射影勾配 Descent (APGD) と呼ばれるBurer-Monteiro因子分解に基づく勾配型アルゴリズムを提案し, 解析する。 非コヒーレンス行列完備化フレームワークを並列化することにより、このルーチンの正確な回復を伴う大域収束保証が、サンプル分割を伴わずに$\mathcal{O}(\mu^2 r^3 \kappa^2 n \log n)$ Bernoulliランダムな観測を得られることを示す。 いくつかの非常に最近の研究で、接空間 Restricted Isometry Property (RIP) とローランク埋め込み多様体の局所曲率を利用するのとは異なり、我々の証明は、EDMC設定の下でランダムグラフ補題を置き換えるための新しい上限を与える。 APGDは驚くほどうまく機能し、数値実験によりサンプルサイズが制限された場合、s-stress関数、すなわち標準だが説明できないEDMCの非凸アプローチを最適化した性能と比較すると、リッチサンプル領域における正確な線形収束挙動は急速に低下する。 理論的な予測とほぼ一致するが、この異常な現象は次のことを示しているかもしれない。 i) APGDの場合は,暗黙の正則化の力が低下する。 (II) このような新しい勾配方向の安定化には, 情報理論の限界が示唆するよりも, はるかに多くのサンプルが必要である。

関連論文リスト

• Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization [7.114174944371803]
  ユークリッド距離情報点対を埋め込む適切な点を見つける問題は、コアタスクとサブマシン学習の問題の両方として生じる。 本稿では,最小限のサンプル数を考えると,この問題を解決することを目的とする。
  論文  参考訳（メタデータ） (2024-10-22T13:02:12Z)
• Asymptotics of Stochastic Gradient Descent with Dropout Regularization in Linear Models [8.555650549124818]
  本稿では,線形回帰における勾配勾配勾配(SGD)のオンライン推論とドロップアウト正規化を反復する理論を提案する。 十分に大きなサンプルの場合,ASGDの投棄による信頼区間は,名目カバレッジの確率をほぼ達成している。
  論文  参考訳（メタデータ） (2024-09-11T17:28:38Z)
• Intrinsic Bayesian Cramér-Rao Bound with an Application to Covariance Matrix Estimation [49.67011673289242]
  本稿では, 推定パラメータが滑らかな多様体内にある推定問題に対して, 新たな性能境界を提案する。 これはパラメータ多様体の幾何学と推定誤差測度の本質的な概念を誘導する。
  論文  参考訳（メタデータ） (2023-11-08T15:17:13Z)
• Curvature-Independent Last-Iterate Convergence for Games on Riemannian Manifolds [77.4346324549323]
  本研究では, 多様体の曲率に依存しないステップサイズが, 曲率非依存かつ直線的最終点収束率を達成することを示す。 我々の知る限りでは、曲率非依存率や/または最終点収束の可能性はこれまでに検討されていない。
  論文  参考訳（メタデータ） (2023-06-29T01:20:44Z)
• Orthogonal Matrix Retrieval with Spatial Consensus for 3D Unknown-View Tomography [58.60249163402822]
  未知視トモグラフィ(UVT)は、未知のランダムな向きで2次元投影から3次元密度マップを再構成する。 提案したOMRはより堅牢で、従来の最先端のOMRアプローチよりも大幅に性能が向上している。
  論文  参考訳（メタデータ） (2022-07-06T21:40:59Z)
• Nonconvex Stochastic Scaled-Gradient Descent and Generalized Eigenvector Problems [98.34292831923335]
  オンライン相関解析の問題から,emphStochastic Scaled-Gradient Descent (SSD)アルゴリズムを提案する。 我々はこれらのアイデアをオンライン相関解析に適用し、局所収束率を正規性に比例した最適な1時間スケールのアルゴリズムを初めて導いた。
  論文  参考訳（メタデータ） (2021-12-29T18:46:52Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• Exact Linear Convergence Rate Analysis for Low-Rank Symmetric Matrix Completion via Gradient Descent [22.851500417035947]
  因数分解に基づく勾配降下は、因数分解行列の完備化を解くためのスケーラブルで効率的なアルゴリズムである。 勾配勾配降下は, 地球自然問題の解を推定するために, 高速収束を楽しむことを示す。
  論文  参考訳（メタデータ） (2021-02-04T03:41:54Z)
• Sparse Representations of Positive Functions via First and Second-Order Pseudo-Mirror Descent [15.340540198612823]
  推定器の範囲が非負である必要がある場合、予測されるリスク問題を考察する。 Emphpseudo-gradientsを用いた近似ミラーの1階および2階の変種を開発した。 実験は、実際に不均一なプロセス強度推定に好適な性能を示す。
  論文  参考訳（メタデータ） (2020-11-13T21:54:28Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  我々は高次元単一インデックスモデルのための正規化自由アルゴリズムを設計する。 暗黙正則化現象の理論的保証を提供する。
  論文  参考訳（メタデータ） (2020-07-16T13:27:47Z)

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

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