論文の概要: Solving the Robust Matrix Completion Problem via a System of Nonlinear
Equations
- arxiv url: http://arxiv.org/abs/2003.10992v1
- Date: Tue, 24 Mar 2020 17:28:15 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-20 08:22:21.967607
- Title: Solving the Robust Matrix Completion Problem via a System of Nonlinear
Equations
- Title（参考訳）: 非線形方程式系によるロバスト行列完全問題の解法
- Authors: Yunfeng Cai and Ping Li
- Abstract要約: 低階行列 $L_*$ とスパース行列 $S_*$ をそれらの和 $M=L_*+S_*inmathbbRmtimes n$ の不完全観測から回復することを目的としたロバスト行列完備化の問題を考える。
このアルゴリズムは並列性が高く、大規模な問題に適している。
数値シミュレーションにより、単純な手法は期待通りに動作し、最先端の手法に匹敵することを示した。
- 参考スコア（独自算出の注目度）: 28.83358353043287
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of robust matrix completion, which aims to recover a
low rank matrix $L_*$ and a sparse matrix $S_*$ from incomplete observations of
their sum $M=L_*+S_*\in\mathbb{R}^{m\times n}$. Algorithmically, the robust
matrix completion problem is transformed into a problem of solving a system of
nonlinear equations, and the alternative direction method is then used to solve
the nonlinear equations. In addition, the algorithm is highly parallelizable
and suitable for large scale problems. Theoretically, we characterize the
sufficient conditions for when $L_*$ can be approximated by a low rank
approximation of the observed $M_*$. And under proper assumptions, it is shown
that the algorithm converges to the true solution linearly. Numerical
simulations show that the simple method works as expected and is comparable
with state-of-the-art methods.
- Abstract（参考訳）: 低ランク行列 $l_*$ とスパース行列 $s_*$ を、それらの和 $m=l_*+s_*\in\mathbb{r}^{m\times n}$ の不完全な観測から回収することを目的としたロバスト行列完全性の問題を考える。
アルゴリズム的には、ロバスト行列完備問題は非線形方程式の系を解く問題に変換され、別の方向法を用いて非線形方程式を解く。
さらに、アルゴリズムは並列化しやすく、大規模問題にも適している。
理論的には、$l_*$ が観測された $m_*$ の低位近似によって近似できる場合の十分条件を特徴付ける。
適切な仮定の下では、アルゴリズムが真の解に線形収束することを示す。
数値シミュレーションにより、単純な手法は期待通りに動作し、最先端の手法に匹敵することを示した。
関連論文リスト
- An approximation of the $S$ matrix for solving the Marchenko equation [0.0]
ここでは、有理関数の和として定式化された運動量$q$に対する$S$-行列依存の新たな近似と、truncated Sinc 級数を示す。
このアプローチにより、特定の解像度で$S$行列をポイントワイズで決定することができ、共鳴挙動などの重要な特徴を高精度に捉えることができる。
論文 参考訳（メタデータ） (2024-10-27T11:06:28Z) - Fine-grained Analysis and Faster Algorithms for Iteratively Solving Linear Systems [9.30306458153248]
我々は、スペクトルテール条件数である$kappa_ell$を、システムを表す行列の最小特異値と$ell$2の比として定義する。
結果のいくつかの意味と$kappa_ell$の使用は、Conjugateメソッドのきめ細かい解析を直接改善することを含んでいる。
論文 参考訳（メタデータ） (2024-05-09T14:56:49Z) - Orthogonally weighted $\ell_{2,1}$ regularization for rank-aware joint
sparse recovery: algorithm and analysis [7.7001263654719985]
我々は,新たな正規化法である $ell_2,1$$(mathitowell_2,1$) を用いて,結合スパース回復問題の効率的な解法を提案し,解析する。
この手法は特徴抽出、行列列選択、辞書学習に応用され、一般的な$ell_2,1$正規化とは異なる。
提案手法のランク認識の証明を行い,提案手法の最適化問題に対する解が存在することを証明し,収束を解析した効率的な解法を開発した。
論文 参考訳（メタデータ） (2023-11-21T01:52:15Z) - A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳（メタデータ） (2023-06-06T22:35:16Z) - Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
アルゴリズムの複雑さは$O(rm polylog(n/epsilon))$であり、これは次元$n$の最適古典アルゴリズムよりも指数関数的に改善される。
我々のアルゴリズムは指数関数的にQNSEの解を加速し、あらゆる非線形問題に適用できる。
論文 参考訳（メタデータ） (2021-12-03T00:27:16Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳（メタデータ） (2021-06-27T17:25:24Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z) - 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 nonlinear dynamical systems from a single trajectory [102.60042167341956]
我々は、$x_t+1=sigma(Thetastarx_t)+varepsilon_t$という形の非線形力学系を学ぶアルゴリズムを導入する。
最適なサンプル複雑性と線形ランニング時間を持つ単一軌道から重み行列$Thetastar$を復元するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-30T10:42:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。