Fast convolution algorithm for state space models

• URL: http://arxiv.org/abs/2411.17729v2
• Date: Fri, 29 Nov 2024 01:10:55 GMT
• Title: Fast convolution algorithm for state space models
• Authors: Gregory Beylkin,
• Abstract summary: We present a robust algorithm for applying a matrix transfer function of a linear time invariant system (LTI) in time domain.<n>We demonstrate that, for any finite user-selected accuracy, the number of matrix-vector multiplications can be reduced to $mathcalOleft(log_2Lright)$.<n> Importantly, using a cascade implementation in time domain, applying the transfer function requires only $N+1$ matrix-vector multiplications.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Quantum Algorithms for Projection-Free Sparse Convex Optimization [32.34794896079469]
  For the vector domain, we propose two quantum algorithms for sparse constraints that find a $varepsilon$-optimal solution with the query complexity of $O(sqrtd/varepsilon)$.<n>For the matrix domain, we propose two quantum algorithms for nuclear norm constraints that improve the time complexity to $tildeO(rd/varepsilon2)$ and $tildeO(sqrtrd/varepsilon3)$.
  arXiv  Detail & Related papers  (2025-07-11T12:43:58Z)
• SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More [37.208622097149714]
  We give a new family of upper-time algorithms which can certify bounds on the maximum of $|M u|$. Our certification algorithm makes essential use of the Sum-of-Squares hierarchy.
  arXiv  Detail & Related papers  (2024-12-30T18:59:46Z)
• Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
  We present a nearly-optimal implementation of this Markov chain with per-step complexity which is roughly the number of non-zero entries of $A$ while the number of Markov chain steps remains the same. Key technical ingredients are 1) to show that the matrices that arise in this Dikin walk change slowly, 2) to deploy efficient linear solvers that can leverage this slow change to speed up matrix inversion by using information computed in previous steps, and 3) to speed up the computation of the determinantal term in the Metropolis filter step via a randomized Taylor series-based estimator.
  arXiv  Detail & Related papers  (2024-09-06T14:49:43Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  We study the problem of residual error estimation for matrix and vector norms using a linear sketch. We demonstrate that this gives a substantial advantage empirically, for roughly the same sketch size and accuracy as in previous work. We also show an $Omega(k2/pn1-2/p)$ lower bound for the sparse recovery problem, which is tight up to a $mathrmpoly(log n)$ factor.
  arXiv  Detail & Related papers  (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. We show that a simple single-pass procedure that thresholds the output of Oja's algorithm can achieve the minimax error bound under some regularity conditions in $O(d)$ space and $O(nd)$ time.
  arXiv  Detail & Related papers  (2024-02-11T16:36:48Z)
• Fast Matrix Multiplication Without Tears: A Constraint Programming Approach [8.52818380743467]
  It is known that the multiplication of an $N times M$ matrix with an $M times P$ matrix can be performed using fewer multiplications than what the naive $NMP approach suggests. This gives rise to the constraint satisfaction problem of fast matrix multiplication. We propose a simple yet novel Constraint Programming approach to find non-commutative algorithms for fast matrix multiplication.
  arXiv  Detail & Related papers  (2023-06-01T19:15:24Z)
• An Improved Classical Singular Value Transformation for Quantum Machine Learning [2.3326951882644553]
  We study quantum speedups in quantum machine learning (QML) by analyzing the quantum singular value transformation (QSVT) framework. Our key insight is to combine the Clenshaw recurrence, an iterative method for computing matrix stability, with sketching techniques to simulate QSVT classically.
  arXiv  Detail & Related papers  (2023-03-02T18:53:03Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  We consider learning in an adversarial Decision Process (MDP) where the loss functions can change arbitrarily over $K$ episodes. This paper provides two algorithms that improve the regret to $tildemathcal O(K2/3)$ in the same setting.
  arXiv  Detail & Related papers  (2023-01-30T14:37:21Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly. We provide a novel binary tree summation procedure that simultaneously estimates all $m$ traces up to $epsilon$ error with $delta$ failure probability. Our lower bounds (1) give the first tight bounds for Hutchinson's estimator in the matrix-vector product model with Frobenius norm error even in the static setting, and (2) are the first unconditional lower bounds for dynamic trace estimation.
  arXiv  Detail & Related papers  (2022-09-30T04:15:44Z)
• Private Matrix Approximation and Geometry of Unitary Orbits [29.072423395363668]
  This problem seeks to approximate $A$ by a matrix whose spectrum is the same as $Lambda$. We give efficient and private algorithms that come with upper and lower bounds on the approximation error.
  arXiv  Detail & Related papers  (2022-07-06T16:31:44Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  We give a sketching-based iterative algorithm that computes $1+varepsilon$ approximate solutions for the ridge regression problem. We also show that this algorithm can be used to give faster algorithms for kernel ridge regression.
  arXiv  Detail & Related papers  (2022-04-13T22:18:47Z)
• Perturbation Analysis of Randomized SVD and its Applications to High-dimensional Statistics [8.90202564665576]
  We study the statistical properties of RSVD under a general "signal-plus-noise" framework. We derive nearly-optimal performance guarantees for RSVD when applied to three statistical inference problems.
  arXiv  Detail & Related papers  (2022-03-19T07:26:45Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• What if Neural Networks had SVDs? [66.91160214071088]
  Various Neural Networks employ time-consuming matrix operations like matrix inversion. We present an algorithm that is fast enough to speed up several matrix operations.
  arXiv  Detail & Related papers  (2020-09-29T12:58:52Z)
• Approximate Multiplication of Sparse Matrices with Limited Space [24.517908972536432]
  We develop sparse co-occuring directions, which reduces the time complexity to $widetildeOleft((nnz(X)+nnz(Y))ell+nell2right)$ in expectation. Theoretical analysis reveals that the approximation error of our algorithm is almost the same as that of COD.
  arXiv  Detail & Related papers  (2020-09-08T05:39:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.