論文の概要: Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
- arxiv url: http://arxiv.org/abs/2405.05865v1
- Date: Thu, 9 May 2024 15:53:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-10 12:53:04.697485
- Title: Faster Linear Systems and Matrix Norm Approximation via Multi-level Sketched Preconditioning
- Title（参考訳）: マルチレベルスケッチプレコンディショニングによる高速線形系と行列ノルム近似
- Authors: Michał Dereziński, Christopher Musco, Jiaming Yang,
- Abstract要約: 我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
我々は、我々の手法の収束が自然平均条件数$A$に依存することを証明し、Nystr"om近似のランクとして改善する。
- 参考スコア（独自算出の注目度）: 10.690769339903941
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a new class of preconditioned iterative methods for solving linear systems of the form $Ax = b$. Our methods are based on constructing a low-rank Nystr\"om approximation to $A$ using sparse random sketching. This approximation is used to construct a preconditioner, which itself is inverted quickly using additional levels of random sketching and preconditioning. We prove that the convergence of our methods depends on a natural average condition number of $A$, which improves as the rank of the Nystr\"om approximation increases. Concretely, this allows us to obtain faster runtimes for a number of fundamental linear algebraic problems: 1. We show how to solve any $n\times n$ linear system that is well-conditioned except for $k$ outlying large singular values in $\tilde{O}(n^{2.065} + k^\omega)$ time, improving on a recent result of [Derezi\'nski, Yang, STOC 2024] for all $k \gtrsim n^{0.78}$. 2. We give the first $\tilde{O}(n^2 + {d_\lambda}^{\omega}$) time algorithm for solving a regularized linear system $(A + \lambda I)x = b$, where $A$ is positive semidefinite with effective dimension $d_\lambda$. This problem arises in applications like Gaussian process regression. 3. We give faster algorithms for approximating Schatten $p$-norms and other matrix norms. For example, for the Schatten 1 (nuclear) norm, we give an algorithm that runs in $\tilde{O}(n^{2.11})$ time, improving on an $\tilde{O}(n^{2.18})$ method of [Musco et al., ITCS 2018]. Interestingly, previous state-of-the-art algorithms for most of the problems above relied on stochastic iterative methods, like stochastic coordinate and gradient descent. Our work takes a completely different approach, instead leveraging tools from matrix sketching.
- Abstract（参考訳）: 我々は、$Ax = b$という形式の線形系を解くための、新しい条件付き反復法のクラスを示す。
提案手法は,低ランクなNystr\"om近似をスパースランダムスケッチを用いて$A$に構築することに基づいている。
この近似はプリコンディショナーを構築するのに使われ、ランダムスケッチとプレコンディショニングの付加レベルを使用して、自身は迅速に逆転される。
我々の手法の収束は、Nystr\"om近似のランクが増加するにつれて改善される自然平均条件数$A$に依存することを証明している。
具体的には、多くの基本的な線形代数的問題に対してより高速なランタイムを得ることができる: 1) 任意の$n\times n$線型系を、$k$を除いてよく条件付きで解く方法を示す: $\tilde{O}(n^{2.065} + k^\omega)$ time は、すべての$k \gtrsim n^{0.78}$に対して [Derezi\'nski, Yang, STOC 2024] の最近の結果を改善する。
2) 正規化線形系 $(A + \lambda I)x = b$ を解くための最初の $\tilde{O}(n^2 + {d_\lambda}^{\omega}$) 時間アルゴリズムを与える。
この問題はガウス過程の回帰のような応用で生じる。
3)Schatten $p$-norms や他の行列ノルムを近似するアルゴリズムを提案する。
例えば、Schatten 1(核)ノルムに対して、[Musco et al , ITCS 2018] の $\tilde{O}(n^{2.11})$ time で実行されるアルゴリズムを与え、$\tilde{O}(n^{2.18})$ method で改善する。
興味深いことに、上記の問題の多くに対する従来の最先端のアルゴリズムは、確率座標や勾配降下のような確率的反復法に依存していた。
私たちの仕事は、マトリックスのスケッチからツールを活用する代わりに、まったく異なるアプローチを取ります。
関連論文リスト
- Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳（メタデータ） (2023-12-14T12:53:34Z) - Quantum speedups for linear programming via interior point methods [1.8434042562191815]
本稿では,$d$変数上の不等式制約で線形プログラムを解く量子アルゴリズムについて述べる。
我々のアルゴリズムは、リーとシドフォードの最先端インテリアポイント法におけるニュートンステップを高速化する。
論文 参考訳（メタデータ） (2023-11-06T16:00:07Z) - Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳（メタデータ） (2023-10-27T16:54:29Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Randomized Block-Coordinate Optimistic Gradient Algorithms for
Root-Finding Problems [8.0153031008486]
大規模設定における非線形方程式の解を近似する2つの新しいアルゴリズムを開発した。
我々は,機械学習における顕著な応用を網羅する大規模有限サム包含のクラスに,本手法を適用した。
論文 参考訳（メタデータ） (2023-01-08T21:46:27Z) - Perseus: A Simple and Optimal High-Order Method for Variational
Inequalities [81.32967242727152]
VI は、$langle F(x), x - xstarrangle geq 0$ for all $x in MathcalX$ であるように、mathcalX$ で $xstar を見つける。
そこで本稿では,テキストitが行探索を必要とせず,$O(epsilon-2/(p+1))$で弱解に確実に収束する$pth$-order法を提案する。
論文 参考訳（メタデータ） (2022-05-06T13:29:14Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - A first-order primal-dual method with adaptivity to local smoothness [64.62056765216386]
凸凹対象 $min_x max_y f(x) + langle Ax, yrangle - g*(y)$, ここで、$f$ は局所リプシッツ勾配を持つ凸関数であり、$g$ は凸かつ非滑らかである。
主勾配ステップと2段ステップを交互に交互に行うCondat-Vuアルゴリズムの適応バージョンを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:19:30Z) - Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。
本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文 参考訳（メタデータ） (2021-10-25T08:34:00Z) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-06-16T03:34:14Z) - Fast and Near-Optimal Diagonal Preconditioning [46.240079312553796]
左か右の対角線再スケーリングにより$mathbfA$の条件数を改善する方法を示す。
構造化混合パッキングと半定値プログラムを対象とし,$widetildeO(textnnz(mathbfA) cdot textpoly(kappastar))$ timeに対して,$mathbfA$の定数係数最適スケーリングを計算する。
論文 参考訳（メタデータ） (2020-08-04T17:53:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。