論文の概要: Fast convolution algorithm for state space models

• arxiv url: http://arxiv.org/abs/2411.17729v1
• Date: Fri, 22 Nov 2024 05:30:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-28 15:25:21.828077
• Title: Fast convolution algorithm for state space models
• Title（参考訳）: 状態空間モデルのための高速畳み込みアルゴリズム
• Authors: Gregory Beylkin,
• Abstract要約: 本稿では,線形時間不変系の行列伝達関数を時間領域に適用するための頑健なアルゴリズムを提案する。 有限個のユーザ選択精度に対して、行列ベクトル乗算の数は$mathcalOleft(log_2Lright)$に削減できることを示す。 重要なことに、時間領域におけるカスケードの実装を用いることで、転送関数を適用するには、N+1$行列ベクトル乗算しか必要としない。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: We present a fast, robust algorithm for applying a matrix transfer function of a linear time invariant system (LTI) in time domain. Computing $L$ states of a multiple-input multiple-output (MIMO) LTI appears to require $L$ matrix-vector multiplications. We demonstrate that, for any finite user-selected accuracy, the number of matrix-vector multiplications can be reduced to $\mathcal{O}\left(\log_{2}L\right)$ (within an $\mathcal{O}\left(L\right)$ algorithm). The algorithm uses an approximation of the rational transfer function in the z-domain by a matrix polynomial of degree $2^{N+1}-1$, where $N$ is chosen to achieve any user-selected accuracy. Importantly, using a cascade implementation in time domain, applying the transfer function requires only $N+1$ matrix-vector multiplications. We note that LTI systems are used in state space models (SSMs) for modeling long range dependencies where $L$ is large. In applications where the state matrix of LTI system is approximated by a structured matrix, the computational cost is further reduced. We briefly describe several structured approximations of matrices that can be used for such purpose.
• Abstract（参考訳）: 本稿では,線形時間不変系の行列伝達関数を時間領域に適用するための高速でロバストなアルゴリズムを提案する。 マルチインプット多重出力(MIMO) LTIの$L$状態の計算には、$L$行列ベクトル乗算が必要である。 有限個のユーザ選択精度に対して、行列ベクトル乗算の数は$\mathcal{O}\left(\log_{2}L\right)$($\mathcal{O}\left(L\right)$アルゴリズム)に還元できることを示した。 このアルゴリズムは、z領域における有理変換関数の近似を、次数2^{N+1}-1$の行列多項式で用いる。 重要なことに、時間領域におけるカスケードの実装を用いることで、転送関数を適用するには、N+1$行列ベクトル乗算しか必要としない。 LTIシステムは、L$が大きければ長い範囲依存をモデル化するために、状態空間モデル(SSM)で使用されることに留意する。 LTIシステムの状態行列が構造化行列によって近似された場合、計算コストはさらに削減される。 このような目的のために使用できる行列のいくつかの構造化近似を簡潔に記述する。

関連論文リスト

• Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
  我々は、このマルコフ連鎖のほぼ最適な実装を示し、ステップごとの複雑さは、約$A$のゼロでないエントリの数であるのに対して、マルコフ連鎖のステップの数は同じである。 1) このダイキンウォークで生じる行列はゆっくりと変化すること,2) この遅い変化を利用した効率的な線形解法を展開し, 以前のステップで計算した情報を用いて行列の逆転を高速化すること,3) ランダム化されたテイラー級数に基づく推定器を用いてメトロポリスフィルタステップにおける行列項の計算を高速化すること,である。
  論文  参考訳（メタデータ） (2024-09-06T14:49:43Z)
• Fast Matrix Multiplication Without Tears: A Constraint Programming Approach [8.52818380743467]
  $N倍のM$行列と$M倍のP$行列の乗算は、単純な$NMPアプローチが示しているよりも少ない乗算で実現できることが知られている。 これにより、高速行列乗法における制約満足度問題が発生する。 本稿では,高速行列乗算のための非可換アルゴリズムを見つけるための,シンプルながら新しい制約プログラミング手法を提案する。
  論文  参考訳（メタデータ） (2023-06-01T19:15:24Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Fast Differentiable Matrix Square Root [65.67315418971688]
  微分可能な行列平方根を計算するために、より効率的な2つの変種を提案する。 前方伝播には, Matrix Taylor Polynomial (MTP) を用いる方法がある。 もう1つの方法は Matrix Pad'e Approximants (MPA) を使うことである。
  論文  参考訳（メタデータ） (2022-01-21T12:18:06Z)
• Efficient Matrix-Free Approximations of Second-Order Information, with Applications to Pruning and Optimization [16.96639526117016]
  Inverse-Hessian Vector Products (IHVPs) の行列のない線形時間アプローチについて検討する。 これらのアルゴリズムは、既存の2階法と比較して計算オーバーヘッドが低いネットワークプルーニングと最適化の最先端結果をもたらす。
  論文  参考訳（メタデータ） (2021-07-07T17:01:34Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  非PSDおよび2乗根行列の次元削減法を提案する。 複数のダウンストリームタスクにこれらのテクニックをどのように使用できるかを示す。
  論文  参考訳（メタデータ） (2021-06-16T04:07:48Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。 本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-12T16:29:45Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  ktimes k$, rank-r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ sample。 我々は、$cal O(frackrepsilon2log2fracepsilon)$ sample, a number linear in the high dimension, and almost linear in the matrices, usually low, rank proofs.というアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-30T19:10:32Z)
• What if Neural Networks had SVDs? [66.91160214071088]
  様々なニューラルネットワークでは、行列反転のような時間を要する行列演算を採用している。 本稿では,行列演算を高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-09-29T12:58:52Z)
• Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
  我々はスパース共起方向を開発し、期待値の$widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$に時間複雑性を減少させる。 理論的解析により,我々のアルゴリズムの近似誤差はCODとほぼ同値であることが判明した。
  論文  参考訳（メタデータ） (2020-09-08T05:39:19Z)
• Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization [24.085358075449406]
  行列平方根とその逆は機械学習で頻繁に現れる。 我々は,$mathbf K1/2 mathbf b$,$mathbf K-1/2 mathbf b$とその導関数を行列ベクトル乗算(MVM)により計算するための高効率二次時間アルゴリズムを導入する。 提案手法は,Krylov部分空間法と有理近似,典型的には4ドル10分の精度で100ドル未満のMVMを推定する。
  論文  参考訳（メタデータ） (2020-06-19T17:56:24Z)

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

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