論文の概要: Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees
- arxiv url: http://arxiv.org/abs/2410.06376v1
- Date: Tue, 8 Oct 2024 21:19:22 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-01 06:09:19.642404
- Title: Riemannian Optimization for Non-convex Euclidean Distance Geometry with Global Recovery Guarantees
- Title（参考訳）: グローバルリカバリ保証付き非凸ユークリッド距離幾何学のリーマン最適化
- Authors: Chandler Smith, HanQin Cai, Abiy Tasissa,
- Abstract要約: ユークリッド距離幾何学問題を解くために2つのアルゴリズムが提案されている。
第一のアルゴリズムは真の解に線形に収束する。
第2のアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
- 参考スコア（独自算出の注目度）: 6.422262171968397
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of determining the configuration of points from partial distance information, known as the Euclidean Distance Geometry (EDG) problem, is fundamental to many tasks in the applied sciences. In this paper, we propose two algorithms grounded in the Riemannian optimization framework to address the EDG problem. Our approach formulates the problem as a low-rank matrix completion task over the Gram matrix, using partial measurements represented as expansion coefficients of the Gram matrix in a non-orthogonal basis. For the first algorithm, under a uniform sampling with replacement model for the observed distance entries, we demonstrate that, with high probability, a Riemannian gradient-like algorithm on the manifold of rank-$r$ matrices converges linearly to the true solution, given initialization via a one-step hard thresholding. This holds provided the number of samples, $m$, satisfies $m \geq \mathcal{O}(n^{7/4}r^2 \log(n))$. With a more refined initialization, achieved through resampled Riemannian gradient-like descent, we further improve this bound to $m \geq \mathcal{O}(nr^2 \log(n))$. Our analysis for the first algorithm leverages a non-self-adjoint operator and depends on deriving eigenvalue bounds for an inner product matrix of restricted basis matrices, leveraging sparsity properties for tighter guarantees than previously established. The second algorithm introduces a self-adjoint surrogate for the sampling operator. This algorithm demonstrates strong numerical performance on both synthetic and real data. Furthermore, we show that optimizing over manifolds of higher-than-rank-$r$ matrices yields superior numerical results, consistent with recent literature on overparameterization in the EDG problem.
- Abstract（参考訳）: ユークリッド距離幾何学(Euclidean Distance Geometry, EDG)問題として知られる部分距離情報から点の設定を決定する問題は、応用科学における多くの課題に不可欠である。
本稿では,EDG問題に対処するために,リーマン最適化フレームワークを基盤とした2つのアルゴリズムを提案する。
本手法は,非直交的にグラム行列の拡張係数として表される部分的な測定値を用いて,グラム行列上の低ランク行列完備化タスクとして問題を定式化する。
最初のアルゴリズムでは、観測された距離エントリの置換モデルで一様サンプリングを行い、高い確率で階数=r$行列の多様体上のリーマン勾配のようなアルゴリズムが真の解に線形に収束し、1ステップのハードしきい値による初期化が与えられることを示した。
サンプルの数は$m$で、$m \geq \mathcal{O}(n^{7/4}r^2 \log(n))$を満たす。
より洗練された初期化は、再サンプリングされたリーマン勾配のような降下によって達成され、さらに$m \geq \mathcal{O}(nr^2 \log(n))$ に制限される。
最初のアルゴリズムの解析は非自己随伴作用素を利用し、制限された基底行列の内積行列に対して固有値境界を導出することに依存し、より厳密な保証のために空間性特性を活用する。
第2のアルゴリズムはサンプリング演算子に対する自己共役サロゲートを導入する。
このアルゴリズムは、合成データと実データの両方で強い数値性能を示す。
さらに,高次階数=$r$行列の多様体上での最適化は,EDG問題における過パラメータ化に関する最近の文献と整合して,優れた数値結果をもたらすことを示す。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - Low-complexity subspace-descent over symmetric positive definite
manifold [9.346050098365648]
対称正定値多様体(SPD)上の関数の最小化のための低複素性アルゴリズムを開発する。
提案手法は、慎重に選択された部分空間を利用して、更新をイテレートのコレスキー因子とスパース行列の積として記述することができる。
論文 参考訳（メタデータ） (2023-05-03T11:11:46Z) - Rank-1 Matrix Completion with Gradient Descent and Small Random
Initialization [15.127728811011245]
我々は,GDの暗黙的正規化が分析において重要な役割を担っていることを示す。
我々は、手頃な分析において暗黙の正規化GDが重要な役割を担っていることを観察する。
論文 参考訳（メタデータ） (2022-12-19T12:05:37Z) - 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) - Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via
GDPA Linearization [59.87663954467815]
アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。
本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。
実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
論文 参考訳（メタデータ） (2021-09-10T07:01:15Z) - Near-Optimal Algorithms for Linear Algebra in the Current Matrix
Multiplication Time [46.31710224483631]
既存の定数係数近似のスケッチ次元における対数的要素について、Nelson and Nguyen (FOCS, 2013) の主な開問題を回避する方法を示す。
私たちが使用している重要なテクニックは、不確実性原理と抽出子に基づくIndykの明示的なマッピングです。
ランク計算と列の線形独立部分集合の探索という基本的な問題に対して、我々のアルゴリズムはCheung, Kwok, Lau (JACM, 2013)を改良し、それぞれ定数係数と$log(n)$-factorの範囲内で最適である。
論文 参考訳（メタデータ） (2021-07-16T19:34:10Z) - On the Efficient Implementation of the Matrix Exponentiated Gradient
Algorithm for Low-Rank Matrix Optimization [26.858608065417663]
スペクトル上の凸最適化は、機械学習、信号処理、統計学に重要な応用がある。
低ランク行列による最適化に適したMEGの効率的な実装を提案し、各イテレーションで単一の低ランクSVDのみを使用する。
また,本手法の正しい収束のための効率よく計算可能な証明書も提供する。
論文 参考訳（メタデータ） (2020-12-18T19:14:51Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳（メタデータ） (2020-02-21T17:45:32Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。