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

• arxiv url: http://arxiv.org/abs/2411.17729v3
• Date: Fri, 11 Apr 2025 00:35:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-14 15:34:41.458622
• Title: Fast convolution algorithm for state space models
• Title（参考訳）: 状態空間モデルのための高速畳み込みアルゴリズム
• Authors: Gregory Beylkin,
• Abstract要約: 線形時間不変系(LTI)の行列伝達関数を時間領域に適用するための無条件安定アルゴリズムを提案する。 そのような転送関数を$L$状態に応用するには、行列ベクトルの乗算を2L$以上必要としない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present an unconditionally stable algorithm for applying matrix transfer function of a linear time invariant system (LTI) in time domain. The state matrix of an LTI system used for modeling long range dependencies in state space models (SSMs) has eigenvalues close to $1$. The standard recursion defining LTI system becomes unstable if the $m\times m$ state matrix has just one eigenvalue with absolute value even slightly greater than 1. This may occur when approximating a state matrix by a structured matrix to reduce the cost of matrix-vector multiplication from $\mathcal{O}\left(m^{2}\right)$ to $\mathcal{O}\left(m\right)$ or $\mathcal{O}\left(m\log m\right).$ We introduce an unconditionally stable algorithm that 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. Using a cascade implementation in time domain, applying such transfer function to compute $L$ states requires no more than $2L$ matrix-vector multiplications (whereas the standard recursion requires $L$ matrix-vector multiplications). However, using unconditionally stable algorithm, it is not necessary to assure that an approximate state matrix has all eigenvalues with absolute values strictly less than 1 i.e., within the desired accuracy, the absolute value of some eigenvalues may possibly exceed $1$. Consequently, this algorithm allows one to use a wider variety of structured approximations to reduce the cost of matrix-vector multiplication and we briefly describe several of them to be used for this purpose.
• Abstract（参考訳）: 線形時間不変系(LTI)の行列伝達関数を時間領域に適用するための無条件安定アルゴリズムを提案する。 LTIシステムの状態行列は、状態空間モデル(SSM)における長距離依存をモデル化するために使用され、固有値が1ドル近い。 LTI 系を定義する標準的な再帰は、$m\times m$ 状態行列が 1 より少し大きい絶対値を持つ1つの固有値を持つと不安定になる。 これは、状態行列を構造化行列で近似して、行列-ベクトル乗算のコストを $\mathcal{O}\left(m^{2}\right)$ から $\mathcal{O}\left(m\right)$ または $\mathcal{O}\left(m\log m\right)$ に下げるときに発生する。 次数2^{N+1}-1$の行列多項式により、z領域における有理変換関数の近似を用いて、非条件で安定なアルゴリズムを導入する。 時間領域におけるカスケードの実装を用いることで、そのような転送関数を$L$状態の計算に適用するには、2L$行列ベクトル乗算を必要としない(ただし、標準的な再帰は$L$行列ベクトル乗算を必要とする)。 しかし、非条件で安定なアルゴリズムを用いることで、近似状態行列が絶対値が 1 未満であるすべての固有値を持つことを保証する必要はなく、すなわち、所望の精度で、いくつかの固有値の絶対値が 1 ドルを超える可能性がある。 そこで本アルゴリズムでは,行列ベクトル乗算のコストを削減するために,より多様な構造近似を用いることが可能である。

関連論文リスト

• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  我々は、最大$|M u|$で境界を証明できる新しいアップタイムアルゴリズムの族を与える。 我々の認証アルゴリズムは, Sum-of-Squares階層を必須に活用する。
  論文  参考訳（メタデータ） (2024-12-30T18:59:46Z)
• Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
  我々は、このマルコフ連鎖のほぼ最適な実装を示し、ステップごとの複雑さは、約$A$のゼロでないエントリの数であるのに対して、マルコフ連鎖のステップの数は同じである。 1) このダイキンウォークで生じる行列はゆっくりと変化すること,2) この遅い変化を利用した効率的な線形解法を展開し, 以前のステップで計算した情報を用いて行列の逆転を高速化すること,3) ランダム化されたテイラー級数に基づく推定器を用いてメトロポリスフィルタステップにおける行列項の計算を高速化すること,である。
  論文  参考訳（メタデータ） (2024-09-06T14:49:43Z)
• 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)
• Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
  Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。 Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
  論文  参考訳（メタデータ） (2024-02-11T16:36:48Z)
• Fast Matrix Multiplication Without Tears: A Constraint Programming Approach [8.52818380743467]
  $N倍のM$行列と$M倍のP$行列の乗算は、単純な$NMPアプローチが示しているよりも少ない乗算で実現できることが知られている。 これにより、高速行列乗法における制約満足度問題が発生する。 本稿では,高速行列乗算のための非可換アルゴリズムを見つけるための,シンプルながら新しい制約プログラミング手法を提案する。
  論文  参考訳（メタデータ） (2023-06-01T19:15:24Z)
• An Improved Classical Singular Value Transformation for Quantum Machine Learning [2.3326951882644553]
  量子機械学習(QML)における量子スピードアップについて,量子特異値変換(QSVT)フレームワークを解析して検討する。 我々の重要な洞察は、行列安定性を計算するための反復的手法であるClenshaw繰り返しと、QSVTを古典的にシミュレートするスケッチ技術を組み合わせることである。
  論文  参考訳（メタデータ） (2023-03-02T18:53:03Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Private Matrix Approximation and Geometry of Unitary Orbits [29.072423395363668]
  この問題は、スペクトルが$Lambda$と同じ行列で$A$を近似しようとする。 近似誤差の上限値と下限値を持つ効率的でプライベートなアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-06T16:31:44Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics [8.90202564665576]
  一般の「信号+雑音」の枠組みによるRSVDの統計特性について検討する。 3つの統計的推論問題に適用した場合、RSVDのほぼ最適性能保証を導出する。
  論文  参考訳（メタデータ） (2022-03-19T07:26:45Z)
• 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)

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

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