論文の概要: RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees

• arxiv url: http://arxiv.org/abs/2505.12919v1
• Date: Mon, 19 May 2025 09:58:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 14:57:11.528072
• Title: RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees
• Title（参考訳）: RGNMR:理論保証付きロバスト行列完備化のためのガウスニュートン法
• Authors: Eilon Vaknin Laufer, Boaz Nadler,
• Abstract要約: $textttRGNMR$は単純な因数分解に基づく反復アルゴリズムであり、ガウス・ニュートン線形化と外れ値と思われるエントリの除去を組み合わせたものである。 既存の RMC 法よりも $textttRGNMR$ の方が優れていること,特に少数の観測項目を扱えることを,いくつかのシミュレーションで示している。
• 参考スコア（独自算出の注目度）: 4.433874763859054
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recovering a low rank matrix from a subset of its entries, some of which may be corrupted, is known as the robust matrix completion (RMC) problem. Existing RMC methods have several limitations: they require a relatively large number of observed entries; they may fail under overparametrization, when their assumed rank is higher than the correct one; and many of them fail to recover even mildly ill-conditioned matrices. In this paper we propose a novel RMC method, denoted $\texttt{RGNMR}$, which overcomes these limitations. $\texttt{RGNMR}$ is a simple factorization-based iterative algorithm, which combines a Gauss-Newton linearization with removal of entries suspected to be outliers. On the theoretical front, we prove that under suitable assumptions, $\texttt{RGNMR}$ is guaranteed exact recovery of the underlying low rank matrix. Our theoretical results improve upon the best currently known for factorization-based methods. On the empirical front, we show via several simulations the advantages of $\texttt{RGNMR}$ over existing RMC methods, and in particular its ability to handle a small number of observed entries, overparameterization of the rank and ill-conditioned matrices.
• Abstract（参考訳）: 低階行列をその部分集合から復元し、そのうちのいくつかは破壊されうるが、ロバスト行列完備化(RMC)問題として知られている。 既存のRCC法にはいくつかの制限がある: 比較的多くの観測項目を必要とする; オーバーパラメトリゼーションの下では、仮定されたランクが正しいものよりも高いときに失敗する; それらの多くは、軽度に不飽和な行列を回復するのに失敗する。 本稿では,これらの制約を克服する新しいRCC法である$\texttt{RGNMR}$を提案する。 $\texttt{RGNMR}$ は単純な分解に基づく反復アルゴリズムであり、ガウス・ニュートン線形化と外れ値と思われるエントリの除去を組み合わせたものである。 理論面では、適切な仮定の下では、$\texttt{RGNMR}$ は下層の低階行列の正確な回復を保証する。 我々の理論的結果は、因子化に基づく手法で知られている最もよく知られた方法により改善される。 経験的な面では、既存のRCC法よりも$\texttt{RGNMR}$の利点、特に少数の観測項目、ランクの過度パラメータ化、および不条件行列を扱う能力について、いくつかのシミュレーションを通して示す。

関連論文リスト

• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• GNMR: A provable one-line algorithm for low rank matrix recovery [7.615353798870043]
  低位行列回復のための極めて単純な反復アルゴリズム GNMR を提案する。 我々は,行列センシングと行列完了設定の両方において,GNMRの回復保証を導出する。
  論文  参考訳（メタデータ） (2021-06-24T11:57:48Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。 この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。 RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。 本稿では、近年のローワークの動機付けについて述べる。
  論文  参考訳（メタデータ） (2020-08-18T04:46:22Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  そこで我々は,適応的かつ音質の高い"核フロベニウスノルム"と呼ばれる新しい非スケーラブルな低ランク正規化器を提案する。 特異値の計算をバイパスし、アルゴリズムによる高速な最適化を可能にする。 既存の行列学習手法では最速でありながら、最先端の回復性能が得られる。
  論文  参考訳（メタデータ） (2020-08-14T18:47:58Z)
• Robust Compressed Sensing using Generative Models [98.64228459705859]
  本稿では,Median-of-Means (MOM) にヒントを得たアルゴリズムを提案する。 我々のアルゴリズムは、外れ値が存在する場合でも、重み付きデータの回復を保証する。
  論文  参考訳（メタデータ） (2020-06-16T19:07:41Z)
• Rank $2r$ iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries [4.230158563771147]
  低階行列補完のための新しい,単純で,計算効率のよい反復法を提案する。 我々のアルゴリズムは、R2RILS(R2RILS for rank $2r$peterative least squares)と呼ばれ、メモリ要件が低い。
  論文  参考訳（メタデータ） (2020-02-05T16:20:58Z)

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

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