論文の概要: Sparse Factorization of Large Square Matrices

• arxiv url: http://arxiv.org/abs/2109.08184v1
• Date: Thu, 16 Sep 2021 18:42:21 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-20 14:37:27.551897
• Title: Sparse Factorization of Large Square Matrices
• Title（参考訳）: 大きな正方行列のスパース因子分解
• Authors: Ruslan Khalitov, Tong Yu, Lei Cheng, Zhirong Yang
• Abstract要約: 本稿では,大面積の正方行列とスパースフルランク行列の積を近似する。 近似では、我々の手法は$Ntimes N$ full matrix に対して$N(log N)2$ non-zero number しか必要としない。 近似行列がスパースかつハイランクである場合,本手法により近似精度が向上することを示す。
• 参考スコア（独自算出の注目度）: 10.94053598642913
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Square matrices appear in many machine learning problems and models. Optimization over a large square matrix is expensive in memory and in time. Therefore an economic approximation is needed. Conventional approximation approaches factorize the square matrix into a number matrices of much lower ranks. However, the low-rank constraint is a performance bottleneck if the approximated matrix is intrinsically high-rank or close to full rank. In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only $N(\log N)^2$ non-zero numbers for an $N\times N$ full matrix. We present both non-parametric and parametric ways to find the factorization. In the former, we learn the factorizing matrices directly, and in the latter, we train neural networks to map input data to the non-zero matrix entries. The sparse factorization method is tested for a variety of synthetic and real-world square matrices. The experimental results demonstrate that our method gives a better approximation when the approximated matrix is sparse and high-rank. Based on this finding, we use our parametric method as a scalable attention architecture that performs strongly in learning tasks for long sequential data and defeats Transformer and its several variants.
• Abstract（参考訳）: 正方行列は多くの機械学習問題やモデルに現れる。 大きな正方行列に対する最適化は、メモリと時間において高価である。 そのため経済的な近似が必要となる。 従来の近似法は、平方行列をより低い階数の数行列に分解する。 しかし、近似行列が本質的にハイランクあるいはフルランクに近い場合、低ランク制約は性能ボトルネックとなる。 本稿では,全ランク行列のスパース積を持つ大きな正方行列を近似する。 近似では、我々の手法は$N(\log N)^2$非零数しか必要とせず、$N\times N$ full matrix である。 非パラメトリックとパラメトリックの両方の方法で因子分解を見つける。 前者では行列の分解を直接学習し、後者では、入力データをゼロでない行列エントリにマッピングするようにニューラルネットワークを訓練する。 スパース分解法は, 種々の合成および実世界の正方行列に対して試験される。 実験の結果,近似行列がスパースでハイランクである場合,本手法により近似性が向上することが示された。 この発見に基づいて、我々のパラメトリック手法をスケーラブルなアテンションアーキテクチャとして使用し、長いシーケンシャルなデータに対する学習タスクを強力に実行し、Transformerとそのいくつかの変種を破る。

関連論文リスト

• Multiresolution kernel matrix algebra [0.0]
  本研究では, あるS形式において, 最適スパース行列を生成するサンプルレットを用いて, カーネル行列の圧縮を示す。 カーネル行列の逆数(もし存在するなら)は S-形式でも圧縮可能である。 行列代数は擬微分計算によって数学的に正当化される。
  論文  参考訳（メタデータ） (2022-11-21T17:50:22Z)
• A Structured Sparse Neural Network and Its Matrix Calculations Algorithm [0.0]
  非対称な三対角行列を導入し, 対角方向のスパース成分とオフセット部分および超対角線を導入した。 行列逆が存在しない場合には、最小二乗型擬逆が提供される。 その結果,行列のサイズが大きくなると計算コストが著しく向上することがわかった。
  論文  参考訳（メタデータ） (2022-07-02T19:38:48Z)
• Low-Rank Updates of Matrix Square Roots [7.832944895330117]
  行列平方根と逆平方根演算を考える。 行列に対する低階摂動が与えられたとき、(逆)平方根に対する低階近似補正が存在すると論じる。 次に、その方程式に対する低ランク解をどのように計算するかについて議論する。
  論文  参考訳（メタデータ） (2022-01-31T12:05:33Z)
• 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)
• Fast Differentiable Matrix Square Root [65.67315418971688]
  微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。 前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。 もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
  論文  参考訳（メタデータ） (2022-01-21T12:18:06Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  一般的なNystr"om法を不確定な設定に一般化する。 我々のアルゴリズムは任意の類似性行列に適用でき、行列のサイズでサブ線形時間で実行される。 本手法は,CUR分解の単純な変種とともに,様々な類似性行列の近似において非常によく機能することを示す。
  論文  参考訳（メタデータ） (2021-12-17T17:04:34Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• 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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。