論文の概要: A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples

• arxiv url: http://arxiv.org/abs/2106.02119v1
• Date: Thu, 3 Jun 2021 20:31:00 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-07 14:53:16.735851
• Title: A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples
• Title（参考訳）: 少数サンプルからのIll-Conditioned Matrix Completionのためのスケーラブルな2次法
• Authors: Christian K\"ummerle, Claudio Mayrink Verdun
• Abstract要約: 低ランク行列補完のための反復アルゴリズムを提案する。 ほとんどサンプルから最大10ドルの条件数で、非常に不調な行列を完遂することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an iterative algorithm for low-rank matrix completion that can be interpreted as an iteratively reweighted least squares (IRLS) algorithm, a saddle-escaping smoothing Newton method or a variable metric proximal gradient method applied to a non-convex rank surrogate. It combines the favorable data-efficiency of previous IRLS approaches with an improved scalability by several orders of magnitude. We establish the first local convergence guarantee from a minimal number of samples for that class of algorithms, showing that the method attains a local quadratic convergence rate. Furthermore, we show that the linear systems to be solved are well-conditioned even for very ill-conditioned ground truth matrices. We provide extensive experiments, indicating that unlike many state-of-the-art approaches, our method is able to complete very ill-conditioned matrices with a condition number of up to $10^{10}$ from few samples, while being competitive in its scalability.
• Abstract（参考訳）: 本稿では,低ランク行列補完のための反復アルゴリズムを提案する。これは反復再重み付き最小二乗(IRLS)アルゴリズム,サドルエスケープスムージングニュートン法,および非凸ランクサロゲートに適用された可変距離近位勾配法と解釈できる。 これは、以前のIRLSアプローチの好ましいデータ効率と、数桁のスケーラビリティの改善を組み合わせたものだ。 アルゴリズムのクラスに対する最小限のサンプル数から、局所収束保証を初めて確立し、この手法が局所二次収束率に達することを示す。 さらに, 未条件の基底真理行列に対しても, 解決すべき線形系が十分に条件付けされていることを示す。 提案手法は,多くの最先端手法と異なり,その拡張性に競争力を持ちながら,少数のサンプルから最大10〜10ドルの条件数で,非常に条件の悪い行列を完遂できることを示す。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares [0.8702432681310401]
  線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。 IRLS法は,低/複合状態の計測に好適であることを示す。
  論文  参考訳（メタデータ） (2023-06-08T06:35:47Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• An adaptive Hessian approximated stochastic gradient MCMC method [12.93317525451798]
  後方からのサンプリング中に局所的幾何情報を組み込む適応型ヘッセン近似勾配MCMC法を提案する。 我々は,ネットワークの空間性を高めるために,等級に基づく重み付け法を採用する。
  論文  参考訳（メタデータ） (2020-10-03T16:22:15Z)
• Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method [0.0]
  低ランク行列に対する反復アルゴリズムを提案する。 多くの最先端の手法とは異なり、我々の手法は少数のサンプルから最大10ドルの条件数で非常に不調な条件を満たすことができることを示す数値実験で示している。
  論文  参考訳（メタデータ） (2020-09-07T06:51:20Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。 低ランク行列の個数の観点から,ScaledGDが最良となることを示す。 我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
  論文  参考訳（メタデータ） (2020-05-18T17:17:16Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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