論文の概要: Structured Semidefinite Programming for Recovering Structured
Preconditioners
- arxiv url: http://arxiv.org/abs/2310.18265v1
- Date: Fri, 27 Oct 2023 16:54:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-30 12:55:12.301481
- Title: Structured Semidefinite Programming for Recovering Structured
Preconditioners
- Title（参考訳）: 構造付きプレコンディショナーの復元のための構造化半有限計画法
- Authors: Arun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur,
Aaron Sidford, Kevin Tian
- Abstract要約: 正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
- 参考スコア（独自算出の注目度）: 41.28701750733703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We develop a general framework for finding approximately-optimal
preconditioners for solving linear systems. Leveraging this framework we obtain
improved runtimes for fundamental preconditioning and linear system solving
problems including the following. We give an algorithm which, given positive
definite $\mathbf{K} \in \mathbb{R}^{d \times d}$ with
$\mathrm{nnz}(\mathbf{K})$ nonzero entries, computes an $\epsilon$-optimal
diagonal preconditioner in time $\widetilde{O}(\mathrm{nnz}(\mathbf{K}) \cdot
\mathrm{poly}(\kappa^\star,\epsilon^{-1}))$, where $\kappa^\star$ is the
optimal condition number of the rescaled matrix. We give an algorithm which,
given $\mathbf{M} \in \mathbb{R}^{d \times d}$ that is either the pseudoinverse
of a graph Laplacian matrix or a constant spectral approximation of one, solves
linear systems in $\mathbf{M}$ in $\widetilde{O}(d^2)$ time. Our diagonal
preconditioning results improve state-of-the-art runtimes of $\Omega(d^{3.5})$
attained by general-purpose semidefinite programming, and our solvers improve
state-of-the-art runtimes of $\Omega(d^{\omega})$ where $\omega > 2.3$ is the
current matrix multiplication constant. We attain our results via new
algorithms for a class of semidefinite programs (SDPs) we call
matrix-dictionary approximation SDPs, which we leverage to solve an associated
problem we call matrix-dictionary recovery.
- Abstract（参考訳）: 線形系を解くための近似最適前提条件子を求めるための汎用フレームワークを開発した。
このフレームワークを活用することで、基本的なプリコンディショニングや、以下の問題を含む線形システム解決のためのランタイムが改善される。
正の定値 $\mathbf{k} \in \mathbb{r}^{d \times d}$ with $\mathrm{nnz}(\mathbf{k})$ nonzero エントリが与えられると、$\widetilde{o}(\mathrm{nnz}(\mathbf{k}) \cdot \mathrm{poly}(\kappa^\star,\epsilon^{-1})$, ここで$\kappa^\star$は再スケール行列の最適条件数である。
グラフラプラシア行列の擬逆あるいは1の定数スペクトル近似である$\mathbf{M} \in \mathbb{R}^{d \times d}$を与えられたアルゴリズムは、$\mathbf{M}$ in $\widetilde{O}(d^2)$ timeで線形系を解く。
我々の対角的プレコンディショニング結果は、汎用半定値プログラミングによって達成された$\Omega(d^{3.5})$の最先端ランタイムを改善するとともに、現在の行列乗算定数である$\Omega(d^{\omega})$の最先端ランタイムを改善する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラム(SDP)のクラスに対する新しいアルゴリズムを用いて結果を得る。
関連論文リスト
- The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。
アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文 参考訳（メタデータ） (2024-10-26T06:21:42Z) - 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) - Efficient Matrix Factorization Via Householder Reflections [2.3326951882644553]
我々は$mathbfH$と$mathbfX$を$mathbfY$から正確に回収することが、$mathbfY$の$Omega$列で保証されていることを示す。
この研究のテクニックが、辞書学習のための代替アルゴリズムの開発に役立つことを願っている。
論文 参考訳（メタデータ） (2024-05-13T11:13:49Z) - 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) - 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) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。
本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
論文 参考訳（メタデータ） (2023-03-22T04:07:26Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Sublinear classical and quantum algorithms for general matrix games [11.339580074756189]
行列ゲームに対する線形古典的および量子的アルゴリズムについて検討する。
任意の固定 $qin (1,2) に対して、$mathcalX$ が$ell_q$-norm 単位球である行列ゲームが加法誤差内で解決される。
同じタスクを時間内に解く、対応する部分線形量子アルゴリズムも提供する。
論文 参考訳（メタデータ） (2020-12-11T17:36:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。