論文の概要: Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity
- arxiv url: http://arxiv.org/abs/2408.13276v2
- Date: Tue, 10 Sep 2024 18:44:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-12 20:12:08.930583
- Title: Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity
- Title（参考訳）: 非凸マトリクスセンシング:サンプル複雑度における2次階乗障壁を破る
- Authors: Dominik Stöger, Yizhe Zhu,
- Abstract要約: いくつかの測定値から低ランク2次凸行列を再構成する問題について検討した。
スペクトル特異性を持つ分解勾配は標本数と真理に収束することを示す。
- 参考スコア（独自算出の注目度）: 11.412228884390784
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: For the problem of reconstructing a low-rank matrix from a few linear measurements, two classes of algorithms have been widely studied in the literature: convex approaches based on nuclear norm minimization, and non-convex approaches that use factorized gradient descent. Under certain statistical model assumptions, it is known that nuclear norm minimization recovers the ground truth as soon as the number of samples scales linearly with the number of degrees of freedom of the ground-truth. In contrast, while non-convex approaches are computationally less expensive, existing recovery guarantees assume that the number of samples scales at least quadratically with the rank $r$ of the ground-truth matrix. In this paper, we close this gap by showing that the non-convex approaches can be as efficient as nuclear norm minimization in terms of sample complexity. Namely, we consider the problem of reconstructing a positive semidefinite matrix from a few Gaussian measurements. We show that factorized gradient descent with spectral initialization converges to the ground truth with a linear rate as soon as the number of samples scales with $ \Omega (rd\kappa^2)$, where $d$ is the dimension, and $\kappa$ is the condition number of the ground truth matrix. This improves the previous rank-dependence in the sample complexity of non-convex matrix factorization from quadratic to linear. Our proof relies on a probabilistic decoupling argument, where we show that the gradient descent iterates are only weakly dependent on the individual entries of the measurement matrices. We expect that our proof technique is of independent interest for other non-convex problems.
- Abstract（参考訳）: 少数の線形測定から低ランク行列を再構成する問題に対して、核ノルム最小化に基づく凸法と分解勾配勾配を用いた非凸法という2種類のアルゴリズムが文献で広く研究されている。
特定の統計モデルでは、核ノルムの最小化は、サンプルの数が基底真実の自由度数とともに線形にスケールするとすぐに基底真実を回復することが知られている。
対照的に、非凸アプローチは計算コストが低いが、既存のリカバリ保証では、サンプルの数は少なくとも2次スケールで、基底トラス行列の階数$r$と仮定している。
本稿では,非凸法が試料の複雑さの観点から核ノルム最小化に匹敵する効率を示すことにより,このギャップを埋める。
すなわち、いくつかのガウス測度から正の半定値行列を再構成する問題を考察する。
スペクトル初期化による分解勾配勾配は、サンプルの数が$Omega (rd\kappa^2)$でスケールするとすぐに基底真理に収束し、$d$は次元、$\kappa$は基底真理行列の条件数であることを示す。
これにより、2次から線形への非凸行列分解のサンプル複雑性における以前の階数依存性が向上する。
我々の証明は確率的疎結合論に依拠し、勾配降下反復が測定行列の個々のエントリに弱依存していることを示す。
我々は、我々の証明手法が他の非凸問題に対して独立した関心を持つことを期待している。
関連論文リスト
- A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。
提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
論文 参考訳（メタデータ） (2024-09-07T06:37:23Z) - 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) - Recovering Simultaneously Structured Data via Non-Convex Iteratively
Reweighted Least Squares [0.8702432681310401]
線形観測から多種多様低次元構造に固執するデータを復元する新しいアルゴリズムを提案する。
IRLS法は,低/複合状態の計測に好適であることを示す。
論文 参考訳（メタデータ） (2023-06-08T06:35:47Z) - Distributional Hardness Against Preconditioned Lasso via Erasure-Robust
Designs [22.41443027099101]
標準スパースランダム設計は, 逆測定消去に対して高い確率で頑健であることを示す。
消去下での任意のスパース信号の部分的回復性が圧縮センシングで研究されたのはこれが初めてである。
論文 参考訳（メタデータ） (2022-03-05T22:16:05Z) - Stochastic regularized majorization-minimization with weakly convex and
multi-convex surrogates [0.0]
提案アルゴリズムの最初の最適性ギャップは,非テンソル依存データ設定下での様々な手法の期待損失率で減衰することを示す。
非テンション依存データ設定の下で, 各種手法の収束点を求める。
論文 参考訳（メタデータ） (2022-01-05T15:17:35Z) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric
Low-Rank Matrix Sensing [36.96922859748537]
低ランク行列推定は、科学と工学のさまざまなアプリケーションで中心的な役割を果たします。
既存のアプローチは、2つの行列因子のスケールのバランスをとるために計量正規化項を加えることに頼っている。
本論文では,低ランク行列の線形測定値の少ない値から回復する性能の理論的正当化について述べる。
論文 参考訳（メタデータ） (2021-01-13T15:03:52Z) - Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。
我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-09-30T19:10:32Z) - Learning Mixtures of Low-Rank Models [89.39877968115833]
低ランクモデルの計算混合を学習する問題について検討する。
ほぼ最適サンプルを用いて未知の行列を復元することが保証されるアルゴリズムを開発する。
さらに,提案アルゴリズムはランダムノイズに対して確実に安定である。
論文 参考訳（メタデータ） (2020-09-23T17:53:48Z) - Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled
Gradient Descent [34.0533596121548]
低ランク行列推定は凸問題を収束させ、信号処理、機械学習、画像科学に多くの応用を見出す。
低ランク行列の個数の観点から,ScaledGDが最良となることを示す。
我々の分析は、低ランク勾配降下に類似した一般損失にも適用できる。
論文 参考訳（メタデータ） (2020-05-18T17:17:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。