論文の概要: 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_*$ の低位近似によって近似できる場合の十分条件を特徴付ける。
適切な仮定の下では、アルゴリズムが真の解に線形収束することを示す。
数値シミュレーションにより、単純な手法は期待通りに動作し、最先端の手法に匹敵することを示した。
関連論文リスト
- 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.774924046750588]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
最大$mathcalO left( (m + n) textnnz (A) kappa (mathcalM) L cdot textpolylog left(m, n, kappa)$ elementary gates and $mathcalO left() を用いて、$m$制約と$n$変数を含む線形最適化問題の正確な解を得る。
論文 参考訳(メタデータ) (2023-11-07T13:26:20Z) - One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。
合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
論文 参考訳(メタデータ) (2023-06-06T22:35:16Z) - Optimal Low-Rank Matrix Completion: Semidefinite Relaxations and
Eigenvector Disjunctions [6.537257913467247]
低ランク行列の完備化は、与えられた観測セットをできるだけ正確に回復する最小の複雑さの行列からなる。
新たな凸緩和は、既存の方法に比べて最大値を大幅に下げる。
論文 参考訳(メタデータ) (2023-05-20T22:04:34Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - 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) - 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) - Optimal Exact Matrix Completion Under new Parametrization [0.0]
適応サンプリング法を用いて、$m倍 n$ の階数 $r$ の行列の正確な完備化の問題を研究した。
対象行列を正確に復元する行列補完アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-02-06T18:31:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。