論文の概要: Low-Rank Updates of Matrix Square Roots
- arxiv url: http://arxiv.org/abs/2201.13156v1
- Date: Mon, 31 Jan 2022 12:05:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-01 19:57:31.605074
- Title: Low-Rank Updates of Matrix Square Roots
- Title（参考訳）: マトリックス角根の低ランク更新
- Authors: Shany Shumeli, Petros Drineas, Haim Avron
- Abstract要約: 行列平方根と逆平方根演算を考える。
逆平方根に対する低ランク近似補正が存在することを示す。
次に、その方程式に対する低ランク解をどのように計算するかについて議論する。
- 参考スコア（独自算出の注目度）: 7.832944895330117
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Models in which the covariance matrix has the structure of a sparse matrix
plus a low rank perturbation are ubiquitous in machine learning applications.
It is often desirable for learning algorithms to take advantage of such
structures, avoiding costly matrix computations that often require cubic time
and quadratic storage. This is often accomplished by performing operations that
maintain such structures, e.g. matrix inversion via the
Sherman-Morrison-Woodbury formula. In this paper we consider the matrix square
root and inverse square root operations. Given a low rank perturbation to a
matrix, we argue that a low-rank approximate correction to the (inverse) square
root exists. We do so by establishing a geometric decay bound on the true
correction's eigenvalues. We then proceed to frame the correction has the
solution of an algebraic Ricatti equation, and discuss how a low-rank solution
to that equation can be computed. We analyze the approximation error incurred
when approximately solving the algebraic Ricatti equation, providing spectral
and Frobenius norm forward and backward error bounds. Finally, we describe
several applications of our algorithms, and demonstrate their utility in
numerical experiments.
- Abstract（参考訳）: 共分散行列がスパース行列と低階摂動の構造を持つモデルは、機械学習アプリケーションにおいてユビキタスである。
学習アルゴリズムはそのような構造を利用するのが望ましいことが多く、立方体時間と二次記憶を必要とするコストのかかる行列計算を避けることができる。
これはしばしば、シャーマン・モリソン・ウッドベリーの公式を通した行列反転のような構造を維持する操作によって達成される。
本稿では,行列平方根および逆平方根演算について考察する。
行列に対する低階摂動が与えられたとき、(逆)平方根に対する低階近似補正が存在すると論じる。
我々は、真の補正の固有値に縛られる幾何学的減衰を確立することで、そうする。
次に、補正の枠組みは代数的リカッティ方程式の解を持ち、その方程式に対する低ランク解がどのように計算できるかを議論する。
代数的リカティ方程式を近似解く際に生じる近似誤差を解析し、スペクトルとフロベニウスノルムの前方および後方誤差境界を与える。
最後に,本アルゴリズムのいくつかの応用について述べるとともに,数値実験でその有用性を実証する。
関連論文リスト
- Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
切り抜き固有分解を用いて得られたカーネル行列の低ランク近似に対するエントリーワイド誤差境界を導出する。
重要な技術的革新は、小さな固有値に対応するカーネル行列の固有ベクトルの非局在化結果である。
我々は、合成および実世界のデータセットの集合に関する実証的研究により、我々の理論を検証した。
論文 参考訳（メタデータ） (2024-05-23T12:26:25Z) - Approximate Secular Equations for the Cubic Regularization Subproblem [20.396963952753435]
立方正則化サブプロブレム(CRS)の新しい解法を提案する。
提案手法は2つの最先端手法より優れている。
論文 参考訳（メタデータ） (2022-09-27T09:22:44Z) - Fast Differentiable Matrix Square Root and Inverse Square Root [65.67315418971688]
微分可能な行列平方根と逆平方根を計算するためのより効率的な2つの変種を提案する。
前方伝搬には, Matrix Taylor Polynomial (MTP) を用いる方法と, Matrix Pad'e Approximants (MPA) を使用する方法がある。
一連の数値実験により、両方の手法がSVDやNSの繰り返しと比較してかなりスピードアップすることが示された。
論文 参考訳（メタデータ） (2022-01-29T10:00:35Z) - Sparse Factorization of Large Square Matrices [10.94053598642913]
本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。
近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。
近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
論文 参考訳（メタデータ） (2021-09-16T18:42:21Z) - Statistical limits of dictionary learning: random matrix theory and the
spectral replica method [28.54289139061295]
ベイズ最適設定における行列記述と辞書学習の複雑なモデルについて考察する。
本稿では, 統計力学とランダム行列理論, スペクトル複製法を組み合わせた新しいレプリカ法を提案する。
論文 参考訳（メタデータ） (2021-09-14T12:02:32Z) - Non-PSD Matrix Sketching with Applications to Regression and
Optimization [56.730993511802865]
非PSDおよび2乗根行列の次元削減法を提案する。
複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
論文 参考訳（メタデータ） (2021-06-16T04:07:48Z) - Solving weakly supervised regression problem using low-rank manifold
regularization [77.34726150561087]
我々は弱い教師付き回帰問題を解く。
weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。
数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
論文 参考訳（メタデータ） (2021-04-13T23:21:01Z) - Fast Rank Reduction for Non-negative Matrices via Mean Field Theory [5.634825161148483]
構造標本空間上の対数線形モデルを用いて行列をモデル化することにより、平均場近似としてランクの減少を定式化する。
提案手法は,NMFとNMFの変種であるlraNMFよりも高速であり,合成および実世界のデータセット上での競合的低ランク近似誤差を実現することを実証的に示す。
論文 参考訳（メタデータ） (2020-06-09T14:55:47Z) - Sketching Transformed Matrices with Applications to Natural Language
Processing [76.6222695417524]
本稿では, 変換行列を用いて, 与えられた小さな行列の積を計算するための空間効率のよいスケッチアルゴリズムを提案する。
提案手法は誤差が小さく,空間と時間の両方で効率がよいことを示す。
論文 参考訳（メタデータ） (2020-02-23T03:07:31Z) - Optimal Iterative Sketching with the Subsampled Randomized Hadamard
Transform [64.90148466525754]
最小二乗問題に対する反復スケッチの性能について検討する。
本研究では、Haar行列とランダム化されたHadamard行列の収束速度が同一であることを示し、ランダムなプロジェクションを経時的に改善することを示した。
これらの手法は、ランダム化次元還元を用いた他のアルゴリズムにも適用することができる。
論文 参考訳（メタデータ） (2020-02-03T16:17:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。