論文の概要: On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure

• arxiv url: http://arxiv.org/abs/2105.01874v1
• Date: Wed, 5 May 2021 05:34:32 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-06 20:04:04.647658
• Title: On the Optimality of Nuclear-norm-based Matrix Completion for Problems with Smooth Non-linear Structure
• Title（参考訳）: 滑らかな非線形構造を持つ問題に対する核ノルム系行列完成の最適性について
• Authors: Yunhua Xiang, Tianyu Zhang, Xu Wang, Ali Shojaie, Noah Simon
• Abstract要約: 行列完備化は、下層の行列に低次元線型構造を仮定する理由がない多くの問題において広く有効であることが証明されている。 原子核のペナライゼーションは、観測がランダムに完全に欠けている場合にこれらの行列を回復するのに有効であることを示す。
• 参考スコア（独自算出の注目度）: 19.069068837749885
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Originally developed for imputing missing entries in low rank, or approximately low rank matrices, matrix completion has proven widely effective in many problems where there is no reason to assume low-dimensional linear structure in the underlying matrix, as would be imposed by rank constraints. In this manuscript, we build some theoretical intuition for this behavior. We consider matrices which are not necessarily low-rank, but lie in a low-dimensional non-linear manifold. We show that nuclear-norm penalization is still effective for recovering these matrices when observations are missing completely at random. In particular, we give upper bounds on the rate of convergence as a function of the number of rows, columns, and observed entries in the matrix, as well as the smoothness and dimension of the non-linear embedding. We additionally give a minimax lower bound: This lower bound agrees with our upper bound (up to a logarithmic factor), which shows that nuclear-norm penalization is (up to log terms) minimax rate optimal for these problems.
• Abstract（参考訳）: もともとは、低階、あるいは概略低階行列の欠落エントリを暗示するために開発された行列完全性は、ランク制約によって課されるような基底行列の低次元線型構造を仮定する理由がない多くの問題において広く有効であることが証明されている。 本書では,この行動に関する理論的直観を定めている。 必ずしもローランクではなく、低次元の非線形多様体に属する行列を考える。 核-ノルムペナリゼーションは、観測が完全にランダムに欠落している場合にも、これらの行列を回復するのに有効であることが示されている。 特に、行列内の行数、列数、および観察された成分の関数として収束率の上限を与えるとともに、非線型埋め込みの滑らかさと次元を与える。 さらに、ミニマックス下限を与える: この下限は、我々の上限(対数係数まで)に一致し、核-ノルムペナリゼーションが(対数項まで)これらの問題に最適なミニマックスレートであることを示している。

関連論文リスト

• Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity [11.412228884390784]
  いくつかの測定値から低ランク2次凸行列を再構成する問題について検討した。 スペクトル特異性を持つ分解勾配は標本数と真理に収束することを示す。
  論文  参考訳（メタデータ） (2024-08-20T14:09:28Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。 重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。 我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
  論文  参考訳（メタデータ） (2024-05-23T12:26:25Z)
• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  この研究は、ディープ線形ネットワークにおけるヘッセン解の最小トレースの帰納バイアスを理解するための第一歩となる。 測定値の標準等尺性(RIP)が1より大きいすべての深さについて、ヘッセンのトレースを最小化することは、対応する終端行列パラメータのシャッテン 1-ノルムを最小化するのとほぼ同値であることを示す。
  論文  参考訳（メタデータ） (2023-06-22T23:14:57Z)
• Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and Eigenvector Disjunctions [6.537257913467247]
  低ランク行列の完備化は、与えられた観測セットをできるだけ正確に回復する最小の複雑さの行列からなる。 新たな凸緩和は、既存の方法に比べて最大値を大幅に下げる。
  論文  参考訳（メタデータ） (2023-05-20T22:04:34Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  本稿では,初期監視情報を同時に拡張し,識別親和性行列を構築することのできる,新しい半教師付きサブスペースクラスタリング手法を提案する。 6つの一般的なベンチマークデータセットの総合的な実験結果から,本手法が最先端手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-05-21T01:47:17Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Robust Low-rank Matrix Completion via an Alternating Manifold Proximal Gradient Continuation Method [47.80060761046752]
  ロバスト低ランク行列補完(RMC)は、コンピュータビジョン、信号処理、機械学習アプリケーションのために広く研究されている。 この問題は、部分的に観察された行列を低ランク行列とスパース行列の重ね合わせに分解することを目的とした。 RMCに取り組むために広く用いられるアプローチは、低ランク行列の核ノルム(低ランク性を促進するために)とスパース行列のl1ノルム(空間性を促進するために)を最小化する凸定式化を考えることである。 本稿では、近年のローワークの動機付けについて述べる。
  論文  参考訳（メタデータ） (2020-08-18T04:46:22Z)
• Compressed sensing of low-rank plus sparse matrices [3.8073142980733]
  この写本は、ランクラパース行列と$sスパース行列の和として表現できる$mtimes n$が計算的に抽出可能な方法で復元可能であることを示す同様の保証を開発する。 その結果, 合成問題, 動的地上/静電分離, マルチスペクトルイメージング, ロバストPCAが得られた。
  論文  参考訳（メタデータ） (2020-07-18T15:36:11Z)
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent [34.0533596121548]
  低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。 低ランク行列の個数の観点から,ScaledGDが最良となることを示す。 我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
  論文  参考訳（メタデータ） (2020-05-18T17:17:16Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。 未知行列の最適低ランク近似を回復するための相対上界を導出する。
  論文  参考訳（メタデータ） (2015-04-26T13:12:16Z)

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

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