論文の概要: Low Rank Matrix Completion via Robust Alternating Minimization in Nearly
Linear Time
- arxiv url: http://arxiv.org/abs/2302.11068v1
- Date: Tue, 21 Feb 2023 23:49:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-23 16:45:13.748382
- Title: Low Rank Matrix Completion via Robust Alternating Minimization in Nearly
Linear Time
- Title（参考訳）: ほぼ線形時間におけるロバスト交代最小化による低ランク行列補完
- Authors: Yuzhou Gu, Zhao Song, Junze Yin, Lichen Zhang
- Abstract要約: 低階行列補完のためのより効率的で堅牢な交互化フレームワークに向けて大きな一歩を踏み出した。
我々の主な成果は、回帰がほぼ解決されているにもかかわらず、適度な誤りを許容できる頑健な交互最小化アルゴリズムである。
- 参考スコア（独自算出の注目度）: 15.749681835900889
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Given a matrix $M\in \mathbb{R}^{m\times n}$, the low rank matrix completion
problem asks us to find a rank-$k$ approximation of $M$ as $UV^\top$ for $U\in
\mathbb{R}^{m\times k}$ and $V\in \mathbb{R}^{n\times k}$ by only observing a
few entries masked by a binary matrix $P_{\Omega}\in \{0, 1 \}^{m\times n}$. As
a particular instance of the weighted low rank approximation problem, solving
low rank matrix completion is known to be computationally hard even to find an
approximate solution [RSW16]. However, due to its practical importance, many
heuristics have been proposed for this problem. In the seminal work of Jain,
Netrapalli, and Sanghavi [JNS13], they show that the alternating minimization
framework provides provable guarantees for low rank matrix completion problem
whenever $M$ admits an incoherent low rank factorization. Unfortunately, their
algorithm requires solving two exact multiple response regressions per
iteration and their analysis is non-robust as they exploit the structure of the
exact solution.
In this paper, we take a major step towards a more efficient and robust
alternating minimization framework for low rank matrix completion. Our main
result is a robust alternating minimization algorithm that can tolerate
moderate errors even though the regressions are solved approximately.
Consequently, we also significantly improve the running time of [JNS13] from
$\widetilde{O}(mnk^2 )$ to $\widetilde{O}(mnk )$ which is nearly linear in the
problem size, as verifying the low rank approximation takes $O(mnk)$ time. Our
core algorithmic building block is a high accuracy regression solver that
solves the regression in nearly linear time per iteration.
- Abstract（参考訳）: 行列 $m\in \mathbb{r}^{m\times n}$ が与えられると、低ランク行列補完問題(low rank matrix completion problem)は、二進行列 $p_{\omega}\in \{0, 1 \}^{m\times n}$ によってマスクされた数個のエントリを観察することによって、$m$ as $uv^\top$ for $u\in \mathbb{r}^{m\times k}$ と $v\in \mathbb{r}^{n\times k}$ を求める。
重み付き低階近似問題の特定の例として、低階行列の完備化を解くことは、近似解(RSW16)を見つけることさえも、計算的に困難であることが知られている。
しかし、実際的な重要性から、この問題に対する多くのヒューリスティックが提案されている。
Jain, Netrapalli, Sanghavi [JNS13] のセミナルな論文では、交代最小化フレームワークが低階行列完備化問題の証明可能な保証を提供することを示した。
残念なことに、彼らのアルゴリズムは反復ごとに2つの正確な多重応答回帰を解く必要があり、その解析は正確な解の構造を利用するため、損なわれない。
本稿では,低ランク行列補完のためのより効率的でロバストな交互最小化フレームワークに向けて,大きな一歩を踏み出す。
我々の主な結果はロバストな交互最小化アルゴリズムであり、回帰がほぼ解かれていても適度な誤りを許容できる。
その結果、[jns13]の走行時間は、問題サイズでほぼ線形な$\widetilde{o}(mnk^2 )$から$\widetilde{o}(mnk )$に大幅に改善され、低ランク近似の検証には$o(mnk)$がかかる。
我々のアルゴリズム構築ブロックは精度の高い回帰解法であり、1イテレーションあたりのほぼ線形時間で回帰を解く。
関連論文リスト
- Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning [10.690769339903941]
我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
論文 参考訳（メタデータ） (2024-05-09T15:53:43Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Efficient Alternating Minimization with Applications to Weighted Low
Rank Approximation [16.409210914237086]
我々は、最小化の交互化のための効率的で堅牢なフレームワークを開発する。
重み付けされた低階近似の場合、 [LLR16] のランタイムを $n2 k2$ から $n2k$ に改善する。
論文 参考訳（メタデータ） (2023-06-07T05:38:55Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Improved No-Regret Algorithms for Stochastic Shortest Path with Linear
MDP [31.62899359543925]
線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。
我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。
第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
論文 参考訳（メタデータ） (2021-12-18T06:47:31Z) - Nonparametric Matrix Estimation with One-Sided Covariates [5.457150493905064]
mathbbRntimes m$ のデータセット $X をスパシティ $p$ で観測する行列推定のタスクを考える。
我々は,行数が小さすぎる場合に,各行を別々に推定することで,アルゴリズムの精度が向上することを示すアルゴリズムと解析を提供する。
論文 参考訳（メタデータ） (2021-10-26T19:11:45Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。