SaFARi: State-Space Models for Frame-Agnostic Representation
Authors: Hossein Babaei
Mel White
Sina Alemohammad
Richard Baraniuk
Venue: Accepted by TMLR ()

Abstract: State-Space Models (SSMs) have re-emerged as a powerful tool for online function approximation, and as the backbone of machine learning models for long-range dependent data.
However, to date, only a few polynomial bases have been explored for this purpose, and the state-of-the-art implementations were built upon the best of a few limited options. In this paper, we present a generalized method for building an SSM with any frame or basis, rather than being restricted to polynomials.
This framework encompasses the approach known as HiPPO, but also permits an infinite diversity of other possible "species" within the SSM architecture. We dub this approach SaFARi: SSMs for Frame-Agnostic Representation.

Published in Transactions on Machine Learning Research (10/2025)
SaFARi: State-Space Models for Frame-Agnostic Represen- tation
Hossein Babaei
hb260rice.edu
Deportment of Electrical and Computer Engineering
Rice University
Mel White
mel.whtterrieecc
Department Electricol and Computer Engincering Rice University
Sina Alemohammad
sa860rice.o edu
Department of Electricol and Computer Engineering
Rice University
Richard G. Baraniuk
richb edu
Deportment of Electricol and Computer Engineering
Rice Universily
Reviewed on OpenReview: https: // openreview. foru?? id= ht-.lgglllBBBddhoottrr/---8--883
Abstract
State-Space Models (SSMs) have re-emerged powerful tool for online function approx- imation, and as the backbone of machine learning models for long-range dependent data. However, to date, only few polynomial bases have been explored for this purpose, and the state-of-the-art implementations were built upon a few limited options. In this paper, we present a generalized method for building an SSM with any frame or basis. This framework encompassos the approach known as HiPPO, but also permits an infinite diversity of other possible "species" of SSM, paving the way for improved performance of SSM-based machine learning models. We dub this approach SaFARi: SSMs for Trame-Agnostic Representation.
1
Introduction
Modeling sequential data is a cornerstone of modern machine learning, with applications spanning natural language processing, speech recognition, video analysis, and beyond (Zubié et al.) 2024 Alemohammad et al. 2021 Nguyen et al. 2022). A fundamental challenge in these domains the efficient representation of range dependence in time-series data, where the goal is to capture and preserve the essential features of the input signal necessary for downstream tasks over extended time horizons while maintaining computational tractability (Hochreiter & Schmidhuber 1997).
Machine learning approaches, such as recurrent neural networks (RNNs), struggle to learn long-range dependencies due to limited memory horizons (Elman 1990 Hochreiter & Schmidhuber) 1997 Schuster & Paliwal| 1997 Pascanu et al., (2013). During backpropagation, gradients are repeatedly multiplied by the weight matrix, causing them to either shrink exponentially (vanish) grow exponentially (explode). Vanishing gradients prevent the network from updating weights effectively, while exploding gradients lead to unstable training. Although variants like LSTMs (Graves & Schmidhuber 2005) and GRUs (Cho et al. 2014 address some of these limitations, they often require task-specific paraneterization, and cannot generalize across different sequence lengths or timescales.
State-space models (SSMs) present a powerful alternative for online representation of sequential data. By design, SSMs enable the online computation of compressive representations, maintaining constant-size

---

Published in Transactions on Machine Learning Research (10/2025)
memory footprint regardless of sequence length. The seminal work of Gu et al. introduced High- Righ-Order Polynomial Projection Operators (HiPPO), which leverages orthogonal function bases to enable theoretically grounded, real-time updates of sequence representations. This framework, and its subsequent extensions into learned architecturcs, have demonstrated remarkable performance in tasks involving long-range dependencies, such as language modeling and signal processing (Gu Dao 2023; Gu el. al., 2022b 2023 Gupta al. 2024
Gu et al., 2022a; Smith et al. 2023; Hasani et al. 2023). By formulating sequence representation as an online function approximation problem, HiPPO provides a unified perspective on memory mechanisms, offering both theoretical guarantees and practical efficiency.
However, despite its successes, the HiPPO framework has been limited to specific familics of orthogonal polynomials. While these bases are well-suited for certain applications, they are not univensally optimal for all signal classes. Fourier bases, for instance, are optimal for smooth, periodic signals due to their global frequency representation. Polynomial bases, such as orthogonal polynomials (e.g., Legendre or Chebyshev), are particularly effective for approximating smooth functions over compact intervals.
The absence of more flexible basis selection restricts the adaptability of the HiPPO framework. In this work, we address this restriction by presenting generalized method for constructing SSMs using any frame or basis of choice, which we term SaFARi (SSMs for Frame-Agnostic Representation). Our approach extends and generalizes the HiPPO framework using a numerical (as opposed to closed-form) method, which enables us to relax the requirements on the basis, such as orthogonality of the components.
Our key contributions are as follows:
Generalized SSM construction: We present SaFARi, framo-agnostic method for deriving SSMs associated with any basis or frame, generalizing the HiPPO framework to broader class of function representations.
Error Analysis: We provide a comprehensive discussion of SaFARi's error sources and derive error bounds, offering thcorotical insights into its performance and limitations.
This paper is organized as follows. In Section 2 review the HiPPO framework and its limitations, motivating the need for generalized approach. Section 3 provides the required mathematical preliminaries. Section introduces our frame-agnostic method for SSM construction, and then Sections 5 and 6 address implementation considerations and stratogics for SaFARi, including error analysis and computational efficiency. Section demonstraatss empirical validation of the method and the theoretical claims presented in this paper. Finally, Section discusses the broader implications of our work and outlines directions for future research.
2
Background
Recent advances in machine learning, computer vision, and LLMs have exploited the ability to collect and contextualize more and more data over longer time frames. Handling such sequential data presents three main challenges: 1) generating compact and low-dimensional representation of the sequence, 2) effectively preserving information within that representation, and 3) enabling real-time updates for streaming data.
The classic linear method of obtaining the coefficients of a compressed representation of a signal is through a transform (e.g. Fourier) [Oppenheim] 1999: Abbate et al. 2012 Box et al., 2015 Proakis 2001 Prandoni & Vetterli 2008). However, significant limitation of this method its inefficiency in handling real-time updates. When new data arrives, the representation must be recalculated in its entirety, necessitating the storage of all prior data, which is inefficient in terms of both computation and storage requirements. This limits the horizon of the captured dependencies within the sequence.
Nonlinear models, such as recurrent neural networks (RNNs) and their variants, have been introduced more recently (Elman 1990 Hochreiter & Schmidhuber 1997 Cho et al. 2014 Schuster & Paliwal 1997). Since these learned representations are task-specific, they are not casily utilized for other cireumstances or applications. Furthermore, RNNs struggle capture long-range dependencies due to issues such as vanishing and exploding gradients.
2

---

Published in Transactions on Machine Learning Research (10/2025)
8(F)
ODE Update
c(t)
B
Figure 1: An SSM block-diagram, with the necessary ODE update step included.
2.1
Space-space models
The state-space representation itself is not new; it was introduced by Kálmán (9660) via the eponymous Kalman Filter. For an input u(4), output y(), and a state representation called =(4), many systems and their properties can described and controlled with the following system of ODEs, illustrated Fig. !
#(t) Ax(t) Bu(() y(t) Cx(()) + Du(t).
(1)
In many classic applications, we iteratively update the matrices A, B, C, and D to control or predict the output y based on previous values of u. For online function approximation, however, we instcad define the matrices A and B such that they iteratively update a vector of coefficients e over a particular basis. For the moment, we can ignore C and D (or, equivalently, consider C to be an identity matrix and D 0). For stability, A must have only negative eigenvalues, so we explicitly include negative sign here. A and B may may not be constant over time, for completeness, we call these A(t), B(t). Eq. 1 is now
ē= -((ee()( (()((()())BB())) B()u(()
(2)
The challenge in the problem of the approximation of online functions is to derive appropriate matrices A and B. Legendre Memory Units (LMUs) were proposed for this task by (Voelker et al. 2019), and subsequently expanded upon by (Gu et al. 2020). We note that the term "SSM" in machine learning literature in recent years has become & synecdoche, relerring both to the classical A, matrix structure described here, as well as the larger models that utilize these SSMs as layer, such as S4 Gu al.) (2022b). For the purposes of this paper, we disambiguate these structures, and will use the term SSM to describe only the former.
2.2 HiPPO: High-order Polynomial Projection Operators
The LMU and HiPPO frameworks (Voelker al. 2019 Gu ct al. 2020) enable online function approximation using pre-determined SSM parameters derived from a basis of orthogonal polynomials G. It. optimizes ||w- (t)l for (t) 9, to find set of coefficients for the orthogonal polynomials every time T, which yields the approximation of the input function over [0.
In addition to choosing the set of polynomials, one must also select a measure, the combination of a weighting function and a windowing function. The window indicates which samples are included, and the weighting assigns a weight to each sample. HiPPO (Gu et al., 2020) considered several possible measures,
two of which (illustrated in Fig. 2 are:
1 (arl1) Ø LETT-N
(so(() = 7 1
(3)
The uniform translated measure, (tr()), gives equal weight to all samples in the most recent window with a constant length 0, and zero weight to previous samples. The uniform scaled measure, Pee(t), gives equal weight all the times observed since = This can be interpreted as squeezing or stretching the basis or frame match the current length of the signal any given time. Thus, the representation produced by this measure becomes less informative about. the finer details of the signal more history is observed, since
3

---

Published in Transactions on Machine Learning Research (10/2025)
the stretching of the basis will gradually increase the lowest observable frequency. This work considers only uniformly weighted measures, for the sake of clarity in our derivations and examples. However, one could
implement any desired weighting scheme by applying any function of I'' in place of or in Eq. 3
For the space orthogonal polynomials, the HiPPO ODE update (Gu et al. 2020 (see Fig. follows a
first-order linear differential equation:
d aT AT)= -(r + Beryu(()
(4)
where u(T) is the value of the input signal at the current time T, and ((T) is the vector containing the representation of the E [0, T] part the input signal. A(r) and B(zy are also a time-varying matrix and vector that can be derived for the particular choice of the measure and orthogonal polynomial.
Solving the differential equation to update the SSM: The differential equation (Eq. 4 be solved incrementally, and there are several methods to do Butcher (1987). We use the generalized bilinear transform (GBT) (Zhang et al., 2007), relying on findings from Gu et al. (2020) that the GBT produces the best numerical error in solving first-order SSMs. The GBT update rule is
c(t - At) (I (taAAt)))) (I 8t(1 ()(()))(()) + (I (t)A(++))) StB(t)u(t),
(5)
where 0 < 1 is a chosen constant. (For 0, the update rule becomes the forward Euler method.)
Diagonalizing the transition matrix A: The incremental update given by the GBT requires matrix inversion and matrix products at each increment. Having diagonal A significantly reduces the computational cost of these operations. If the measure used for the SSM is such that the cigenvectors of A(t) remain constant (for example, if A(t) is constant matrix multiplied by an arbitrary function of time), then it is possible to find a change of basis that makes the SSM matrix diagonal. To do this, one finds the eigenvalue decomposition the matrix A(I) = VA(I)V-1 and re-write the SSM as
i
Ot c = -A(Tē Bu(t),
(6)
where ē = V-te and B V().()). This means that one solve Eq, 6 instead of Eq. then find the representation from ē with single matrix multiplication.
2.3 Limitations of HiPPO
The original HiPPO formulation and a subsequent follow-up (Gu al. 2023) included handful of orthogonal polynomial bases with specific measures. There is method in the literature for arbitrary choice of basis and measure (see Table D.
184 technically applics an exponential measure ODE; however, the A matrix SSM is generated based on uniformly weighted scaled Legendre polynomial basis. 2Sme implementations in the translated case also apply an exponential decay measure in order to ensure or orthogonality.
Scaled (1)c)
1g
10
1/2
1p
10
1g
Trassattd (pt))
Er
to
12
2r
to
fg
Figure 2: Two different uniform measures (red) applied to signal (blue). The red shaded demonstrates
how the measure changes as time evolves and more samples of the input are observed.
4

---

Published in Transactions on Machine Learning Research (10/2025)
Measure
Scaled
Translated
Basis or Frame
Legendre
Gu et al.
2020
Gu al.
2020
Gu et al.
(2023
Fourier
Gu et al.
2020
Gu al.
2020
1.8
Laguerre
Gu ct al.
2020 .4
Chebychev
Gu el al.
12020 254
Arbitrary
Table 1: An overview of the combinations of frames (or bases) and measures covered in the literalure to date. SaFARi fills in missing combinations in this table for the scaled and translated measures in Section
Performance of various bases were shown to be strongly task-dependent. Only one basis-measure combination, the scaled-Legendre (LegS), performed empirically well across most tasks Gu et al 2020). but it introduced additional challenges as its A matrix is not stably diagonalizable (Gu al. 2022a The majority of the follow-up work since HiPPO has abandoned the task of function approximation by SSMs alone. Instead, most research has employed diagonal approximation of the best-performing extant version (LegS) as initiolization for machine learning architectures such as S4 (Gu et al. 2022b Smith et al. 2023). Still, the HiPPO framework still holds untapped potential for online function approximation and better initializations for learning tasks.
3 Mathematical Preliminaries
Prior to introducing SaFARi, we first cover some required Cheoretical background on the use of frames for function representation and approximation. This section will cover distinctions between approximations performed on the full signal all at once, and approximation performed in soquential (online) fashion.
3.1 Function representation using frames
Given a function u(f) of a time domain E Dr, we aim to represent u(t) using a collection of functions over Dr. This representation is performed with respect a measure that determines the relative importance of the function's 's value different times. We formulate the task of function representation using frames via the definitions below.
Frame: The sequence t = ='nn)er is frame in the Hilbert space H if there exist two constants A > 0 and B > 0 such that for any f H:
A
<
Σ KF. < Btrame || EET
where (...) is the inner product of the Hilbert space H. and denotes the indices of the frame elements in 4.
If Aframe = Brrames then the frame is said to be tight (Mallat] 2008 Christensen 2003 Gröchenig 2001).
Frame operator: the sequence = (du)ner is a frame, then its associated operator Up is defined as:
u On = (f.
Vn e
(8)
It can be shown that the frame condition (Eqq. is necessary and sufficient for the frame operator (Eq. to be invertible on its image with a bounded inverse. This makes the frame complete and stable (though potentially redundant) framework for signal representation.
Dual frame: The set T (en is the dual of the frame o, क (u) if:
Tm = (U on
(9)
where U% is the adjoint of the frame operator: (U+J, (ʃ. U..).

---

Published in Transactions on Machine Learning Research (10/2025)
It can be shown that the composition of the dual frame and the frame is the identity operator in the Hilbert
space H: U = MMallat 2008 Christensen
2003 Gröchenig 2001 Thus, we can think of the dual frame as the operator that transtorms the signal from frame representation back into the signal space.
The compressive power of frame-based function approximation lies in its ability to efficiontly represent functions using a relatively small number of frame clements. Different classes of functions exhibit varying effectiveness in capturing the essential features of different signal classes. This efficiency is closely tied to the decay rate of frame coefficients, which can differ significantly between frames for a given input function class. As a result, selecting an appropriate frame is critical for optimal approximations while minimizing computational resources and storage space.
Function approximation using frames:
In the task of online function representation, we aim to represent function ur == (u(1), [0, T]} for any time T, using a frame & that has the dual and the domain L E D. To do so, we need an invertible warping function so that the composition of the frame and the warping function ((T)) includes the domain T]. Without loss of generality,
assume that the frame has the domain D& [0, 1), and use the warping (t)) @ (+). (If this is not the case, then and apply it beforehand.) To calculate the representation, the frame operator of dy acts on wr:
casily find another warping function to warp D& + [0,
Projection: c (TT uT, Ca = (uT, (/) f1" ((0)))((((()))))))
(10)
where k(t) is the complex conjugate of <(t). Then, the dual frame operator transforms the discrete representation back to the function wr:
Reconstruction: ur क (T)
uT(1)=
Σ (WT, 2a (TT
(11)
REL
Measures: Throughout this paper, we work with the Hilbert space consisting of all functions over the domain with uut) representing a measure as in Eq. and the inner product defined as:
/ ((t)u(t)u(t)dt.
(u, 1)
(12)
LED
We will consider both scaling and translating windows with uniformly weighted measures as described in Eq. and Fig. 2 and derive the SSMs for cach. We only implement uniform weighting schemes in this work for the sake of clarity and generalizability, as the weighting does not impact the SSM's derivation. The windowing function does impact the derivation, however, because it changes the limits of integration, and we provide frameworks for both scaled (with changing number of prior inputs) and translated (with a constant number of prior inputs). Given the combination of these generic models, one could create any arbitrary measure by combining the appropriate window with any desired weighting scheme as a function of t in Eq. 12
3
4 SaFARi
We now introduce generalized method for online function representation using arbitrary frames. We formulate the update rule for online approximation as a first-order linear differential equation following a state-space model, and provide templates for the uniform translated and scaled measures.
4.1 Formulation
For the given frame + (without loss of generality, we assume & has the domain D = [0. 1)), and an input: function u(T), the objective is to find the representation of the function using the frame similar to Eq. 10
Projection: (T) = (U+u). f"d u(t) (TT)) (t)((t)t.
(13)
Je=to
The representation vector aT) a vector with th component defined as above. We next find the derivative of the representation with respect to the current time T, and show that it follows a particular SSM for scaled translated measure.
6

---

Published in Transactions on Machine Learning Research (10/2025)
4.2 Uniform scaled measure: Mac
When the scaled measure (Psal() in Eq. 3) the representation generated by applying the frame operator to the observed history of the input wr(t) is
1 1 [ u(t) mm
cn (T)
( dt.
(14)
Definition 1. For given frame consisting functions on D, we define the auxiliary derivative of the frame Tg {Un her as collection having Un (t).
The auxiliary derivative of the frame is the result of the operator t ar Note that the auxiliary derivative of the frame is not necessarily frame itself and the frame condition in Eq. 7 does not necessarily hold for T4.
2 acting each individual frame element.
Theorem 1. For the represenlation defined in Eq. 14 the partial derivalive of ē with respect to T is
0 oT a =
- AdTT) + Bu(T), 1=1+UrU3
(15)
where B is the complez conjugate of a vector containing members of the main frame evaluated at T = 1 so that = (T = 1))mer. The A operator can also be described as matric
[
0 (t) 2.00
Ar = 5ú5 +
(t''')
(16)
1=1""
Proof is provided in the Appendix A.1 We will refer to the SSM with scaling measure as scaled-SaFARi.
4.3 Uniform translated measure: Per
When the translated measure is used (t)r(t) in Eq. 3) the representation resulting from applying the frame operator to the window of recently observed input ut(() is
u(t) C.(TT - (
f"
('-(T-0)
0) de.
(17)
Definition 2. For a given frame +- {Φn hner consisting of functions of time, we define the time derivative of the frame + = (d.. कe ())) as a collection of time derivatives of o, components.
Definition 3. For given frame + (er consisting of functions of time, the zero-time frame operator is similar to the frame operator but only acts on t instead of the integral over the entire domain:
Q+f=3 In = (( = (1=
(18)
Theorem 2. For the representation defined in Eq. 14 the partial derivative of č with respect to T is
a (T) - Bu(T). A= + Q+Q
(19)
OT
where B is the complez conjugale of vector containing members of the main frame evaluated al T = so
have B = (0,(T' 1))mer The A operator can also be described using the matria representation
Ar - (,,500 + /
C T 5e
J)(t))t
(20)
1=
Proof is provided in Appendix
A.2
We will refer to the SSM with scaling measure translated-SaFARii.

---

Published in Transactions on Machine Learning Research (10/2025)
HiPPO-LegS Matrix, N
10
SAFARi LegSS A Matrix bub-Block, N 10
250
500
L
1000
8
0
7.99
- -.07-
-1.08-
8
-1.66-
-1.52-
8
-1.92-
-2.01-
10-2
10"
10-2
10 -4
10
15.97
15.95
8.98
-2.52
15.97
-3.54
15.97
-4.69
10
10
10
16.4 86
17.97
10
16.86
17.92
9.95
16.88
17.97
9.99
16.88
17.97
10
Figure 3: HiPPO provides closed-form solution for the scaled Legendre (LegS) SSM. SaFARi provides a computed solution, where the accuracy depends on the discretization of the N L. frame. Larger gives a finer discretization of the basis vectors and thus a better numerical result.
4.4 SaFARi generalization of HiPPO
HiPPO provides exact, closod-form solutions for and B for a few specific basis and mcasure combinations. numerical
caused by discretization of the frame vectors into length L. Increasing L will provide matricos that converge toward the closed-form solution (see Fig. 33. When closed-form solution exists for the desired basis and measure (e.g., HiPPO-LegS for the scaled Legendre basis), then it is preferable to use it Gu et al. (2020) 2023 SaFARi provides a method for any basis/ measure where the closed-form solution might not exist. We also show that SaFARi preserves all of HiPPO's robustness to timescale when applied to a general frame in Appendix A.3
SaFARi replicates these A and B matrices within
While the numerical method described above could be applied to any differentiable of vectors, we require that the vectors form frame. Tf not, then projecting the input signal onto the given vectors is lossy and not invertible. More preciscly, the frame condition (Eq. 7 is necessary and sufficient for the frame operator to be invertible on ils image with a bounded inverse. This makes the frame complete and stable (though potentially redundant) framework for signal representation. Second, and most importantly for this work, if & does not meet the frame condition, then Eq. 9 does not hold, and the derivative of representation with respect to time cannot be calculated using only the current hidden stale.
5 Error analysis
This section describes the computational efficiency and accuracy concerns of SaFARi, including strategies for producing the dinte-dimensional approximation the complete dimenssadmmessinall SaFARi in Section 5.1 We analyze the errors introduced by these approximations Section 5.2
5.1 Truncation of frames
Section demonstrates how a particular SSM can be built from an arbitrary frame Φ. Since the input space for the SSM is the class of functions of time, no & with a finite number of elements can meet the frame condition (Eq. 7 since the true representation of the input signal infinito-dimensional. In practice, the representation reduces to the truncated representation. In this section, analyze the theoretical implications of truncated representation using SaFARi.
5.1.1 Finite-dimensiona approximation of SaFARi
In the finite-dimensional case, we will use only N clements of a frame. Partial representation of size N requires that the resulting representation approxinates the infmite-dineeniooall representation. We call the SSM with its 7 having N coefficients (aFARi(N)
Note that HiPPO used the convention absorbing negative sign from the ODE Eq. into the matrix, whereas
8

---

Published in Transactions on Machine Learning Research (10/2025)
Definition 4. A (aFARi(N) sequence is sequence of the pairs [A(M), B(M] where A E CNN and B(M) E CN such that sequence converges to [A, B] of SaFARi as
lim A A, N-000
lim B(N) B. N
(21)
where convergence for A is the Strong Operator Topology (SOT) convergence, and convergence for B is the vector norm-2 convergence. This convergence means any arbitrary precision be achieved by selecting the appropriate truncation level. See Appendix A.5 for details.
Definition 4 is not a constructive definition; that is, it does not uniquely determine B(O). In fact, there may be many such sequences that converge to [A, BJ. Of course, this does not mean that all such sequences would produce equal representation error. For the following section, we assume the convergence and present and analyze two alternate constructions. See Appendix A.5 for details.
5.1.2 Truncation of dual (ToD)
The ToD construct of SaFARi(N) sequence begins with the infinite-dimensional A and B, then truncates to size N as
A = Ap.N.O.N] B(N) = BBo.N)-
(22)
This construction results in a sequence that approximates the anfnite-dimensionn SaFARi according Definition In practice, we find the truncated A, B via Ar, introduced in Eq. 16 and Eq. 20 for i,j N.
Calculating Ar, requires finding X, the dual of the (iinitt-dimensionna) frame Φ. For certain families of functions, the dual frame can be found analytically. However, if an analytical dual frame & is not known, then one must use numerical approximation of the dual frame. In this case, the construction for [A(M), (,,,B(M B(N] involves forming the truncated frame for much bigger size N₂ N, then finding (Na) Dual (o: numerically as an approximation for the dual frame (#()2 x D). Next, we truncate the approximate dual and use its first N elements as an approximation for size N dual frame in Eq. 16 and Eq. 20
5.1.3 Dual of truncation (DoT)
The ToD construction becomes numerically intractable for cases where the dual frame is not analytically known; this motivates the need for an alternate constructor for SaFARi(N), To construct this sequence
Truncate the frame at level and form ((N) = f
Numerically approximate the dual of the truncated frame ((N) Dual(g(()) using the pseudo- inverse.
Use (N) and (N) in Eq. 16 or Eq. 20 to compute [A(N), B(N)).
The DoT and ToD constructions approximate SaFARi with different rates. In the next sections, we provide a thorough error analysis of SaFARi that enables us to compare the usage of different frames, as well different construction methods for size N constructs. We then demonstrate that the DoT construction always has minimum reconstruction error, and is the optimal choice for implementing SaFARi.
5.2 Error analysis
Using truncated representations for online function approximation will result in some reconstruction error, regardless of basis. We focus here on errors emanating from truncation of the representation in an SSM, rather than those caused by sampling, which have been extensively studied in the digital signal processing literature [Oppenheim| 1999).
Let (00 denote the infinite-dimensional representation obtained from an SSM without truncating associated A, B matrices. When the associated A. B matrices for the SSM are truncated to the first N levels, it produces truncated representation (N)) This truncation causes two distinct types of error, which we outline below.

---

Published in Transactions on Machine Learning Research (10/2025)
5.2.1
Truncation errors
Truncation errors are due to fact that the truncated frame of size N cannot represent any part of the signal contained in indices N. This is not limited SSMs, but is true for any basis represenlation signal. SaFARi, truncation errors correspond discarding the green shaded region in the A illustrated in Fig. 4
N
5.2.2 Mixing errors
Mixing errors arise from error propagation the SSM update rule. Specifically, this update involves computing Ac (as in Eq. 15 and
A
Mixing
Eq. 19 where the matrix A introduces unwanted mixing between the omitted components (n >> N) and the retained components (n S N) of the representation. Consequently, errors from the truncated portion of the representation propagate into the non- tuuntrrd portion. This is illustrated by the blue shaded regions Fig. For the operator A and truncation level N, the contaminating part of the operator Vii N, N).
N
Truncation
In the case of translated measure, this mixing error is exacerbated since each update step requires estimating the initial value in that window (recall Eq. 2 A key insight from our analysis below is that mixing errors have two sources:
Figure 4: Error types due to frame truncation. Truncation errors arise from energy in coefficients of index n > N, while mixing errors result from energy blending during the operation Ac.
1. nonzero components in the upper right quadrant of A, and nonzero coefficients in indices greater than N.
5.2.3 Mitigating errors
Truncation errors can never be eliminated, but may be alleviated by using frame that exhibits a rapid decay in the energy carried by higher-order levels of representation.
To counter mixing errors, we should ensure that values in the upper right quadrant of are as close to zero possible, and/or that coefficents of in the blue region of Fig. 4 are close to as possible. Tf the matrix A is lower-triangular, then any arbitrary truncation results in the contaminating part of A being zero, which guarantees the second type of error is always zero, regardless of any coefficients in This is the case for the HiPPO-LegS (scaled Legendre) A matrix, as shown in Fig. 5(a). Indeed, the zero coefficents in the upper right quadrant of were considered strictly necessary in prior work (Gu et al. 2020 2023). This restriction explains the continued use of HiPPO-LegS Legendre polynomials are an optimal choice for given application.
follow-up works, regardless of whether or not scaled
To summarize, there are two primary concerns when finding appropriate frame for in SSM:
(a) Scaled Legendre
(b) Translated Legendre
(c) Scaled Fourier
(d) Translated Fourier
50
500
Figure 5: Examples of the A matrices for several basis/mcasure combinations: (a) Scaled Logendre, (b) Trans- lated Legendre, (c) Scaled Fourier, and (d) Translated Fourier. The dense non-zero elements in the upper right of (b) explain its poor performance compared to (a). The numerous small nonzero elements above the diagonal in (c) and (d) contribute to mixing errors over long sequences.
10

---

Published in Transactions on Machine Learning Research (10/2025)
1. compatibility between the frame and the given class of imput signals, and the operator A that results from a given frame has a small contaminating part.
Truncation and mixing errors have different sources but linked. The optimal strategy to reduce both at the same time is to choose basis that results in representation where the energy is concentrated in the first N coefficients. This can only be achicved, however, if we have some prior knowledge of the input signal in order to choose the right. basis and truncation level. In cases where little known about the input signal or correct truncation level, it is advisable to instead choose an SSM that is zero in the upper right quadrant, such as HiPPO-LegS, as it will inherently negate mixing errors.
5.2.4
Error bound
In order quantify the mixing error, we show that the truncated representation follows the same differential equation with a perturbation defined by the theorem below.
Theorem 3. (Poof in Appendia: A.G) The brancated represenlation generaled by scaled SaFA Ri follows a differential equation simalar to the full representation, with the addition of a perturbation factor:
1 - a 1 Ac+ + - 1 [E(T)
-
ØT c -
(23)
where
(T) = (WT,E),
\= 1).
(24)
The mixing error term ε(T cannot be directly calculated; however, we derive upper bound for the mixing error and demonstrate that this bound can be made arbitrarily small with appropriate truncation. This generic error bound is not necessarily tight; tighter bounds could be identified for specific instantiations of SSMs for given parameters (frame or basis, measure, dimension, etc.)
Theorem 4. If one finds upper bound such that for all the times before T have ||e(T))le Em, then the representation error is bound by
1 | cm Σ Σx -m
(25)
where >i are the eigenwalues of A, and F indicates the Frobenius norm.
See proof in Appendir A.6
5.2.5 Error analysis for different (aFARi(N) constructs
define SaFARi(N) finite dimensional approximation for SaFARi, and provide two particular rucstouc DoT and ToD. Armed with the quantification of representation error, compare these different constructs. We provide Theorem to demonstrate DoT has the optimal representation error between different choices for (aFARI(N) using the same frame.
In Section 5.1.1
Theorem 5. Given frame 4, the Dual of Trancation (DoT) construct introduced in Section 5.1.3 has optimal representation error when compared to any other SaFARR()) construct for the same frame o. See proof in Appendir A.6
As established in Theorem 5 SaFARi(M) SSMs should be constructed with the DoT method.
6 Computational and runtime complexity
This section develops the computational methods for obtaining sequence representations with SaFARi, emphasizing its efficiency in both training and inference phasos. We analyze the computational complexity of different update methods, and highlight the benefit of parallel computation with diagonalizable SSMs. These discussions provide foundation for understanding the scalability of SaFARi in practical applications.
11

---

Published in Transactions on Machine Learning Research (10/2025)
6.1 Computational complexity for sequential updates
To compute representations using scaled-SaFARi, the GBT update requires solving an N N linear system at cach step, leading to L() complexity for a sequence of length L. In contrast, translated-SaFAAR reuses the same inverse across all steps, reducing the complexity to O(N²L).
If the state matrix A is diagonalizable, both scaled and translated variants can be accelerated. The sequence representation C is computed for the diagonal SSM and transformed back via C = VC, roducing the complexity to (). On parallel hardware, such diagonalized systems decompose into N independent scalar SSMs, yielding (T.) runtime with sufficient parallel resources.
Diagonalizability of an SSM depends on the frame or basis used in its construction. One limitation of Legendre- based SSMs such HiPPO is that its A matrix cannot be stably diagonalized, even for representation sizes small N = 20 (Gu et al. 2022a leading to significantly higher cost. To address this limitation, (Gu et al. 2023) proposed a fast sequential update method for HiPPO-LegS, claiming O(N) computational complexity and (1) runtime complexity per update on parallel processors. However, we observe that this method becomes numerically unstable at larger N, as discussed in Appendix [A.7.I] To resolve this, we suggest a simple modification: computing lower-degree representations before higher-degree ones. While the modified approach preserves the O(N) overall computational cost, it increases runtime to O(N) per sequential updale, as it is no longer parallelizable.
Similar to HiPPO-LegS for the scaled mcasure, HiPPO-LegT for the translated measure also cannot be stably diagonalized. To our knowledge, LegT has no analogue for the fast LegS update method in Gu el al. (2020) Therefore, the computational complexity remains considerably higher than for diagonalizable SSMs.
6.2 Convolution kernels and diagonalization
When using an SSM for recognition learning task, training phase is required in which the downstream model is trained on the generated representation. Using sequential updates for training is prohibitively taxing on computational and time resources as the whole sequence is available in the training time. Ideally, we
would perform computations of the sequential SSM in parallel. However, this is a challenge since each new update depends on the result of the previous. The authors of Gu et al (202bb) discussed how to implement a parallel computation algorithm for SSMs produced by HiPPO. To do so, one "unrolls" the SSM as:
Ck A& ... A, + ..... AB + BRUE c c= K
(26)
A (I 8la.A,) -1 51(1 (1)(1-))A)) A.),,,
B== )1)
(27)
The convolution kernel K in Eq. 26 removes the sequential dependency, enabling parallel compulation on hardware such GPUs, and significantly reducing training time.
6.3
Runtime complexity
6.3.1 Runtime complexity of scaled-SaFARi
If the SSM is not diagonalizable, then the kernel can still be computed in parallel by framing the problem as a scan over the associative prefix product. Since matrix multiplication is associative, all such prefix products can be computed efficiently using parallel scan algorithms (Blelloch 1990 Hillis & Jr. 1986). When implemented on parallel hardware such as GPUs, this strategy achieves a time complexity of O(N log L) if enough parallel processors are available.
However, if the SSM is diagonalizable, all the matrix products Ag matrices in the matrix products appearing in the kernel expression become diagonal. As a result, the convolution kernel can be calculated with the time complexity of ONN log L). Furthermore, the below theorem suggests how to find the kernel in closed form.
Theorem 6. For scaled- SaFARi, if A is diagonalizable, then the convolution kernel K that computes the represeniations can be found in closed form. See. Appendir A.7 for the closed-forn solution.
12

---

Published in Transactions on Machine Learning Research (10/2025)
Name
Spans L2
Orthogonal
Redundant
Category
Legendre
X
Orthonormal Basis
Laguerre
X
Orthonormal Basis
Chebyshev
V
X
Orthonormal Basis
Fourier
/
X
Orthonormal Basis
Bernstein
X
X
Non-orthogonal Basis
Gabor
X
V
Frame
Random Harmonics
Neither
Fourier-Randdn Harmonics
X
Frame
Table 2: The first. four elements in this table were studied in previous works (Gu et al. (2020 2023 We reproduce them here for comparison. We also introduce several new variants with characteristies such non-orthogonality and redundancy, which can now be handled with SaFARi.
As noted above, HiPPO-LegS is not diagonalizable, complicating kernel computation. heuristic method proposed by Gu et al. (2023) enables approximate kernel evaluation with time complexity O(N log L), but it introduces additional computation and lacks closod-form solution.
6.3.2 Runtime complexity of Manslated-SaFAAR
Similar to the scaled case, all the matrix products A Ag-m can be computed efficiently using parallel scan algorithms (Blelloch 1990 Hillis & Jr. 1986). As a result, the convolution kernel K can be computed with an overall time complexity of ON log (L) since As remains the same for all values of k. Similarly to the scaled case, if the matrix diagonalizable, then the A matrices become diagonal. With access to parallel processors, the runtime complexity can be reduced to O log(L)).
Furthermore, for diagonalizable SSMs, the convolution kernel for the translated measure has a closed form.
Theorem 7. For translated-SaFAl if A is diagonalizable, then the convolution kernel K that computes the representations can be found in closed form. See Appendir A.7.
7 Empirical validation
We demonstrate that SaFARi generate SSMs for function approximation any frame basis by choosing examples that are non-orthogonal, incomplete, or redundant. We then evaluate SaFARi-generated state-space models on some sample datasets online function approximation, benchmarking against established baselines. Code to replicate the results of this section, as well as generate SSMs with arbitrary frames is provided at: https:///ithhni wwt.:ccoccccccceeeee www.////aaaa////coooooccoaaaaaaa safaaiissaaar-aiaaia
7.1 Instantiations with different frames
No single frame is universally optimal all imput classes. Different signal families exhibit different decay rates in representation error depending on the chosen frame or basis. We instantiate SaFARi over several sets of functions as in Fig. G which may constitute bases, frames, or neither, as summarized in Table 2 Description and further discussion can be found in Appendix A.8 For each function family, we scale the functions to an interval of [0, 1].
7.2 Diagonalization of A
As discussed in Sec. 6.3 not bases produce an A matrix that stably diagonalizable. This section does not attempt provide rules guarantoe stably diagonalizable A. However, we consider two key metrics that illustrate how the choice of basis and measure can result an matrix with more (or less) desirable properties: how sensitive eigendecomposition is to perturbation, and the effective rank of A.
13

---

Published in Transactions on Machine Learning Research (10/2025)
From the Bauer-Fike theorem [Bauer & Fike (1960)), ) given matrix A with eigenvalues X and eigenvectors V, and perturbed matrix A A + with corresponding eigenvalues X, we have tha
j x- (V)
(28)
where x(V) || This theorem describes relationship between matrix perturbation and the impact on its eigenvalues, which has a bound delermined by the condition number of the eigenvectors of A. The larger this value, the less numerically stable the operations on A will be. Varying N for different SaFARi instantiations can result in unstable diagonalization of A matricos, as shown in Fig. 7
<(V) gives some information about the stability of the eigenvalue decomposition, but does not address structural issues such degenerate eigenvalues. To address this, we consider the effective rank, defined by Roy & Vetterli (2007) as the Shannon entropy of the normalized singular values Pk- The closer this value is to N, the less redundancy of eigenvalues.
erank = exp
P& log
(29)
k=1
While these metrics may not account for all possible edge cases, general, we would like the matrix to have a very low value for x(V) and a high value for erank. Notably, in Fig. 7 several the orthogonal polynomials of prior work are suboptimal, whereas some of our newly-introduced frames (which can only be constructed via SaFARi, having no closed-form solution) show improvements in both metrics.
7.3 Datasets for experiments
We use the daily S&P 500 index as a broad, large-cap U.S. equities benchmark over the last decade: from August 2015 August 2025 (Yahoo Finance (0225)). The series consists of end-of-day levels for the price index. Overlapping sequences of 500 samples are collected different instances of time series to form dataset, and resampled into 4,000 samples to emulate longer time-series signals.
S&P 500:
TThe norm || || in Eq. 28 can be any p-norı, e.g. 1, 2, or oc. The 2-norm was used here, which denotes the largest singular
value of E.
Legendre Polyuomials
Scaled
Transated
Fourier
Staled
Transltedd
1000000
50
0.5
30
Chehyshev Polynorails
A Scaled
A Translated
Razdom Harmonies
A Scaled
A Tranclated
10
Laguere Polynomials
Postriin: Randlom Frame
Staled
Translated
0.5
10
0.5
Berusteia Polynomiale
A Staled
Trandated
Gabor Filters
A Scaled
A Trandated
0.2
30
A Am Amah
0.5
-0.2
50
Figure For each of the SSMs instantiated in this work, we show few elements of the frame, and the resulting A matrices for scaled and translated measures. The scale for the A matrices is the same in Fig. for consistency.
14

---

Published in Transactions on Machine Learning Research (10/2025)
Condition Number Figenectors of
Effoctive Rank of
10
LegS
LegT
FouS
1044
FouT
ChebyS
x(V)
CbebyTT
1010
Lag8
LagT
Bem8
10
Bon'T
Gah8
GabT
10 10
20
30
40
50
00
70 10 20
30
40
50
70
N (dimension of A)
N [dimemsion of A)
Figure 7: Comparison of A matrices produced by different frames via SaFARi. The condition number of cigenvectors of A indicates how sensitive the diagonalization is to perturbations, and the effective rank relates to the distribution of eigenvalues. Our results support the findings of prior work in Gupta et al. (2024); Gu jtt al. (2022a), noting that at. relatively low N, Tegendre-based A matrices rapidly become difficult to stably diagonalize, but other frames (such as Fourier and Gabor) do not.
M4: The M4 dataset consists of collection of time-series data across different realms, including economic, financial, industrial, and demographic, various intervals.
7.3.1 Function memorization and approximation
Members of the M4 and S&P 500 datasets were passed SSMs constructed from differ- ent bases and frames. At each iteration, the SSM generates coefficient vector (see Fig, [ Eq. 13 and subsequent equations) which is a compressed representation of the time-series signal up to that point. The error between the reconstructed signal from e and the original input signal is a measure of how effectively the SSM can remember and represent the signal. An illustration based on single instance of M4 is shown in Fig. 8
Recoustruction by Fourier Basis and Harmonics
Signal
Fourier
Harmonies
Fourier
Harmonics
2,000
4,000
6,000
8,000
10,000
Recoustruction by Polynomial Families
10
2
Signal
Laguerre
Chebyshev
Legendre
Scaled and translated SSMs: For the trans- lated case, the window size is sot at 10% of the input signal length. Since we are only estimat- ing a small portion of the signal each time we evaluate the translated casc, the MSE reported is the mean of all intermediate estimates. For consistency, the error in the scaled case is mea- sured the same way. The MSEs between the reconstructed signal and the estimated signal are reported Table 3
2
2,000
4,000
6,000
8,000
10,000
Reconstruction by Non-orthogonal Frames
Signsl
Gabor
Bernstein
0
2,000
4,000
6.000
8,000
10,000
Both scaled and translated versions were evaluated with N 32, 64, 128, where N is the size of the signal representation. For orthonomal bases, basis elements are lin- early independent, so both basis and A matrix have rank N. For frames, elements have redundancy, so the SSM has effective rank Not < N. In Table 3 the two frames (Fourier+Randoo Harmonics and Gabor) are treated scparately to highlight the distinction. We first instantiate these frames with N member vectors (Fou+, Gabor). We then add N > member vectors and diagonalize the resulting A matrix, so that the resulting (Nar) matches the desired N (Fou+*, Gabor*).
Size and Rank:
Figure 8: One sample from the M4 datasot reconstructed by different SaFARi implementations. These are separated into multiple subfigures for visibility.
15

---

Published in Transactions on Machine Learning Research (10/2025)
Scaled
Translated
N 32
N
64
N
128
.V
32
N 64
N
128
SP
M4
SP
M4
SP
M4
SP
M4
SP
M4
SP
M4
Leg
0.039
0.328
0.039
0.322
0.039
0.322
0.166
0.288
0.166
0.287
0.166
0.289
Fou
0.018
0.218
0.013
0.159
0.009
0.109
0.314
0.271
0.314
0.270
0.314
0.271
Lag
0.678
0.712
0.678
0.709
0.678
0.712
0.313
0.271
0.314
0.207
Cheby
0.015
0.162
0.013
0.117
0.012
0.077
0.021
0.179
0.024
0.176
0.030
0.181
Bern
0.026
0.194
0.020
0.173
0.017
0.158
0.021
0.179
0.021
0.174
0.021
0.178
Rand
0.026
1.175
0.020
0.563
0.014
0.249
0.022
0.179
0.023
0.176
0.026
0.179
Fou+
0.017
0.191
0.011
0.152
0.009
0.109
0.021
0.179
0.023
0.175
0.026
0.180
Fou+*
0.013
0,156
0.009
0.101
0.007
0.058
0.022
0.179
0.025
0.176
0.027
0.181
Gabor 0.024
0.266
0.018
0.191
0.714
0.206
0.021
0.179
0.022
0.175
0.023
0.179
Gabor*
0.018
0.223
0.016
0.181
0.051
0.144
0.022
0.179
0.022
0.175
0.024
0.179
Table 3: MSE of reconstructed signals with different instantiations of SaFARi. The table is divided into polynomial (top) and non-polynomial (bottom) representations. Asterisks indicate that the frame was augmented with additional vector elements to achieve an effective rank. For each test, the minimum MSE for polynomial and non-polynomial SSMs is shaded. Missing entries for Laguerre could not be computed due to numerical errors arising from exponents in higher-order terms. The standard deviation is reported in Appendix A.9.
Discussion: In Table 3 the lowest MSE depends on combination of N, the windowing function, and the data being processed. However, some broad patterns emerge. Most of the best-performing SSMs have characteristics of redundancy (Fou+, Fou+*, Gabor, Gabor*) or non-orthogonality (Bernstein), which were never explored in prior work due to their lack of a closed-form solution for and B. This suggests that alternative SSMs constructed via SaFARi could improve the performance of SSM-based models.
We also observe that the representative power of given SSM depends in part on the length of the signal under consideration. In the translated case, the window size is constant, so any SSM that can adequately model features in a signal of length W will have negligible performance advantages. In the scaled case, however, the length of the signal changes at each iteration, and the choice of frame or basis for SSM can have a significant impact on MSE.
Ultimately, the choice of basis or frame is task-dependent, and different representation structures will perform better or worsc, depending on the signal's features. No single SSM is universally optimal for all signal typos. However, given our observations regarding redundancy and non-orthogonality, wavelets are natural choice. It. was found in Babaei et al. (2025) that Daubechies wavelets can generally outperform soroomlll-bssee HiPPO SSMs for time-scries signals, especially when those signals contain discontinuities or other non-idealities.
7.3.2 Comparing SSMs to learned structures in the long horizon delay task
To compare the performance of SaFARi SSMs as online memory units, SaFARi features are computed on a signal by sequential update, then the observed scalar input at t= T= T- d (where is the current time sample and d is the delay) carlier reconstructed from the representation via the dual frame. The MSE between the reconstruction and the ground truth delayed input is an indicator of the memory performance of the structure, as it demonstrates that information in the long history horizons is recoverable. For each test, we use the same delay amount and the same representation size of 32. The SSM-based models in our study do not include any learned parameters; their dynamics are fully determined by the state-space formulation, so their number of learnable parameters is effectively zero. The LSTM and GRU models are trained using an Adam optimizer (Kingma (2044) until they converge, and the final validation performance shown in Fig, 9
Discussion: The trends in Fig. 0 reffect how SSM-based models demonstrate better memory performance than learnable models for the same representation size. Models with learnable parameters (LSTMs, GRUs)
16

---

Published in Transactions on Machine Learning Research (10/2025)
S&P 500 Dataset
M4 Dataset
LSTM GRU
10-2
10
SaFARi- RiChbbbseyy
SaFARi Gabor
2.2
HiPPO-Legenee
10
H6PPO-Fourre
10-2
244
10
0
500
1,000
1,500
2,000 2,500 3,000
3,500
500
1,000
1,500
2,000
Delay
Dolay
Figure 9: Memory recall performance of learned models, HiPPO SSMs, and SaFARi SSMs in the long horizon delay task. Legendre and Chebyshev SSMs are nearly indistinguishable. Gabor and Fourier also track closcly.
need large amounts of data to generalize well. When the delay horizon is long and the available data is limited, these models tend to perform worse. This consistent with our observation that the gap between RNNs and SSMs is smaller for the M4 dataset, which has many more samples, compared to the S&P 500 dataset. Even in data-rich scttings, RNNs prioritize short-term dependencies because of their internal gating mechanisms and training dynamics, which helps avoid vanishing exploding gradients. This bias limits their ability to retain information from long time horizons. In contrast, SSM models are designed to maintain information flow over longer sequences.
Another notable trend in the plots of Fig the varying MSE as the delay increases. Intuitively, at longer delays, the memorization task becomes more difficult, and we expect the MSE to increase. The MSE does increase overall, but not strictly monotonically, and this is especially salient for the SSM models. If the underlying time series exhibits non-monotonic autocorrelation structure, then periodic quasi-periodic components cause the signal at specific lags to be more correlated (and thus more predictable) than at nearby lags, which is often the case for real-world signals Kantz & Schreiber (2003). SSM models also contain structured ionstions that exhibit periodicity (see Fig. G). whereas learned models do not necessarily converge to periodic representations. Thus, the same structure that gives SSMs an advantage in MSE performance can also make them more susceptible to periodic correlation in delay and copying tasks.
8 Conclusions
In this work, we demonstrate how our method, SaFARi, generalizes HiPPO (Gu et al. [2020) to accommodate bases or frames where closed-form solutions are unavailable, paving the way for broader applicability in sequential modeling tasks. Key findings of this work regarding the choice of frame or basis of an SSM motivate the need for more flcxibility than prior methods could provide:
The underlying frame of the SSM should be compatible with the signal of interest; there is no *one size fits all The correct choice of frame reduces both the error and representation size (Sec.
Notably, SSMs using non-orthogonaa and redundant frames which do not have closed-form solutions-can can outperform the standard polynomial-based instances (Sec.
Even for optimal frame, an SSM's performance will also depend structural features of the A matrix (Sec. 5.2h. Different frames result in A matrices with better or worse numerical properties (Sec. 7.2 and stable diagonalization of the A matrix is critical for computational
efficiency (Sec. 6.3
The groundwork laid this paper lends itself naturally to several future research directions. One considers SaFARi as a standalone representation module. While we have presented several new frames and bases this work, there are many other structured frames, such different wavelet types, that could be leveraged for localized and sparse representations.
17

---

Published in Transactions on Machine Learning Research (10/2025)
Another direction focuses on the integration of SaFARi into learned models, specifically advanced SSM architectures such as S4 and Mamba. By embedding known temporal structures of dynamical systems directly into the SSM architecture with SaFARi, we can improve memory and reconstruction performance of the core SSM, which in turn reduces the need to learn all parameters from scratch. We anticipate that this will reduce the computational burden of training, while increasing stability and parameter efficiency. SaFA Ri is also a natural candidate for implementing gating-like behavior: the memory encoded in the state vector determines how historical information is selectively integrated into downstream computations. In this sense, SaFARi modules could function analogously to gating layers in RNNs, but with efficiently designed, context-aware structure.
SaFARi also enables us to investigate the synergy between ML models and SSM variants. The interplay between the internal structure of the SSM (from the frame and measure) and the architecture of the learned model that contains may play an important role overall performance. For example, a wavelet-basod SSM that detects discontinuities signals may have better synergy with models designed for sparse data, whereas polynomial-based SSMs techniques may be better suited for with techniques involving logistic regression.
By extending SSM construction beyond specific bases, SaFARi provides flexible foundation for efficient state-space representations by linking theoretical advancements to practical applications in sequential data processing.
Acknowledgments
The authors thank T. Mitchell Roddenberry for fruitful conversations over the course of this project, and Matt Ziemann for assistance with code development. This work was supported by NSF grants CCF-1911094, IIS-1838177, and IIS- IIS-1730574; ONR grants N00014-18-122 1--777,, N00014-20-1-22 1-234, N00014-18-1-2047; MURI N00014-20-1-2787, AFOSR grant FA9550-22-1-0060, and DOE grant DF-SC0020345. Additional support came from Vannevar Bush Faculty Fellowship, the Rice Academy of Fellows, and the Rice University and Houston Methodist 2024 Seed Grant Program.
References
Agostino Abbate, Casimer DeCusatis, and Pankaj K Das. Wavelets and Subbands: Pundamentals and Applications. Springer, 2012.
Sina Alemohammad, Hossein Babaei, Randall Balestriero, Matt Y. Cheung, Ahmed Intiaz Humayun, Daniel LeJeune, Naiming Liu, Lorenzo Luzi, Jasper Tan, Zichao Wang, and Richard G. Baraniuk. Wearing a mask: Compressed representations of variable-length sequences using recurrent neural tangent kernels. In 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 2950-2954, 2021.
Hosscin Babaci, Mel White, Sina Alemohammed, and Richard Baraniuk. WaLRUS: Wavelets for long range representation using state space methods. In The Thirly-ninth Arceual Conference on Neural Information Processing Systems, 2025.
Friedrich L. Bauer and C. T. Fike. Norms and exclusion theorems. Numerische Malhemalik; 2:137 141, 1960.
Guy E. Blelloch. Prefix sums and their applications. Tochnical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University, 1990.
George EP Box, Gwilym M Jenkins, Gregory C Reinsel, and Greta M Ljung. Time Series Analysis: Forecasting and Control. John Wiley & Sons, 2015.
John Charles Butcher. The Numerical Analysis of Ordinary Differential Equations: Runge-Kuul Kutta and General Linear Methods. WilleyInnterccience 1987.
Kyunghyun Cho, Bart Van Merriënboer, Caglar Gulechre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. Xiv preprint 1406. 1067188, 2014.
18

---

Published in Transactions on Machine Learning Research (10/2025)
O Christensen. An Introduction to Frames and Riesz Bases. Birkhauser, 2003.
Jeffrey L. Elman. Finding structure in time. Cognilive Science, 14(2):179 211, 1990.
Alex Graves and Jürgen Schmidhuber. Framewise phoneme classification with bidirectional LSTM and other neural network architectures, Neurol Networks, 18(5):602 610, 2005.
Karlheinz Gröchenig. Foundations of Time- Free-eeey Analysis. Springer, 2001.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint arXiv:2312.00752 2023.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. HiPPO: Recurrent memory with
optimal polynomial projections. In Advances in Neural Information Processing Systems, 2020.
Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the parameterization and initialization of diagonal state space models. In Advances in Newral Information Processing Systems, 2022a.
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference Learning Representations, 2022b.
Albert Gu, Isys Johnson, Aman Timalsina, Atri Rudra, and Christopher Re. How to train your HiPPO: State space models with generalized orthogonal basis projections. In International Conference on Learning Representations, 2023.
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective structured state spaces. In Advances in Neural Information Processing Systems, 2024.
Ramin Hasani, Mathias Lechner, Hsun-Hsuan Wang, Makram Chahine, Alexander Amini, and Daniela Rus. Liquid structural state-space models. In International Conference on Learning Representations, 2023.
W. Daniel Hillis and Guy L. Steole Jr. Data parallel algorithms. Communications of the ACM, 29(1)) 1170 1183, 1986.
Sepp Hochreiter and Jürgen Schmidluber. Long short-term memory. Newral Compulation, 9(8):1735 1780, 1997.
Rudolf E. Kálmán. new approach to linear filtering and prediction problems. Basic Eng., pp. 35 46546, March 1960.
Holger Kantz and Thomas Schreiber. Nonlinear Time Series Analysis. Cambridge University Press, 2 edition, 2003.
Diederik P Kingma. Adam: method for stochastic optimization. arXiv preprint orXiv:1412.6988 2014.
Stéphane Mallat. A Wavelet Tour of Signal Processing: The Sparse Way. Academic Press, 3rd edition, 2008
Eric Nguyen, Karan Goel, Albert Gu, Gordon Downs, Preey Shah, Tri Dao, Stephen Baccus, and Christopher Ré. S4ND: Modeling images and videos as multidimensional signals with state spaces. In Advances in Neural Information Processing Systems, 2022.
Alan V Oppenheim. Discrete-Time Signal Processing. Pearson, 1999.
Razvan Pascanu, Tomas Mikolov, and Yoshua Bengio. On the difficulty of training recurrent neural networks. In Proceedings of the 30th International Conference Machine Learning, volume 28, pp. 1310 1318, 17 19 Jun 2013.
Paolo Prandoni and Martin Vetterli. Signal Processing for Communications. EPPL Press, 2008.
John G Proakis. Digital Signal Processing: Principles, Algorithmss, and Applications. Pearson, 2001.
19

---

Published in Transactions on Machine Learning Research (10/2025)
Olivier Roy and Martin Vetterli. The effective rank: A measure of effective dimensionality. In 15th European Signal Processing Conference, pp. 606-610, 2007.
Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE Transactions on Signal Processing, 45(11):2673-22 2281, 1997.
Jimmy T.H. Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for sequence modeling. In International Conference on Learning Represenlations, 2023.
Aaron Voelker, Ivana Kajić, and Chris Eliasmith. Legendre memory units: Contimuous-tine representation in recurrent neural networks. In Advances in Neural Information Processing Systems, volume 32, 2019.
Yahoo Finance. S&P 500 index historical data. https://finaance.yahhh http://awwaaaaaooooo//////////aa 2025. Accessed: 2025-09-04.
Guofeng Zhang, Tongwen Chen, and Xiang Chen. Performance recovery in digital implementation of analogue systems. SIAM Journal on Control and Oplimization, 45(6):2207 2223, 2007.
Nikola Zubié, Mathias Gehrig, and Davide Scaramuzza. State space models for event cameras. IEEE/CVE Conference on Computer Vision and Pottern Recognition, 2024.
A Appendix
A.1 Derivation of SaFARi with the scaled measure
Theorem I Assuming elements in the frame & and the input signal are right for the representation defined in Eq. 14 the partial derivative is:
OT (T) = T
ACT) + Bu(T)
(A.1)
where A a linear operator defined as:
1
(A.2)
and B is the compler conjugate of a vector containing members of the main frome evaluated at T 1 we have B = (T, 1))ner One can show that the A operator can also be described using the matris
multiplication:
Ars = deg + S.' v,(0)5(())
(A.3)
Proof: Taking partial derivative with respect to T, we have:
a
T [
0T 1=0 T =n(()n
T dt
(A.4)
0T
Now applying the Leibniz integral rule we have:
['
T -1
-1
t
t
)tt + (1(
OT (T)
(T)
u(t)
dt
u(t)
u(T)
1:=0 7 =
T
t=0
T
T
T
T
1
t
dt + T (1)
On +
u(t))
Un
TTT)
T
T
1=0
T
T
T
-1
(1) T(T)
On +
(u, vn) +
(A.5)
T
T
T
This is still not SSM since the second term is not explicitly linear form of (T). To convert this to linear form of (()), we use the equality given in Eq. 11 to represent vn using the frame T
(t)
Σ Jer
(un 25)55
Σ jer
(vnn F5)
(A.6)
20

---

Published in Transactions on Machine Learning Research (10/2025)
- (u, Un) = (u,
Σ (Uis x5)ور) = Σ
(Un, (y) 05) = Σ
Un Qy) cy())
(A.7)
Jer
JEr
JET
Putting Eq. A.7 in Eq.
A.5
results in:
(I) T (T)
(T) = --
(A.8)
This proves the theorem.
A.2 Derivation of SaFARi with the translated measure
Theorem Assuming elements in the frame & and the input signal are right-conttnnoos, for the represcntation defined in Eq. 14 the partial derivative is:
0 . aT)
1 AA(T) + Bu(T) -
(A.9)
where A is linear operator defined as:
+
(A.10)
and is the compler conjugate of a vector containing members of the main frame evaluated at T = 1 80 we have = (o,(T = 1)]eer. One can show that the A operator can also be described using the matrix multiplication:
/
- (t)
0 01
A. 2,00),
(t')
(A.11)
1=
Proof: We can write the coefficients as:
Gn (T) f
t t- (t-(T- (T (t-
8)
u(1)
dl
(A.12)
oo 0
Taking the partial derivative with respect to T, have
(c)(T)
-1 _ u(t)o' 8² T-B
t-- (T-(T-0)
1
1-
dt + 0 o (1)
(0)u(( - 0)
(A.13)
8T
0
Similar to our approach for the previous theorem, we write (=) as
(2)22 E(da (d))))))s(2)))
Σ Qn,i (z(2)
(A.14)
iET
Qu
By (2) (z)dz
(A.15)
==0
Now, if we use this expansion, and put in Eq.
A.13
we have
(C)(T) T
(T
0)
u(t)
dt + 2n (0)((T- - -8)
(A.16)
OT
0² T-B
0
LiET
dcn (T)
-1 Σ
tt- (T
1- 56 5 (T)u(T-))))) -
u(1)))
di
+ o (1)(()
(A.17)
ØT
n,
ser
T-0
We also write - 0) as a reconstruction using the current representation u(T A) = (,
)c,(T)
-1 Σ Qn, a
1- (1)()) - -0----/ -0 E
1-
(A.18)
OT
dc, (T)
Σ Cn. + +300,, 2 (1)
(A.19)
0T
If we put Ar Q., + ()))))(()) proves the theorem.
21

---

Published in Transactions on Machine Learning Research (10/2025)
A.3 Mathematical properties of SaFARi
Proposition. For wny scalar B > 0, if h(t) v(3)) then for the scoled measure we have Sa SaFARi(h)(T)
SaFA
Proof: We start by writing the representation generated by the scaled SaFARi for h(t).
SaFARi(b)(T))
h(1)@n
dt
(A.20)
T
u(B()on
T dl
(A.21)
1=0
[ y(l')nn t=0
1 dt'
= SaFARi(u)((T)
(A.22)
3T
T 3
Proposition. For any scalar >>0 0, if l(tt) = u(t)) then for the translated measure with parameter we have (a)) (u)
Similar to the previous proposition, we start by writing the representation of the scaled SaFARi:
t (T f)
(h) = T-
h(t)
0 dt
(A.23)
0
t (T
0)
w u(t))nn
0 dt
(A.24)
T-
0
3T
(1' (3T 300
1 di'
u(t))nn
(u)
(A.25)
J'=81
30
0
A.4
The closed-form solution for SaFARi differential equations
Lemma 1. The closed form solution for the differential equation indroduced in Fgg. 15 is:
T 1 exp (Aln 4) Bu(l)dl.
C c= -
(A.26)
Proof: We begin by re-writing the differential equation for any time t
at c(t + Ac(t) Bu(t)
(A.27)
Now we multiply both sides by exp(AAn(tt)
exp(AIn(tt) (t) + - exp (AI(()))(t)) exp(Aln(t)) 0t
(A.28)
The left side of the equality is now a complete differential
πt (exp(Aln(1)z(0) exp (Aln(()) Bu(l) Bu(()
(A.29)
exp (AIn(T)) /" exp (A)n())) Bu(t)
(A.30)
/ exp (Aln(() Bu(t) ==
(T) = exp (-Aln(7))
(A.31)
This proves Lemma. 1. 0
22

---

Published in Transactions on Machine Learning Research (10/2025)
Lemma 2. The closed form solution for the differential equation introduced in Eq. 19 is:
1 -
exp A (A'=7)
c= -
Bu(t).
(A.32)
Proof: We begin by re-wriling the different equation for any time as
δt dt + _ 0
a
- Bu(t).
(A.33)
Now we multiply both sides by exp(AA)
+ 7 A exp A (2))(0)))
0 exp (A)) Bull)
exp
A 0
a()
[()
(A.34)
ōt
The left side of the equality is now complete differential
0
exp
A
at) = 0 exp (1 Bu(t)
(A.35)
01
aT) = cxp (-11g
T
/
1=T-0 0 exp (1' Bu(t)
T
(A.36)
This proves Lemma
A.5
Truncation of frames
For a sequence of matrix operators to converge, there are different types of convergence, including operator norm convergence, Strong Operator Theory (SOT) convergence, and entry-wisc convergence. A sequence of operators A, said to converge to the Strong Operator convergence sense if An + A strongly if Vz (2:
AA,Pa Arl| +
(A.37)
Where Pa projects the vector x into vector containing only its first coordinates.
This type of convergence guarantees that for the SSM updates, [[A,ε(7) A - 0. This means that the difference between the true infinite dimensional update and the update using truncated A vanishes to have zero norm-2, guaranteeing that the representation error using SaFARi updates can be diminished to an arbitrarily small value.
Our implementations and empirical evidence support that the DoT and ToD constructs Section 5.] are (aFARi(N) sequences. The fact that our DoT constructs reproduce the closed-form HiPPO derivations for A and B also provide strong evidence for this framing of the construction. However, rigorous proof that that the two introduced structures meet the SOT convergence criteria is still needed, and should be addressed in follow-up work.
A.6 Error analysis
Theorem 3 The truncated representation generated by the scaled-SaFARi follows differential equation similar to the full represenlation, with the addition of perturbalion factor.
0T c= T
-
Ac
T
Bu(T) [T)
(A.38)
where is defined as
E(T) = ((UTEE)
(A.39)
T
(A.40)
23

---

Published in Transactions on Machine Learning Research (10/2025)
Repeat the steps taken in the proof of Theorem 1 until Eq. A.6 Truncating the frame results in error in this step which can be written as
Proof:
on (t) Σ
(un G2) + (t)
(A.41)
jer
In fact, this how & is defined. Adding & as a correction term here changes the SSM derivation:
+ (u, Un) (u, En +
Σ
(un و5)
(Mn (5) En)
Σ
(Uns (5) + (u, En)
(A.42)
jer
jer
jer
Putting Eq.
A.42 in Eq.
A.5
results in:
1 ① c A Bu(T) (TT)
(A.43)
ar
T
Theorem 4 one finds upper bound such that Vt < T have [|<(t)]22 Cm, then the representation ertor can be bound by
||cc(T]ll <
em Emp
Σ x
6m ||
(A.44)
Proof: Using the result of Theorem
3
0
0T = - Ac + (Bu(T) - -
(A.45)
We can use Lemma I to find the closed form solution of the perturbed SSM above
[" 1 exp AAm t 7
c=
(Bu(t) - [(t) dt
(A.46)
1 t
1
exp
Alm T) Bu(t)dt-
T 1- exp
Aln t T
a(t)t
(A.47)
t=0
t
1=0
Size N representation = representtno Error
(A.48)
The last. term indeed the second lype error that we have discussed the error analysis section of the paper.
Using eigenvalue decomposition of VAV-1 we re-write the above error term as
Error = /T
1 exp AAln t [ V V-'z(()dt
(A.49)
== 1
with a change of variable s = In
Error I" exp(As)V- E(s)ds
(A.50)
==0
According to the assumption of this theorem |V-1c(t)l2 ||<(t)l22 cm
Error] < exp(sl))emds = 6m
(A.51)
A
t=
Error || Error s cm
Σ
=
(A.52)
Suppose frame + given. The Dual of Truncation. (DoT) construct introduced in Sec- tion 5.1.3 has optimal representation error when compared any other SaFARdN) construct for the same frame +
Thcorem
24

---

Published in Transactions on Machine Learning Research (10/2025)
Proof:
The proof for this theorem involves two steps.
First, we show that the optimal representation error in the theorem can be reduced to optimal error of the second type (mixing).
Then, we demonstrate that for given frame Φ, and given truncation level N, the construct with the optimal second type error control DoT.
As discussed in Sec. 5.2 the first type of error is due to truncating the frame, and is independent of the SSM. In the scope of this theorem, all the SaFARi(M) constructs use the same frame and the same truncation. Therefore, comparing the representation error between SaFARi(N) in the thcorem reduces to comparing the mixing error.
The mixing error is shown in Theorem 3 be proportional
( (uT, E)
(A.53)
To minimize
|| irrespective of the imput signal, one has to minimize ||El]
{ = Y [o:N] (N0
(o:N (P 1)
(A.54)
Where Tio:N] and Poo:jj are the first N elements of T and 4. (N) is the approximation of the dual frame that determines the SaFARi(M) construction. For the ease of notation, we rewrite Eq. A.54 as:
{ = r(Φ0-1 I) I)
(A.55)
For fixed Y, and Φ we aim to minimize
|E| with respect to कK
Aryming | 1)l?
(A.56)
For the optimal T the partial derivative is zcro.
2
K
|| TT 1) 2TT (क0 T)x2" =
(A.57)
aΦ
OΦ
き = (Φ
(A.58)
One should note that the described T is indeed the pseudo-inverse dual for the truncated frame [[o:N]- Therefore, among the possible SaFARi(N) constructs for the same frame, the Dual of Truncation (DoT) has optimal representation error. D
A.7 Parallelization using the convolution kernel
Theorem For SaFARi using the scaling measure, if A diagomalizable, computing the scaled represen- tation on sequence with samples can be done using a kernel multiplication. a) For the discretization using General Biliniear Transform (GBT) with parameter a, the kernel be computed using:
Ihk (1 (1- 1-
Kr[i.
ERNXL
(A.59)
Ih (1)))))))
b) For long sequences, the kernel K can be approzimated using
Kz(i,)) - (1) ERLXL
(A.60)
For either case a or b, the representation is computed as:
MKM, M Vdiag( (V-I) BB)
(A.61)
where V. and Da the eigenwector matria and eigenvalues of A.
25

---

Published in Transactions on Machine Learning Research (10/2025)
Proof: a) rewriting the GBT update rule for the diagnoalzied SSM we have:
Cp++1]= + 1| [+ a
n a++1" ) ==11)
1
Clnl + 1+ n 2) Bu[n]
a
(A.62)
n
A, [n] [m]
+ Bnu(
C - 1] [1, + A Iu(. 1] +... + AL... Ān Bou(0]
(A.63)
for the ease of computation and notation, we define Kr such that:
Kz[i,5] AL... Ast1 (1+ 1+1 A1) lkk (1- - Ni)
1+
(A.64)
Il 1 x1
C = Bi Σ Ky Kzli,j]u[j] = B.(K
(A.65)
č B (K diag (B)
(A.66)
Vč Vdiag MK,
(A.67)
Proof: b) Using Lemma I for the diagonalized version of Scaled-SaFARI the closed form solution is
exp (Al1 (AIn+)
Bu(l)al.
ビ=
(A.68)
11=0 t
T 1
B,u(t)dt B /"
1/t t
2
exp
A In T
T
u(t)dt u]
(A.69)
1=
き= 3 (Kr.0) diag Kr)
(A.70)
c= Vē= Vdiag( MMKū
(A.71)
Theorem 7 For SoPARi using translated measure with Oz, samples long sliding window, if A is diogonalizable, computing the translated representation on sequence with L samples can be done using a kernel multiplication.
a) for the discretization using General Bilinear Transform (BT) with porameter a,, the kernel can be computed using:
1.-j
A
Kr.li.11 = 1 aA
(A.72)
1 + ax:
b) For long sequences, the kernel K can be upprosimated using
K2(i,)) 01
exp (- (->: AL
L. 1-j
ERRXL
(A.73)
For either of case or b, the representation is computed by
c= MKKū M = Vddaa(V-11))
(A.74)
where V. and D; are the eigenvectors matrie, and eigenwalues of A.
Proof:
a) rewriting the GBT update rule for the diagonalized SSM we have:
Önn + 1] (1 ( -1 11-11-1110 --1--A) T(m] + (T+ x) Bu[n) = AC(m) + Buln)
(A.75)
26

---

Published in Transactions on Machine Learning Research (10/2025)
take similar approach to the previous theorem. The only difference is that A and B remain the same for all the time indices.
+|= Bu[L] ABulL 11 + + A A Bu[o]
(A.76)
for the ease of computation and notation, we define Ke such that:
B 1 (1
L-j
Kr]ū,
(A.77)
1+ db
g g\
C B, Σ K Krli,jlußj] [.[
(A.78)
غ == B (K = diag L
(A.79)
V2 (dia MK₁
(A.80)
Proof: b) Using Lemma 2 for the diagonalized version of Translated-SaFARi, the closed-form solution is:
c
1
exp
(
A
Bull).
(A.81)
1=T
0
1
T-T
2
exp
Ai
Bru(t) B,(
(A.82)
|=1 0 0
A
غ == B 3 (K diag B
(A.83)
== Vč= = Vdia = MK
(A.84)
A.7.1 Numerical instability of the fast sequential LegS solver
As part of our experimental findings, we realized that the proposed method for sequential updates for LegS SSM( in Gu et al. (2020), Appenndxx E) suffers from numerical instability when working with larger SSMs.
cumsum (Buusun(ccuproo)) cumprod
(A.85)
where the introduced a₁ = de a decreasing function. One can confirm that in the thh iteration, and for 144 the htth degree Legendre polynomial
d2
2(t + -
0g
(A.86)
1+ d₃
2(t
1)+
Then the proposed solution requires finding cumulative product of 1 for is E [1 in each step.
log cumprody
1 ap.'
(A:)
Σ
K
log
Σ log
-1 4(t ((t+1) (1)+1)++ +1
(A.87)
Ock'
2(t + 1) - k/
2(++1)
4(t + 1) +1
K Σ
4(t ( 1) +1
= log
-1+
log
1+ - 2(t 1)
(A.88)
2(t + 1) k2
W 11=((++)+11
2(++1)
K K-2(++1
-1+ 4(1+11 1) +1
4(t + 1) +1 1
= Σ log
+
Σ
log
(A.89)
2(t+1) //
K=1
27

---

Published in Transactions on Machine Learning Research (10/2025)
300
20
250
25
80
20
200
150
100
100
200
300
400
500
100
200
300 400
500
Figure 10: Fast Legs numerically diverges. left: For system with N 500, log log for different values of & [1, _ plotted different iterations t 20, 40, 60, 80. right: log of the cumulative product which is equal to the cumulative sum of the left plot is plotted for different iterations. In the right plot, it is notable that for t = 80, the cumulative product reaches to 10300 for a h 500 which is the largest value that a float-64 variable can handle. The studied Fast-LegS method for an SSM having more then 500 coefficients diverges after only 80 sequential updates.
140
120
100
80
60
1000
2000
3000
4000
5000
Figure 11: As the given LegS size N grows, the longest sequence length before observing numerical diversion is given in the above plot. For N 400 we did not observe the numerical diversion. for N 400 the fast legS sequential update method cannot handle sequences longer than limited length before it becomes numerically unstable.
For any specific iteration (fixed t), as grows(higher representation index), the second summation above grows to infinity. Thus, for large enough N, cumprod( ov diverges beyond machine precision. As a result, the proposed fast sequential legS solver proposed in (Gu et al. (2020) Appendix E) fails. Figure. 10 Shows an example where for N 500, fast LegS mumerically diverges for any sequence longer than 80 samples. It is crucial to note that this numerical instability fundamental to legS, and does depend on the input: signal at all.
We also investigate the longest sequence length that the given fast legS sequential solution can handle without numerical diversion. Figure [1 shows that as N grows, then length of sequence that fast legS sequential solver can handle before becoming numerically unstable decrease to a limited length.
A stable version of solving LegS would be a similar approach as fast-LegS, but in the last step, instead of introducing the proposed and 3, we find 21 then recursively find x; after finding all the pervious æ,s. This way, the overall computation complexity remains the same, while the run-tim time complexity increases, one cannot compute 2; until Tp,..., Ii-1 computed.
28

---

Published in Transactions on Machine Learning Research (10/2025)
A.8 Bases and frames
Legendre Polynomials: Legendre polynomials form an orthonormal basis for square-integrable functions on the compact interval [-1, 1]. Their recurrence relations and bounded values make them well-suited for tasks such as Gaussian quadrature, spectral methods for solving differential equations, and polynomial interpolation. However, SSMs built. from Legendre polynomials can suffer from numerical instability for high degrees, require global support (making them less effective for localized features), and may produce oscillations near interval boundaries, limiling their practicality in approximating functions with sharp varialions or discontinuities.
The familiar Fourier series is an orthonormal basis, and with integer n elements have the format) sinnmntt.. The Fourier series represents functions as infinite sums of sines and cosines, which form an orthonormal basis for square-integrable functions on a compact interval, making them highly effective for approximating periodic functions. Howeeer, they have important limitations for function approximation: they assume periodicity, and can exhibit the Gibbs phenomenon when approximating con-periodic sharply varying functions; they provide global support, making them inefficient for capturing localized features; and high-frequency components are often needed to approximate functions with sharp transitions, which can be computationally expensive.
Fourier Series:
Similar to the Fourier series, these functions have the form v2 cos((att,) v siimaatt,, where a is a real number sampled from a uniform distribution, not integers. A random collection of these functions is not guaranteed to span L2, and therefore is not a frame or basis. In general, using random vectors in place of frame or basis is a poor choice. We include separately only as a counter-example to orthogonal bases and redundant frames. We can also use this set to augment a Fourier basis: since Fourier basis spans L2, concatenating additional vectors introduces redundancy, and we have a frame.
Random Harmonics:
Laguerre Polynomials: Laguerre polynomials form an orthonormal basis for square-integrable functions on the semiiinfinite interval [0, oo] with respect to the weight function e e= These properties make them well-suited for approximating functions defined on unbounded domains, particularly when the function decays exponentially, and they are widely used in quanlum mechanics, numerical analysis, and differential equations. Laguerre polynomials are less effective for approximating functions on compact intervals, as they exhibit increasingly oscillatory behavior for large degrees, and their reliance on specific weight function limits their flexibility for approximating functions that do not exhibit exponential decay.
Chebyshev Polynomials: Chebyshev polynomials form an orthonormal (or orthogonal, depending on normalization) basis for square-integrable functions on the compact interval [-1, 1] with respect to the weight - They are known for their near-minimax property, meaning polynomial approximations using Chebyshev nodes minimize the maximum crror. This makes them highly effective in polynomial interpolation, spectral methods for solving differential equations, and numerical approximation schemes that need high accuracy with fewer terms. However, Chebyshev polynomials are global basis functions, so they are less effective for functions with localized features or sharp discontinuities. They also require transformations or rescaling for domains other than 1-1, 1], and like other polynomial bascs, they can be inefficient for very high-dimensiooall or highly irregular function approximations.
Bernstein polynomials form a basis for continuous functions on the compact interval [o, 1]. They are non-negative, form a partition of unity, and have excellent phaaee-pes properties, making them particularly useful in computer graphics, geometric modeling (e.g., Bézier curves), and approximation theory. Bernstein polynomials are not orthogonal, which limits their efficicncy in some numerical computations, and achieving high accuracy often requires large polynomial degrees, leading to higher computational cost. They are also less suitable for capturing oscillatory behavior or sharp transitions, compared to orthogonal polynomial bases like Chebyshev or Legendre.
Bernstein Polynomials:
Gabor filters (or Morlets) capture localization in both time and frequency, making them popular for use in biomedical signal processing and image texture analysis. They can be constructed by modulating a complex sinusoid with a Gaussian as: fa(x) = e e (a-be / e (x)), where by are shifts in time, 4g are frequencies, and w the scaling of a Gaussian envelope. To ensure that the resulting set of functions creates oversampled lattice, we ensure that. the time-frequency sampling overlaps; that is, AaAb < 1.
Gabor:
29

---

Published in Transactions on Machine Learning Research (10/2025)
A.9 Additional Experimental Results
Tables and provide the standard deviation for the MSE results in Table 3 Most values are the same order of magnitude. A notable exception is "Rand". Since the collection of random sines and cosines do not form a complete frame or basis, it a matter of luck how well they represent a particular signal. The more random components are added, the more likely it that the vectors will support the signal of interest, and shorter signals require fewer components. Since the translated measure has a consistently small window, the variance here is on par with other true bases bases/frames. /frames. The worst case when the signal is long (scaled measure) and the rank is low (N=32), as expected.
Scaled
N 32
N 64
128
SP
M4
SP
M4
SP
M4
Leg
0.0007
0.0062
0.0007
0.0060
0.0007
0.0060
Fou
0.0003
0.0040
0.0002
0.0029
0.0002
0.0020
Lag
0.0012
0.0100
0.0012
0.0100
0.0012
0.0100
Cheby
0.0003
0.0030
0.0003
0.0021
0.0003
0.0014
Bern
0.0005
0.0037
0.0004
0.0032
0.0003
0.0029
Rand
0.0005
0.0258
0.0004
0.0105
0.0003
0.0048
Fou+
0.0003
0.0036
0.0002
0.0028
0.0002
0.0019
Fou+* 0.0002
0.0029
0.0002
0.0018
0.0001
0.0010
Gabor 0.0004
0.0050
0.0003
0.0033
0.0125
0.0040
Gabor
0.0003
0.0041
0.0003
0.0035
0.0009
0.0026
Table 4: Standard deviation of reconstructed signals with different instantiations of SaFARi and a scaled measure. The table divided into polynomial (top) and non-polynomial (bottom) representations.
Translated
N
32
N 64
N = 128
SP
M4
SP
M4
SP
M4
Leg
0.0029
0.0069
0.0029
0.0068
0.0029
0.0069
Fou
0.0006
0.0052
0.0006
0.0051
0.0006
0.0052
Lag
0.0006
0.0052
0.0006
0.0051
Cheby
0.0006
0.0052
0.0008
0.0052
0.0011
0.0054
Bern
0.0006
0.0052
0.0006
0.0051
0.0006
0.0052
Rand
0.0006
0.0053
0.0007
0.0052
0.0009
0.0053
Fou+-
0.0006
0.0052
0.0007
0.0051
0.0009
0.0053
Fou+**
0.0006
0.0053
0.0008
0.0052
0.0009
0.0054
Gabor 0.0006
0.0052
0.0006
0.0051
0.0007
0.0053
Gabor
0.0006
0.0053
0.0007
0.0051
0.0007
0.0053
Table 5: Standard deviation of reconstructed signals with different instantiations of SaFARi and translated
measure. The table is divided into polynomial (top) and non-polynomial (bottom) representations. Missing entries for Laguerre could not be computed due to numerical errors arising from exponents in higher-order terms.
30


Reviews:
[{"review_id": "9G6ohP2jmx", "reviewer": "Reviewer_LAw1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The method to compute transition matrices for SSMs with any frame or basis seems novel.\n\n2. Introduction and discussion of Dual of Truncation (DoT) that is computationally efficient and has a minimum reconstruction error.\n\n3. The paper does a commendable job disentangling the different relevant components of SSMs (frame, measure, discretization, diagonalization, efficient implementation), and provides good explanations in general.\n\nWeaknesses:\n\n1. The paper is missing empirical validation demonstrating the usefulness of more general frames.\n\n2. Section 2.3 clearly states the limitations of HiPPO, but the paper then only partially addresses these limitations.\n\n3. Insufficient explanation how weighting and windowing measures influence the frame operator.\n\n4. Diagonalizability of A is key to applying the method in practice. The paper has scarce discussion how choice of frame and measure influence whether A is diagonalizable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a method for computing transition matrices in state spaced models (SSMs) for arbitrary frames, extending the popular HiPPO approach for SSMs.\n\nIn theory, this new method improves on multiple weaknesses of HiPPO, namely the non-diagonalizability of the ubiquitous scaled Legendre (LegS), by choosing other frames and measures that should result in more stable dynamics. In this context, the submission also introduces the notion of truncation and mixing errors, and shows how to optimally construct the dual with finite-dimensional approximations.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Requested changes:\n\n1. Empirical validation: For example replication of experiments from HiPPO (pMNIST etc). The validation should show that the matrices derived with the presented method work in practice, at least on toy problems, and that in some scenarios not commonly used frames are superior to LegS.\n\n2. The claim in Section 2.3 – that many of the bases perform quite poorly – is rather strong and requires more citations.\n\nAdditional questions:\n\n1. Why are only uniformly weighted measures considered ?\n\n2. How does this method benefit large-scale SSMs?\n\n3. What is the usecase of more general frames, especially non-orthogonal basis functions? How do these influence performance of the algorithm?\n\n4. The explanation why A.3 has different results from HiPPO is not good enough – the authors should check if indeed they get to the same results when using a different Fourier basis or range, and otherwise reach out to HiPPO authors trying to understand where the difference comes from.\n\n5. Does SaFARi allow for the design of new gating mechanisms in RNNs?\n\n6. Is Theorem 4 really a tight bound? The Frobenius norm could be quite large.\n\nAdditional comments:\n\n1. Diagonalizing the transition matrix A in section 2.2: This section has multiple imprecise statements that only hold under certain conditions, in particular the authors neglect the case of having degenerate eigenvalues and subspaces of eigenvectors. Should this be mentioned somewhere?\n\n2. Bad line break at end of page 2.\n\n3. Using variable \"x\" in Equations (8ff) is somewhat confusing.\n\n4. The variable mu in Equation (12) should be explicitly introduced.\n\n5. Text just before (A.12) should probably say \"We can write the coefficients as\"", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Mcoezr61cP", "reviewer": "Reviewer_QyCH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. A major strength of the work is the generalizable applicability to any frame or basis. In contrast, previous approach makes assumptions about the basis. For example, HiPPO requires a polynomial basis.\n2. The work include very solid theoretical study on the error bounds of the work. Even though the proposed framework is based on numerical methods and subject to numerical errors, the theoretical study results provides a comprehensive and in-depth analysis on this error which provides better guarantee for the applicability of the proposed framework.\n3. The work provides technical details on the implementation and computational efficiency analysis.\n\n** Weakness**\nA major weakness of the work is lack of quantitative results. There're many tasks the proposed approach can apply to like forecasting or inference. Many existing SSMs or deep-learning based methods like LSTM or transformers can be applied to these tasks as well. The work should compare their methods against these methods on these tasks and provide quantitative results.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The work proposed SaFARi (SSMs for Frame-Agnostic Representation), a generalizable method for building an SSM with any basis and framework and extends existing methods like HiPPO which are restricted to polynomial basis. To address the challenge that closed-form solution is not available, the work provides numerical methods which apply to both uniform scaled and uniform translated measures. The work shows theoretical study results on the error bound of the approach. The work shows the proposed approach can run in time complexity as low as O(N Log L), demonstrating superior computational efficiency against existing methods.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would like to see the work to include some quantitative study results and make comparisons against existing SSMs like HiPPO or learning-based methods like LSTM or transformers.", "broader_impact_concerns": "As a work primarily focusing on methodology and results, I don't have big concerns for its broader impacts.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "NSxz2KGtHK", "reviewer": "Reviewer_8VQc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- a novel (to my knowledge) but natural derivation\n- a quite extensive exposition, with interesting discussions on practical implementation, relation to prior work, and so on\n\nWeaknesses:\n- there are no numerical experiments (or almost). I understand that this is a \"resubmitted\" shorter version that focuses on the theoretical aspects (I do not have access to the previous version), however it is difficult to visualize and understand how the proposed method \"generalize\" previous works to \"any frame\" without providing one single new example and demonstrating its numerical performance and its implementation, its error bound, and so on. Is there a particularly striking new example of frames that is significantly different from previous work, and whose implementation can be done with the results of the paper?\n- it does not seem that $\\Phi$ being a frame (or even a basis) plays any role in the theoretical analysis? If not, is it possible to indicate why it is important to have a frame? (beyond obvious numerical performance)\n- The section on truncating and error bound is a bit unrigorous. It is not immediate to define the convergence of growing matrices towards operators (def. 4): one must introduce proper norms, hypotheses of summability, etc. Following that, subsequent claims that truncations \"obviously converge\" must be handled a bit more carefully.\n- Related to the two previous points, one would expect to see the $A_{frame}, B_{frame}$ appear somewhere in the bounds? If not, why?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors derive general equations for State Space Models (SSM) where any frame may be used for function approximation. This generalizes earlier results mostly based on various orthogonal polynomials (so-called HiPPO method). Instead of closed-form expressions, they obtain SSMs were the update operators are under the form of various inner product between frames and their duals. They then discuss quite exhaustively matters of finite approximation, resulting errors, and computational complexity. The appendices are quite extensive.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)