HOPE for a Robust Parameterization of Long-memory State Space Models
Authors: Annan Yu
Michael W. Mahoney
N. Benjamin Erichson
Venue: ICLR 2025 Poster (2025)
Keywords: state space model
sequence modeling
Long-Range Arena
long memory
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We introduce a novel parameterization for state-space models (SSMs) based on Hankel operator theory, which enhances the initialization and training stability and significantly improves long-term memory retention in our models.

Abstract: State-space models (SSMs) that utilize linear, time-invariant (LTI) systems are known for their effectiveness in learning long sequences. To achieve state-of-the-art performance, an SSM often needs a specifically designed initialization, and the training of state matrices is on a logarithmic scale with a very small learning rate. To understand these choices from a unified perspective, we view SSMs through the lens of Hankel operator theory. Building upon it, we develop a new parameterization scheme, called HOPE, for LTI systems that utilizes Markov parameters within Hankel operators. Our approach helps improve the initialization and training stability, leading to a more robust parameterization. We efficiently implement these innovations by nonuniformly sampling the transfer functions of LTI systems, and they require fewer parameters compared to canonical SSMs. When benchmarked against HiPPO-initialized models such as S4 and S4D, an SSM parameterized by Hankel operators demonstrates improved performance on Long-Range Arena (LRA) tasks. Moreover, our new parameterization endows the SSM with non-decaying memory within a fixed time window, which is empirically corroborated by a sequential CIFAR-10 task with padded noise.

Published as a conference paper at ICLR 2025
HOPE FOR A ROBUST PARAMETERIZATION OF LONG- MEMORY STATE SPACE MODELS
Annan Yu'
Michael W. W.Maahnny22- N. Benjamin Erichson" 1 Center for Applied Mathematics, Cornell University, Ithaca, NY 14853, USA
2 Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
3 International Computer Science Institute, Berkeley, CA 94704, USA
4 Department of Statistics, University of California at Berkeley, Berkeley, CA 94720, USA
ay2 2ere6eeeeeeellee edu mmahoney@stat www.eeeeeey........... eddu erichsoneicsi bew.eeeeeee..b.................
ABSTRACT
State-space models (SSMs) that utilize linear, time-invariant (LTI) systems are known for their effectiveness in learning long sequences. To achieve state-of-the- art performance, an SSM often needs specifically designed initialization, and the training of state matrices is on logarithmic scale with very small learn- ing rate. To understand these choices from unified perspective, we view SSMs through the lens of Hankel operator theory. Building upon it, we develop new parameterization scheme, called HOPE, for LTI systems that utilizes Markov pa- rameters within Hankel operators. Our approach helps improve the initialization and training stability, leading to a more robust parameterization. We efficiently implement these innovations by nonuniformly sampling the transfer functions of LTI systems, and they require fewer parameters compared to canonical SSMs. When benchmarked against HiPPO-initialized models such as S4 and S4D, SSM parameterized by Hankel operators demonstrates improved performance on Long-Range Arena (LRA) tasks. Moreover, our new parameterization endows the SSM with non non-decaying memory within fixed time window, which is empirically corroborated by a sequential CIFAR- 10 task with padded noise.
INTRODUCTION
State-space models (SSMs) (Gu et al., 2022b) have gained popularity and success in sequence mod- cling. Known for its excellent efficiency and capability of handling long sequences, SSM lever- ages the continuous-time linear, time-invariant (LTT) systems. These systems are often defined by
four matrices r (A, B, C)
x' x((1) = Ax(() + Bu(t).
y(t) = Cx(() Du(t),
(I)
and they can be used to model the mappings from input time-series u(-) to the output times-series y(), where u(l)= E m and y() E IRP every The (hidden) states, which capture the latent dynamics, are denoted as x x()) E R". The system matrices are of dimensions A Cax,, Coxn, and E Coxm, Often, the size n the state vector x much larger than
B E @axmm and p. which allows to memorize information about the past inputs ul(-00,4) .i in the state vector x(t) and retrieve it later to compute y via C.
The so-called S4 (Gu al., 2022b) and S4D (Gu al., 2022a) models both set m p == and they differ in the structural requirement of A. This framework was later generalized to the case where m. p > 1 by the $5 model (Smith et al., 2023) via the parallel seans. Another line of research involves making the state transition rule A depend on the input u. along which the two most notable models are Liquid-S4 (Hasani et al., 2023) and Mamba (Gu Dao, 2023), where the latter model achieves the tfate-of-the-rr performance
large-scale real-world datasets.
However, SSMs typically need to be initialized and trained (very) carefully. A randomly initialized SSM has suboptimal performance, but the so-called high-order polynomial projection operators (HiPPOs) (Voelker et al., 2019; Gu et al., 2020; 2023) can be used to empirically improve it. On the other hand, properly initialized SSM needs to be trained with care. One often needs

---

Published as a conference paper at ICLR 2025
to set smaller learning rate for the matrix A (Gu et al., 2022b), and the LTI systems require reparameterization to be trained stably (Wang & Li, 2023). To better understand these initialization and reparameterization efforts from unified perspective, we analyze SSMs through the lens of Henkel Operator theory. Specifically, we use the Hankel singular value decomposition (HSVD) to analyze an operator defined by r. The decay of the Hankel singular values tells how "expressive" the LTI system is. If the Hankel singular values of I' decay fast, then it informally means that our I' cannot capture the complex patterss in the input space {u(+)); in fact, the theory of reduced-order modeling (ROM) says that r can be well-approximated by a reduced system with a much smaller state-space dimension < n (Glover, 1984).
We find that the decay of the Hankel singular values can be used for predicting the performance of an SSM, and that every previous effort in proposing a good initialization and training scheme can be viewed as an effort to avoid fast-decaying Hankel singular values. This is reminiscent of the works by Martin& & Mahoney (2021) and Martin et al. (2021) that connect the singular values of the weight matrices to deep neural network's performance. Using the Hankel singular values as heuristics, we show that an S4D model is vulnerable to losing expressiveness during training. Moreover, even LTI system is very sensitive to perturbation of its parameters, A, B,
with reparameeterization, and C, impairing the training stability of an S4D model.
Based these insights, we propose com- pletely different parameterization of the LTT systems. Instead of using the continuous-time systems by matrices A, B and C, we param- eterize our LTI systems by the Markov param- eters of the so-called discrete Hankel operator (HOPE). discrete Hankel operator is defined by a Hankel matrix, and is naturally associ- ated with a discrete I.TI system, and with continuous-time system via the bilinear trans- form with At- = (Glover, 1984). While this continuous-time LTI system acts on se- quential data, the optimization algorithms are applied to the Markov parameters of the Han- kel matrix. (See Figure 1.) We prove that unlike an LTI system parameterized by (A, B, C, D), one parameterized by the Markov parameters almost surely has slowly decaying singular val- ues (see Theorem 3); moreover, it enjoys global stability to perturbation (see Theorem 4). Hence, unlike canonical SSM, our HOPE- SSM can be stably trained without reparame- terization or reducing the learning rate, also reducing the need for hyperparameter tuning. We show that our HOPE-SSM can be implemented by nonuniformly sampling the transfer function, enjoying the same computational complexity as the S4D model. Moreover, it requires only 1/3 the number of parameters of an LTI system in an S4D model to parameterize that in a HOPE-SSM.
95, H.Y
Cupun
y7
y
Impulon Reeporen
x(j)= Axd? Bet))
Condinuuus Ln Syatem
Discreto LTI System A
Hanbel Opentor H.C C...- 1²
OXto
Iruse
Sydtem
HOPE-SSM
Qupput
Figure 1: There are many equivalent ways to rep- resent LTI system. While most of the canon- ical SSMs use continuous LTI systems as their parameters,
propose to parameterize by the Markov parameters in its Hankel operator. The feedthrough matrix D is not shown in the di- agram, but it is also parameter of the LTI layers in both the canonical SSMs and our HOPE-SSM.
SSM
The practical benefits of our novel parameterization are improved robustness (with respect to initial- ization and training stability) and performance (with respect to model quality and parameter count). Moreover, show that the memory of our HOPE-SSM does not decay (see eq. (6)) in a fixed time window, making it possible to solve tasks that involve even longer-range dependency by tuning the sampling period At at discretization. This partially addresses the well-known issue that the LTI system of a canonical SSM suffers from exponentially decaying memory (Agarwal et al., 2023).
Related Work. Initially proposed by Voelker et al. (2019), the general idea of the HiPPO framework is to memorize the input by projecting it onto an orthogonal polynomial basis and storing the coef- ficients in the state vector (t). This was later generalized some different orthogonal polynomial bases in Gu et al. (2020; 2023). The S4D model uses a slightly perturbed version of the HiPPO-LegS initialization, and the effect of the perturbation was studied in Yu et al. (2024). The initialization issue was also studied in Orvieto et al. (2023) in the discrete-time setting, which provides an alter- native justification of HiPPO based on the spectrum of the state matrix. While common way to reparameterize a diagonal SSM is by training Re Re(diag(A)) on a logarithmic scale (Gu et al., 2022a),
2

---

Published as a conference paper at ICLR 2025
other stable reparameterrizatios were considered in Wang & Li (2023). A method that directly pa- rameterizes the convolutional kernel of the discretized LTI system was presented in Fu et al. (2023). Compared to their work, in this paper, adopt compute- teeettteeen--teizzte strategy by still parame- terizing the underlying continuous dynamics, making our SSM capable of handling sequences with varying lengths.
The decaying memory of RNNs and SSMs is analyzed and discussed by a wide literature (Hardt al., 2018: Gu al., 2020; Wang & Xue, 2024; Orvieto et al., 2024). Ways lift the memory capacity of an SSM were considered in Wang & Li (2023) and Agarwal et al. (2023) via either reparameterizing the state matrix or applying a spectral filter. We remark that while Agarwal et al. (2023) showed that a spectral SSM is exponentially close to an SSM, our HOPE-SSM is an actual SSM containing L.T systems, and it only differs from a canonical SSM in the parameterization.
Contributions. Our main contributions are summarized as follows.
We show that high-degree LTI systems (i.e., those with doowyieg Hankel singular val- ues) in an SSM lead to good performance. We justify this causal relationship using ideas in reduced-order modeling (ROM). We theoretically prove that expressive, high-degree LTI systems are scarce in the parameter space of (A, B, C). Thus, they need careful designs and are numerically unstable. This explains difficulties in initializing and training SSMs.
2.
We propose new parameterization of LTI systems using the Hankel operator (HOPE), which can be implemented efficiently by nonuniformly sampling the transfer function and requires 1/3 the number parameters in an LTI system from an S4D model. We prove that our parameter space is full of high-degree LTI systems. Hence, HOPE-SSM does not suffer from the lack of expressiveness during initialization and training; morcover, it can be stably trained and has non-decaying long memory.
3. We empirically demonstrate that our HOPE-SSM is robust using the sCIFAR-10 10 task and that has long-term memory using a noise-padded SCIFAR-10 dataset. We test the perfor- mance of a full-scale HOPE-SSM on the Long- Range Arena and observe that its perfor- mance exceeds that of its S4 and S4D counterparts and many other SSMs for most tasks.
PRELIMINARIES
Let r = (A, B, C, D) be continuous-time LTI system defined in eq. (1). One can take a bilinear transform to obtain discrete system r (A, B, C, D) that the underlying dynamics is given by
X = Ax + Bug;
Y& = CX.
Dug-
(2)
The transfer functions of r and are rational functions on the complex plane C defined by
G(s) = C(sI
and
G(z) -
-
respectively. We usually care about the values of G and G on the imaginary axis and the unit circle in C, respectively. They "transfer" the inputs to the outputs in the frequency domain by multiplication:
(continuous case)
(s)) = ((is)
8 E R.
(discrete case)
yx G L
0 OSkS
where the hats on a function and on a vector mean the Fourier transform and the Fourier coefficients, respectively, and W/ = exp(i2rk/ L) is the kth Fourier node of length L. Throughout this paper, we assume that our LTI systems are asymptotically stable, i.e., the eigenvalues of A have negative real parts, equivalently, the eigenvalues of A are contained in the open unit disk in the complex plane. In this paper, we also discuss a completely different notion of stability: the numerical stability of an LTI system. This refers to the system's 's sensitivity a perturbation of its parameters. We will clearly distinguish these two notions of stability by appending the adjectives "asymptotic" or "numerical".
Given a discrete LTI system I. its Hankel operator defined by doubly infinite Hankel matrix
H E Xo
H (N)
H = CA "A'
1,j20,
where (N) = f( f, E C, E 1f < oo). This discrete Hankel operator on (2(N is bounded linear operator of rank n, the number of latent states. We denote its singular
3

---

Published as a conference paper at ICLR 2025
2 on H 0. Analogously, can define continuous Hankel operator H : (20 00) + (10, given a continuous time LTI system T, where (i0, oo) = {f [0, 00) - C f measureable, _ (f(t) < oo). If T is discretized from I using the bilinear transform, then the singular values of H are equivalent to those of H. i.e., (H( o, (H). (See Appendix B for more details.) In this paper, we consider the decay of the Hankel singular values. To quantitatively measure how "small" a singular value is, we introduce the numerical rank of an LTI system. Given a small number e 2 O, we define the e-rank of I' to be the number of relative Hankel singular values larger than c:
values by 01 H 2 H2
rank, (T) = max (j oy ( >
When O, we reproduce the exact rank of H, which is rarely < in the Seating-point arithmetic. A small positive e allows us to climinate the small but perhaps positive singular values.
3. UNRAVEL A MYSTERY: HANKEL SINGULAR VALUES IN INITIALIZATION AND TRAINING
Frozen LTT Systems
Trained LTI Systems
88
Accuracy
28
Accuracy
8
8
8 8
88
23
50
50 100
20
40
50
100
Epochs
Epochs
Figure 2: Test accuracy of the SSMs on the sCIFAR task. The LTI systems are initialized in three different ways and either trained or untrained. We notice that when the LTI systems are initialized with initi to (red), training the LTTI system together with other model parameters is impairing the model accuracy. This is in contrast to SSMs initialized with i inits (blue), where assigning the LTT system a small positive learning rate is helping the performance.
We begin our exploration by presenting a mystery. We use it to elicit and support the use of the Hankel singular values as protocols for explaining and predicting the success of SSMs, without stressing it as a fine-grained study of different initializations. We train an S4D model to learn the SCIFAR-10 10 image classification task (Krizhevsky al., 2009; Tay al., 2021). We consider three initialization schemes of the LTI systems in the SSM: init initz, and init3. While inits the HiPPO-LegS initialization, we treat the others black boxes in this paper, leaving the details to Appendix D. Instead, we later explain their success or failure by measuring their Hankel singular values. For an SSM initialized using a certain init, (1 S j S 3), we train it two different ways: either by freezing A, B, and C and only training the other model parameters by assigning A, B, and a small learning rate. The three initializations and two learning rate assignments comprise total of six combinations, summarized in Figure 2. Besides the natural question of why see general difference between models initialized differently, Figure raises a more intriguing mystery:
For SSM initialized by ini init t1, initz or initz, why does training the LTI systems impair, level, or improve the performance of the model, respectively?
To answer these questions, relevant? The reason is that the Hankel singular values measure the "complexity" of an LTI system. The easiest way to see this is via ROM of the system I (Adamyan al., 1971; Glover, 1984):
study the Hankel singular values of the systems, but why are they
For any ls < n, there exists reduced-order approximation F (A, (, with À Ckxk such that ||G IG-GGo ~l Ej=en (H) < (n k)ox+1 1 (H), where Ô is the transfer function of and || Iloo is the L-infinity norm over the imaginary axis.
In particular, if the sum of the trailing Hankel singular values Σj= Ty (H) is small, then by eq. (3), I' and ñ produce similar outputs any input. Hence, ROM says that if the Hankel
4

---

Published as a conference paper at ICLR 2025
initi
init2
init3
101
10
At Initializaaio
10
10
10-
10f
105
10
10
12"
122
After Epochs
10
10
100
10/
10
10
10
10"
195
(H (FT)
( (F))
(H)/m (H)
Figure 3: The distribution of all relative Hankel singular values oj (H)/a, (H) of the LTI systems
in an SSM. For each initialization, the distribution is shown both at initialization and after the SSM
is trained for 10 epochs. Note that the second row only applies when the LTI systems are not frozen.
singular values decay fast, then we can replace the LTI system with much smaller one without too much loss; in other words, most states in x() are not properly used memorize the input.
In our experiment, each SSM has 4 layers and 128 channels. These comprise x 128 = 512 different copies of bongle-input/singl--ooo
LTI systems. Every LTI has n 64 latent states. These make up 512 x 64 = 32768 relative Hankel singular values o, 7, (H) (H) to consider. In Figure 3, we show the histograms of all these relative Hankel singular values at two different stages of training. Note that the three histograms on the second row only apply when the LTI systems are trained with a small learning rate; when they are frozen, the distributions always stay the same as those at initialization. We can explain the behaviors of the three SSMs using their Hankel singular values:
1. The systems in model initialized by init; 1 initially have high numerical ranks. Hence, when the systems untrained, they define random mappings that capture the rich content in the input data, yielding the rest of the work to other model parameters in the SSM. However, when the systems trained, their Hankel singular values start to decay rapidly with only 27. 27.87% of the singular values satisfying that o, (H)/o, (H) > 0.01, and the systems
longer handle a variety of distinct inputs. This makes it harder to parse complicated images in the SCIFAR-10 dataset.
2. No matter whether trained or not, the Hankel singular values of the systems in the model initialized by inity decay very fast, which means the systems essentially lack expressive- ness and cannot capture the complicated patterns in the imput space. Hence, the SSMs with both trained and untrained L.TT systems could not learn the task effectively.
3. The systems in the model initialized by initz, trained or not, have high numerical ranks. In particular, over 87.82% of the singular values satisfy that or (H)/o,(H) > 0.01 after 10 epochs. In this case, training the LTI systems allows us to accelcrate the optimization.
We just established the Hankel singular values protocol for evaluating and predicting the perfor- mance of an SSM on tasks that involve complicated long-range dependencies. We can further derive theory to explain the patterns observed in the histograms in Figure 3, which brings out potential weaknesses of the S4D models and motivates the development of our HOPF-SSM.
3.1 MANY LTI SYSTEMS HAVE Low RANKS
We saw that LTI systems with high numerical ranks make an SSM thrive, but do we have an abun- dance of them? We approach this question from a random matrix theory perspective. We randomly sample an asymptotically stable LTI system. Since every diagonal entry a, A diag(a1..... an) needs to be contained in the open unit disk, we cannot assume that they are sampled from a random Gaussian distribution. Instead, we assume that every aj is sampled i.i.d. from a distribution F, with
P ((a,) > (1 - p)) = O(p))
as
p p 0+
for some a For example, aj uniformly distributed on the open unit disk, then we have 1. Moreover, assume that B C. is random vector with each entry sampled i.i.d. from
5

---

Published as a conference paper at ICLR 2025
normal distribution (0. 1), where is the Hadamard product. The skip connection matrix D has no effect on the Hankel singular values. With these assumptions, we formally show that the system has low e-rank with high probability.
Theorem 1. Given any > 0,0 < a S 1, and 0 < ď < 1, with probability at least 1- 5, the e-rank of r = (A,,,C,)) with d ~ Fa i.i.d and bygg ~ NN(0, 1) i..d. is (1n(( ((1n(6-3/26-3)) (6) n²). where
1n(2 + (ln(1/6)/2)
B ++a
In(n)
and the constant O is universal.
We defer the proof Appendix E. What Theorem says is that if we ignore the logarithmic factors in the O-notation, then the c-rank of F scales like n as n + 0c, where 3 < 1. For exam- have B 1/2 plus small number
ple, when aj uniformly distributed bounded by In(2 + /In(1/6)/2) In(n). practice, we find that this term can almost be ignored (see Appendix H). The importance of Theorem is twofold: from an expository point of view, theoretically verifies, using our Hankel operator framework, that random initializations of LTI systems could lead to poor model performance, as observed in Gu et al. (2020) and Orvieto et al. (2023); from a practical perspective, it suggests high-rank systems are only scarce in the space of S4D model parameters. Hence, even when LTI system is initialized with slow-decaying Hankel singular values, when A, B, and C are perturbed during training, it is at risk of losing numerical ranks and thus expressiveness. This is indeed observed in Figure even for ini initz.
the unit disk,
3.2 LTI SYSTEMS ARE NUMERICALLY UNSTABLE UNDER PERTURBATIONS
In this section, we perform sensitivity analysis of an S4D model, which suggests numerical stability issue in training the model.
Theorem 2. Let r B, C,D) be stable continuous-time LTI system, where A diag(a (1 d1.............................. an) is diagonal. Let r (A, B, C, D) be perturbed stable system with À diag(a .a. a.). Assume there exist A AB > such that la, äyl I A S min, [Re(a)))/2 and lb,c, أ I min(lb,,,l. An) for all = -....,mm n. Let G and G be the transfer functions of T and I, respectively. Then, the following statements hold.
(a) We have
bygyl [Re(a)))
|G- 5 AnAA max
+ MAB max j [Re(a,))
(b) The upper bound is tight up to a factor of n. That is, given any r, A S miny [Re(a))l/2, and AB < min, [6ycşl. there exist two systems I'A and Î', with transfer functions G'A and ÖB. respectively, that satisfy the above perturbation conditions and have
|| G 2 AA max 1bycyl [Re(a,))2
||G -BBBl 2 AB max Re((a)))
The proof can be found in Appendix Theorem 2 says that when a diagonal LTI system is trained, its numerical stability depends on two things: the proximity of its poles aj to the imaginary axis and the magnitudes of B and C. We defer the discussion of aj to the end of this subsection. One may imagine that || ho is related |bycyl. and hence, Ibycyl plays no role in the relative numerical stability (i.e., || G/llo/ /l))) of the system. However, this is not true as system with a small ||G]| may have an arbitrarily large B C (see Figure 4 (Left)). Working with such system can be numerically hazardous even at inference time due to the so-called cancellation errors YYu & Townsend, 2024). Later, show that our HOPE parameterization does not suffer from these issues.
Combined with the spectral information of the state matrices A, Theorem lets us explain why sys- tems initialized by initi are much more sensitive to perturbation than those initialized by ini Eg- In Figure 4, we show the locations the poles a, and their associated magnitudes [bycyl. Compared to the systems from inits, the poles of the systems from init; are much closer the imaginary axis whereas the values of [byc,l are also much larger. Hence, by Theorem 2, they are much more sensitive training, and therefore lose numerical ranks easily. This is indeed seen in Figure 4.

---

Published as a conference paper at ICLR 2025
init,
init3
Hankel Singular Values
aj and byg
Hankel Singular Values
Aj and
b;c
10
10
10
400
10"
350
10
Imaginary Axis
10a
10
Imaginary Axis
10
6:/01
03/01
200
10"4
10
10
150
10
-0
15%
19
100
19%
17%
50
10
10.5
10
10
20
30
40
50
80
-102
100 -10 Real Axis
10
20
30
40
50
60
100 -10 Real Axis
Figure 4: A random perturbation to the imaginary part of is added to a system from init, 1 and a HiPPO-LegS system from initz. The magnitude of the perturbation is set to 0.1% and 1% of the original matrix A. For each system, on the left, we show the relative Hankel singular values a, o of the original and perturbed continuous-time systems; the right, plot the location of each aj in the complex plane and use the color to indicate the magnitude of its associated [bbcş|-
Theorem 2 delivers a disturbing message. As stated in Baker et al. (2015), "[the Hankel singular values] decay more rapidly the farther the A(A) falls in the left half of the complex plane." where A(A) is the spectrum of A, which is equivalent to (a1...., ",) in the diagonal case. Hence, many diagonal LTI systems with high e-rank, i.c., those that we carlier found necessary for an SSM to capture the long-range dependency, would have eigenvalues aj close to the imaginary axis, making the system more sensitive perturbation and thus the training less numerically stable.
4 HOPE-SSM: A RANKFUL, STABLE, AND LONG-MEMORY PARAMETERIZATION
Given the potential issues of an SSM discussed in section 3, we propose an entirely different param- eterization of the LTI systems called HOPE. We first describe the details of our HOPE-SSM and then explain how it resolves the low-rank and numerical instability issues of an LTI system. In addition, it also benefits from long-term memory. Our strategy is to use a Hankel matrix defined in eq. (4) to parameterize an LTI system. Instead of having A, B, C, D, and At as the model parameters, we now have vector h of length n, the skip connection D, and At as our model parameters. Hence, we use complex parameters from h to replace the 3n (resp. 4n) complex parameters from A, B, and C in S4D (resp. S4); We remark that, as mentioned in the introduction, our model only modifies the LTI systems in SSM. That is, it requires 1/3 the number of parameters in an S4D model for each LTT system. Since there are other components in an SSM (e.g., the encoder and the decoder), we do not compress the number of parameters in the entire model by factor of 1/3. The finite Hankel matrix H E C is then defined by the Markov parameters in h:
H 1 (itien)het)
(S)
In an S4D model, we start with A, B, and C so that hepj = CA ++1 with hi+; and the matrix H corresponds to a discrete LTI system I,, which is further associated with continuous-time system via the bilinear transform with At it is the continuous system I' that takes the role of (A, B. C) in canonical SSM, e.g., S4 and S4D. In particular, I' then discretized with trainable sampling period At for a discrete sequential input. Algorithm 1 computes HOPE, and we leave detailed derivation in Appendix I. We also present a flowchart in Figure 5 to better illustrate the concept. We emphasize that compared to most convolutional-tye -type models (Li et al., 2023), which parameterize a discrete convolutional kernel, our method parameterizes a continuous convolutional kernel. Given the discrete input sequence, we then discretize this convolutional kernel with respect trainable At, making the model adaptable to sequences of varying lengths (see Table 3 for an ablation study).
B; in a HOPE-SSM, we start
Notably, in our HOPE-SSM,
'There are different variants of S4D models that combine B and C into single complex vector use fewer copies of A than the number of channels. Here, we compare HOPE to vanilla S4D model.

---

Published as a conference paper at ICLR 2025
Algorithm 1 Computing the output of an LTI system parameterized by its Hankel matrix.
Input: an input sequence u E R², the Markov parameters of Hankel matrix h E C", and sampling period At> Output: the output y E R of the LTI system defined by h given input u and sampling period At.
1: c- exp 2 2 0:(1-1)
{create FFT nodes)
L
2: + (w
1)./(w +)
{convert to the s-domain, where ./ is the entrywise division {scale the frequency domain in the s-panee (convert back the z-plane) store samples of the transfer function)
3: s + s/At
4:
(1 +
(1+s)./f1 s)./(1 -s)
5: g + zeros( ())
6: for i = 0: (n- 1) do
7: g+ + h. (ww.h.//............. (w.(-i-1))
{compute the ith moment, where ^ is the entrywise power]
8: end for
9: y + Re (1FFF((F))( og)
fo is the entrywise (i.e., Hadamard) product)
conceptual only, explicitty computed
Input
Trainable At
Discretize and Compute the Output
Parametertze
Identify
Continuate
H
(A, B, C, D)
D,
Impulse Response
Impulse Response
Computing Y+
The parameters fip impuise resporse that is not the one app inputs.
Air
The discrete impulse transformed continuous one, which will be discretzed respect different.de dt.
Figure 5: A flowchart that illustrates how the Hankel matrix H is used to compute an output se- quence y given an input sequence u.
With L processors, we can compute the entries of g in Algorithm in parallel, each of which takes (n) time. Computing the FFT and iFFT takes OLL L). Overall, the evaluation of the Hankel- Hankel-parameterie parameterized LTI system takes Ö(L + n) time and O(L) space, which agree with the complexities of the S4 and S4D models. To make the model recurrent during the inference time, one either identify system (A, B, C) whose Hankel operator is H and compute if it is an S4D model (Kramer & Gorodetsky, 2018; Aumann & Gosea, 2023), or directly compute the convolutional kernel using the iFFT of g in Algorithm 1.
Advantage I: A HOPE-SSM has a High Numerical Rank, We can build upon Bryc et al. (2006) and Nekrutkin (2013) prove the following result about random Hankel matrices.
Theorem 3. Let h hg.... a sequence of i.i.d. random variables with mean and variance that have finite third moments. We almost surely have that for any e 0, the (e/vIn(n)) of H, is ((n), where H is the n x n Hankel matrix defined in eq. (5).
Hence, if we ignore the logarithmic factor of /in(n). then the numerical rank of random Han- kel matrix should be proportional to always randomly initialize a high-rank LTI system with HOPE; even better, system parameter- ized by HOPE does not lose rank during training (see Figure 6), because the low-rank systems are themselves rare in the space of the Markov parameters (but not in the space (A, C)).
+ co. That means unlike the S4D model, we can
Ad Advantage II: A HOPE-SSM is Numerically Stable under Perturbation. Unlike the LTI system, a Hankel matrix H is very numerically stable under perturbation, as shown in the following theorem.
Theorem 4. Let h E x be vector and G be the transfer function defined in eq. (11). Suppose perturb h to h and let & be its transfer function. Then, we have ||G Gl vnl h
hl12-
8

---

Published as a conference paper at ICLR 2025
Test Accuracy of HOPE-SSM
Hankel Singular Values
90
At Initializatio
10²
70
Accuracy
60
S4D-init
S4D-init (untrained)
50
S4D-niit
1374
97*
10"
105
10
40
intt, (untrained)
After 10 Epochs
105
840 init
30
S4D-ini, (untrained)
105
20
HOPE-S4
HOPE (untrained)
10
20
100
Epochs
( (1)))//r (H)
Figure 6: The test accuracy of the HOPE-SSM the SCIFAR-10 task and the evolution of the Hankel singular values of the model. The plots are to be compared with Figure and Figure 3.
Therefore, the numerical stability of the HOPE-SSM does not depend on the parameter h itself. Consequently, our HOPE-SSMs are trained without having to rescale the Markov parameters h
Advantage III: A HOPE-SSM's Memory Does Not Fade. While many LTI systems are tailored for long-term memory (Voelker et al., 2019; Gu et al., 2020), an asymptotically stable system must inevitably suffer from an exponential decay in its memory (Agarwal al., 2023). This can be
manifested by the Hankel matrix: since No
yi
H
u ...
we can write
yJ Σ H H k=1
u
Σ
H Ho.st--iu
J20. 0.
(6)
That means the effect of the input u on the output y, depends on the magnitude of Ho.k+j-1- Hence, the decay of Ho.rl gives us a measurement of the decay of the memory. For discrete LTT system, we have by definition that Ho. = CA'B. B. Since the spectrum of A for an S4D model, regardless of At, is contained in the open unit disk, A is a contraction operator and the "memory" of the system decays as time goes by. Asymptotically in time, this decay of (Hg.el exponential, and for most systems, it starts at the very beginning when t increases from 0.2 However, we parameterize the LTT system by the Markov parameters in the Hankel matrix, then Ho..| h, which does not have to decay as long as < n. We acknowledge that when 2 n, we have Ho.c = O. which means the LTI system has essentially memory after time n. We remark, however, that our HOPE-SSM utilizes the continuous-time LTI system associated with Hankel matrix H. That is, from a continuous-tin
perspective, unlike S4D, our system's ' memory does not decay for t E [0, n] (see Figure 7). Hence, even with long sequence whose length is much larger than n, by setting the sampling period At to small enough, our HOPE-SSM could still enjoy non-decaying memory.
EXPERIMENTS AND DISCUSSIONS
Experiment I: Singular Values of a HOPE-SSM. In this section, we implement randomly initial- ized HOPE-SSM learn the SCIFAR- 10 task. We use the same model hyperparameters as the S4D models in section 3. In particular, the Hankel matrices in this model are 64-by-64. We randomly initialize the Hankel matrix and not set smaller learning rate for the Hankel matrix entries h, i.e., all model parameters except for A/ have the same learning rate. In Figure 6, we show the test accuracy and the Hankel singular values of the HOPE-SSM. Compared to Figure 2, a random HOPE-SSM can be trained to high accuracy. In addition, training does not reduce the numerical rank a Hankel matrix. This corroborates our findings in Theorem 3 and Theorem 4. Note that since used the log-log scale plot the histograms, the small relative Hankel singular values make up a misleadingly large portion of densities in Figure 6 than they really do.
In particular, this is the for HiPPO-LegS (see Figure 7).

---

Published as a conference paper at ICLR 2025
Test Accuracy on noisy
Memory Decay of Systems
100
10.6
Accuracy
10
40
10a15
HOPE-SSI SSM
HOPE-SSM
10
$4D
20
20
40
60
80
100
Epochs
Figure 7: Left: the test accuracies of the $4D model and our HOPE-SSM on the noisy-SCIFAR task, Right: unit impulse at f = acted on the LTT system. The plot shows the decay of (t) as increases. Data are collected for all 512 LTI systems in trained model. The dark curve shows the median of [t) over the 512 numbers. The darkly shaded region is from the first quartile to the third quartile. The lightly shaded region is from the minimum to the maximum.
Experiment I:: HOPE-SSMs Have Long Memory. In section 4, we claim that HOPE-SSM benefits from non-decaying memory. We show this experimentally in this section. To do so, for each flattened picture in the sCIFAR-10 dataset, which contains 1024 vectors of length 3, we append random sequence of 1024 vectors of length to the end of it. The goal is still to classify an image by its first 1024 pixels. We call this task noise-padded CCIFAR-10. This task obviously requires long memory so that the earlier data can still be retrieved after the noises are taken. We train both an S4D model and our HOPE-SSI to learn this task, using common sampling period of At 0.1 (see Appendix K.2 for different values of At). We see in Figure 7 that the HOPE-SSM significantly outperforms the S4D model this task. To understand this gap, give unit impulse t to the LTI systems both the trained S4D model and our HOPE-SSM. We watch how the impulse response (t) decays time goes by. In Figure 7, we see that the memory of the trained S4D model decays exponentially while that of the trained HOPE-SSM does not decay at all for t E [0, 64]. where n 64 the size of the Hankel matrix. This is exactly what we expected in eq. (6).
Experiment III: Performance in the Long-Range Arena. Finally, we present the performance of HOPE-SSM on large datasets. We use the same model architecture as in the S4D paper (Gu et al., 2022a), except that we replace the L.TI blocks with our HOPE blocks. The specific model and training hyperparameters are reported Table in Appendix K. We show the performance of our model in Table 1. We see that our HOPE-SSM outperforms most sequential models many tasks.
Table 1:
Test accuracies in the Long-Range Arena of our HOPE-SSM and other models. We report the median and the standard deviation of executions with 5 random seeds. The bold (resp. under- lined) numbers indicate the best (resp. second best) performance on task. An entry is left blank if no result found. We use the same model sizes as those in the S4D model.
Model
ListOps
Text
Retrieval
Image Fathfinder Path
Avg.
DSS (Gupta et al., 2022)
57.60
76.60
87.60
85.80
84.10
85.00
79.45
S4++ (Qi al., 2024)
57.30
86.28
84.82
82.91
80.24
Reg. S4D (Liu
2024)
61.48
88.19
91.25
88.12
94.93
95.63
86.60
Spectral SSM (Agarwal ct al., 2023)
60.33
89.60
90.00
95.60
90.10
Liquid $4 (lasani et al., 2023)
62.75
89.02
91.20
89.50
94.80
96.66
87. $7.32
S5 (Smith et al., 2023)
62.15
89.31
91.40
88,00
95.33
98.58
87.46
S4 (Gu ct al., 2022b)
59.60
86,82
90.90
88.65
94.20
96.35
86,09
S4D (Gu al., 2022a)
60.47
86.18
89.46
88.19
93.06
91.95
84.89
HOPEESSM
62,60
89.83
91.80
88.68
95.73
98.45
87.85
CONCLUSION
In this paper, we presented a new theory based on the Hankel singular values to understand the parameterization scheme, called HOPE, that is based on the Markov parameters in a discrete Hankel operator. We proved that a HOPE-SSM can be robustly initialized and trained and has long memory.
difficulties in initializing and training an SSM. We proposed
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
AY was supported by the SciAl Center, funded by the Office of Naval Research under Grant Number N00014-23-1-2729, NBE would like to acknowledge NSF, under Grant No. 2319621, and the U.S. 1231 and DE-AC02-05CHI
Department of Energy. under Contract Number for providing partial support of this work. We thank the anonymous reviewers for their comments that helped improve this paper. We would also like thank Alex Townsend, Anil Damle, and Sarah Dean for some inspiring discussions.
REFERENCES
Vadim Movsesovich Adamyan, Damir Zyamovich Arov, and Mark Grigor evich Krein. Analytic properties of schmidt pairs for a hankel operator and the generalized schur-takagi problem. Matematicheskii Shormik, 128(1):34-75, 1971.
Naman Agarwal, Daniel Suo, Xinyi Chen, and Elad Hazan. Spectral state space models. arXiv preprint arXiv:2312.068377 2023.
Quirin Aumann and Ion Victor Gosea. Practical challenges in data-driven interpolation: dealing with noise, enforcing stability, and computing realizations. arXiv preprint arXiv:2301.04900 2023.
Anthony Austin. On trigonometric interpolation in an even number of points. Electronic Trans- actions on Numerical Analysis, 58:271 1-28,, 2023.
Jonathan Baker, Mark Embree, and John Sabino. Fast singular value decay for лyaрunov solutions with nonnormal coefficients. SIAM Journal on Matrix Analysis and Applications, 36(2):656-668, 2015.
Alex H Barnett. How exponentially ill-conditioned are contiguous submatrices of the fourier matrix? SIAM Review, 6411), 2022.
Arup Bose. Patterned random matrices. Chapman and Hal//CRC, 2018.
Wlodzimierz Bryc, Amir Dembo, and Tiefeng Jiang. Spectral measure of large random Hankel, Markov and Toeplitz matrices. 2006.
Daniel Fu, Elliot L Epstein, Eric Nguyen, Armin W Thomas, Michael Zhang, Tri Dao, Atri Rudra, and Christopher Ré. Simple hardware-efficient long convolutions for sequence modeling. In International Conference on Machine Learning, pp. 10373-10391. PMLR, 2023.
Keith Glover. All optimal Hankel-norm approximations of linear multivariable systems and their L,00-erorr bounds. International journal control, 39(6): 111--199, 1984.
Leslie Greengard and June Yub Lee. Accelerating the nonuniform fast fourier transform. SIAM review, 46(3):443-454, 2004.
Albert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces. arXiv preprint 2rXiv:23/2.00055,, 2023.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. Advances neural information processing systems, 33: 1474-1487, 2020.
Albert Gu, Karan Goel, Ankit Gupta, and Christopher Ré. On the parameterization and initialization of diagonal state space models. Advances in Neural Information Processing Systems, 35:35971- 35983, 2022a.
Albert Gu, Karan Goel, and Christopher Re. Efficiently modeling long sequences with structured state spaces. In International Conference on Learning Representations, 2022b.
Albert Gu, Isys Johnson, Aman Timalsina, Atri Rudra, and Christopher Ré. How to train your hippo: State space models with generalized orthogonal basis projections. International Conference on Learning Representations, 2023.
11

---

Published as a conference paper at ICLR 2025
Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces effective structured state spaces. Advances in Neural Information Processing Systems, 35:22982-22992 2022.
Moritz Hardt, Tengyu Ma, and Benjamin Recht. Gradient descent learns linear dynamical systems. Journal of Machine Learning Research, 19(29):1-44 44, 2018.
Ramin Hasani, Mathias Lechner, Tsun-Hsuan Wang, Makram Chahine, Alexander Amini, and Daniela Rus. Liquid structural state-space models. International Conference on Learning Repre- sentations, 2023.
Boris Kramer and Alex A Gorodetsky. System identification via car-factored hankel approximation. SIAM Journal on Scientific Computing, 40(2):A848 2018.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alan J. Laub, Michaelt Hcath, C Paige, and R Ward. Computation of system balancing transforma- tions and other applications of simultaneous diagonalization algorithms. IEEE Trans. Automat. Contr, 32(2):115 1222,,15-122, 1987.
Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. What makes convolutional models great on long sequence modeling? Eleventh International Conference on Learning Rep- resentations, 2023.
Fusheng Liu and Qianxiao Li. From generalization analysis to optimization designs for state space models. arXiv preprint arXhv:2405.02670, 2024.
Charles Martin and Michael W Mahoney. Implicit self-regularization in deep neural networks: Evidence from random matrix theory and implications for learning. Journal of Machine Learning Research, 22(165):1-73, 2021.
Charles H Martin, Tongsu Peng, and Michael W Mahoney. Predicting trends in the quality of state- of-the-art neural networks without access to training testing data. Nature Communications, 12 (1):4122, 2021.
Yuji Nakatsukasa, Olivier Sête, and Lloyd N Trefethen. The aaa algorithm for rational approxima- tion. SIAM Journal on Scientific Computing, A 1494-11922222 2018.
VV Nekrutkin. Remark the norn of random hankel matrices. Vestnkk St. Petersburg University: Mathematics, 46:189-1999 192, 2013.
Antonio Orvieto, Samuel L. Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pas- canu, and Soham De. Resurrecting recurrent neural networks for long sequences. arXiv preprint arXiv:2303.06349 2023.
Antonio Orvicto, Soham De, Caglar Gulcehre, Razvan Pascanu, and Samuel L Smith. Universality of linear recurrences followed by non-linear projections: Finite-widds width guarantees and benefits of complex eigenvalues. In Forty-first International Conference on Machine Learning, 2024.
Vladimir Peller. An introduction to hankel operators. In Hankel Operators and Their Applications, pp. 1-59. Springer, 2003.
Biqing Qi, Junqi Gao, Dong Li, Kaiyan Zhang, Jianxing Liu, Ligang Wu, and Bowen Zhou. S4++: Elevating long sequence modeling with state memory reply. 2024.
Jimmy T.H. Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for se- quence modeling. In The Eleventh International Conference Learning Representations, 2023.
Yi Tay, Mostafa Dehghani. Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Scbastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. International Conference in Learning Representations, 2021.
Aaron Voelker, Ivana Kajié, and Chris Eliasmith. Legendre memory units: Continuous-tiin time repre- sentation in recurent neural networks. Advances in neural information processing systems, 32, 2019.
12

---

Published as a conference paper at ICLR 2025
Shida Wang and Qianxiao Li. Stablessm: Alleviating the curse of memory in state-space models through stable reparameterization. arXiv preprint arXiv:2311.1499) 2023.
Shida Wang and Beichen Xue. State-space models with layer-wise nonlinearity are universal ap- proximators with exponential decaying memory. Advances in Neural Information Processing Systems, 36, 2024.
Heather Wilber, Ethan N Epperly, and Alex H Barnet.. A superfast direct inversion method for the nonuniform discrete fourier transform. arXiv preprint arXiv:2404.13223, 2024.
Annan Yu and Alex Townsend. On the stability unevenly spaced samples for interpolation and quadrature. BIT Numerical Mathematics, 63(2):23, 2023.
Annan Yu and Alex Townsend. Leveraging the hankel approximation and data-driven algo- rithms in reduced order modeling. Numerical Linear Algebra with Applications, pp. e2555, 2024.
Annan Yu, Aruur Nigmetov, Dmitriy Morozov, Michael W. Mahoney, and N. Benjamin Erichson. Robustifying state-space models for long sequences via approximate diagonalization. In The Twelfth International Conference on Learning Representations, 2024.
Kemin Zhou and John Comstock Doyle. Essentials of robust control, volume 104. Prentice Hall, Upper Saddle River, NJ, 1998.
13

---

Published as a conference paper at ICLR 2025
A MORE BACKGROUND ON THE LTI SYSTEM AND HANKEL OPERATORS
The purpose of this section is to provide more thorough exposition of section which leaves some concepts that are unnecessary in order to understand the main text. Let [ = (A, B, C,C be continuous-time LTI system defined in eq. (I). One take bilinear transformation to obtain discrete LTI system:
= (I+ B= C=C(1+A\V2, D + C(I-A)-
The bilinear transformation is invertible and defines one-to-one correspondence between in eq. (1) and [ = (A, C. given by
x = Ax Bug
yk CX2 DUg-
The transfer functions of I and are
G(s) C( A and
= C(xI- BB-
respectively. The two transfer functions are equivalent via Mobius transformation:
G(s) = G ((1 + (1-())111))))1))
G(=) G ((= +))+++)))
The importance of the transfer functions is that they bring the inputs to the outputs in the Laplace domain by multiplication, which reduces to the Fourier domain if we assume that u is bounded and compactly supported:
(s) (()))
y = G
where the hat of function and vector means the Fourier transform and the Fourier coefficients, respectively, and w is the vector of roots of unity.
Given continuous-tine LTI system one can define its Hankel operator by
(Hv) - 1
H : (0) + (0, oo),
The Hankel operator maps the past inputs to the future outputs, i.e., if u(t) 0 for t 2 and define v() = u(-t), then we have (4) (Hv) Analogously, the Hankel matrix of discrete LTI system is doubly infinite matrix defined by
22
H = CA + "JB,
i.j 0.
The Hankel matrix has the similar physical interpretation: if u. = 0 for all A 2 0, then we have [ y. ...] H V_ ...] Both H and H are bounded linear operators of rank S n, the number of latent states. In fact, the singular values 01 (H 2 ( 2 2 on (H)
of are equivalent those of H. and they are called the Hankel singular values of and r.
B MORE BACKGROUND ON HANKEL SINGULAR VALUES
In section 2, we define the Hankel singular values di.... Jn to be the singular values of the finite- rank bounded linear Hankel operator separable Hilbert space. Throughout the paper, treated them as black boxes and used their distributions to understand the performance of SSMs. The goal of this section is open the black boxes and introduce singular values. Note that the proof of Theorem to be presented in Appendix E heavily relies on the background discussed in this section. The concepts in this section can be presented on discrete LTI system (A, B. C. D).
useful properties of the Hankel
continuous- time LTI system (A, B, C, D) analogously We focus mainly on a continuous time system for cleanliness. Since D has no effect on the Hankel singular values, further assume that D and write only r (A, C)
14

---

Published as a conference paper at ICLR 2025
B.1 HANKEL SINGULAR VALUES FROM BALANCED REALIZATION
One of the most popular ways to compute the Hankel singular values is via the so-called balanced realization. Assume (A, B, C) is asymptotically stable, i.. the spectrum of A contained in the open left plane. Then, there exist two Hermitian and positive semi-definite matrices P E C and Q E C" such that
AP PA B =0, A-Q + QA - CCC=
(8)
The equations in eq. (8) are called the Lyapunov equations and P and Q are called the controlla- bility Gramian and the observability Gramian, respectively. They can be explicitly expressed by the following matrix integrals:
Q Q= f exp(A*t)C Cexp(Aftdt.
P
(9)
The controllability Gramian P is positive definite if and only if the system is controllable, i.e., for any Xo, X1 E CC" and any T >> O, there exists an input u on T] that makes x(7) = X1 when x0) Xo. Likewise, Q is positive definite if and only if the system is observable, i.c. for any T' 0, the initial state x0) can be determined by the input and the output y on [0, 2] (Zhou & Doyle, 1998).
The singular values of PQ turn out to be exactly the squares of the Hankel singular values, i.e., of. o....., o of the system In general, P and Q are dense matrices. However, one can use the so-called balanced realization algorithm (Laub et al., 1987) to compute an equivalent system r, = (A, B,, C₂) VV-AV, V- BB, CV), where V E Cuxn an invertible matrix, so that its Gramians P3 and Q are equivalent and diagonal, i.e.,
Ps Q = diag( on))
Balanced realization is an algebraic method that is based singular value decompositions (SVDs). In practice, it is a very popular method to compute the Hankel singular values system.
B.2 HANKEL SINGULAR VALUES AS RATIONAL APPROXIMATION PROBLEM
The balanced realization gives us a good way to compute the Hankel singular values in practice. However, it does not offer too much insight in theoretically analyzing them. The theory of Hankel singular values is usually derived via function approximation. Here, we introduce how Hankel singular value can be reframed as the solution let H (resp. H be the Hardy space with functions h C - Cm that are bounded and analytic in the open right (resp. left) half-plane. The non-tangential limit of h exists almost everywhere on the imaginary axis, and by the Maximum Modulus Principle, we must have
rational approximation problem. To this end, we
|bllo == ess suPR(<))) (h)))ll
sup [|^()]]2, Re())>0
h H
and
|/]bo = ess sup suppe())=ollb(()]] = sup [1(s)]12, Re(s)<0
hE H
The Adamyan-Arov Krein (AAK) Theory (Adamyan et al., 1971) says the following:
Øc+1 = inf || R Flloo, 0 S k < 1,
(10)
RE.F
where R& ranges over all rational functions with at most & poles, all contained in the open left half- plane, and F ranges over H In fact, discussed in section 2, R₂ is the transfer function of reduced system I (, with A E Clxk Hence, eq. (10) tells us that the transfer function of I' can be well-approximated by rational functions, then it has fast-decaying Hankel singular values. The other direction is not true, due to the existence of F. That is, if the Hankel singular values decay fast, then it does not necessarily mean that G can be appl-appro by rational functions. However, section 2 shows that this is true the sum of the tails of the Hankel singular values decay rapidly.
15

---

Published as a conference paper at ICLR 2025
C COMPARISON TO RELATED WORKS
One of the advantages of our HOPE-SSM its long-memort capacity (see section 4). Notably, there have been two prior works that also consider the memory issues of an SSM (Wang & Li, 2023; Agarwal et al., 2023). In this section, we briefly introduce the two works and compare them to our HOPE-SSM. The Sable-SSM proposed by Wang & Li (2023) is based on theoretical analysis of stable representations of long-memory SSMs. In that work, it is shown that without any reparam- eterization of the matrix A, an LTI system cannot stably represent dynamics with long memory. That is, one can slightly perturb the LTI system to break the long memory. Based on the theory, it then proposes, in addition the traditional log(Re(A)) parameterization of the real parts of A, dif- ferent parameterizations to enhance of stability of long-meoory representations. Our HOPE-SSMs are also based on different parameterizations of LTT systems. While a Stable-SSM reparameterizes A, B, and C, we totally give up representing the system matrices but instead rely on the Hankel operator. That is, a HOPE-SSM has addition two advantages and II) shown in section 4. More- over, it is easy to directly change the memory decay of HOPE-SSM to account for recency bias (see Appendix L).
The Spectral-SSM, proposed in Agarwal et al. (2023) is based the spectral filtering mechanism. The idea is to project the input sequence adaptively onto a predefined basis and then compute the output by taking a linear combination of the projections. The model is convolution-based, similar to HOPE. However, the two models attack the varying-length sequences different ways. A Spectral- SSM handles varying-length sequences by fixing truncated set of basis that is independent of the input length, while a HOPE-SSM defines a continuous-time convolution kernel to be discretized by trainable a At to handle sequences of different lengths. Finally, Spectral-SSM may not be equivalent to standard SSM with LTI systems, whereas HOPE-SSM is indeed one with LTI systems.
D THREE DIFFERENT INITIALIZATION SCHEMES
In this section, explain the details of initi, inity, and init; in the main text. We stress again that we do not claim that these initialization schemes are representative. Indeed, we only use them to elicit the story of the Hankel singular values. As mentioned in the main text, inits is the HiPPO-LegS initialization scheme (Gu et al., 2020). To sample a random with initi, we create random samples of the transfer function {(s,, Gj)}ر== where 8j E E and G, C. We then identify a system I whose transfer function G satisfies that G(is;) Gj. The way we identify this model is via the so-called AAA algorithm (Nakatsukasa et al., 2018; Aumann & Gosea, 2023). For ini t2, we sample a discrete system by assuming the diagonal entries of A = diag(a1,... an) are uniformly sampled on the unit disk and B C random vector with each entry sampled i.i.d. from normal distribution (00, 1). We then compute the corresponding continuous-time system from the discrete system using the bilinear transform.
E PROOF OF THEOREM 1
Let G be the transfer function of random system T i.e.,
= C(al
By the AAK theory, the Hankel singular values T can be studied via the rational approximation of G. Since the matrix D does not affect the Hankel singular values system, we assume, without loss of generality, that = O. We let o1..... on be the random variables that are equal to the singular values of the random LTI system Tz. We approach Theorem 1 in three steps:
1.
We separate out the poles of the transfer function G of (A, B, C, 0) that are close to the boundary of the unit disk. This breaks G into two low-rank systems Gj and G2 where G is low-rank because it has few poles and G2 low-rank because its poles are far away from the boundary.
2. We then estimate the decay of the singular values of G2 using the information of the maxi- mum moduli of its poles.
16

---

Assume G(z) can be written as Published as a conference paper at ICLR 2025
3. Finally, control in probability. This gives control on the relative singular values.
We will make these three steps into three lemmas and use them to derive the result at the end. Lemma 1. Given 7 > O, with probability at least 1 8, there are at most n poles (z)) outside the disk D(0, 1 n n>), where
In(1/5)
B 1 logn
n
2n
Proof. Let Z be the number of poles inside D(0, 1 n 7)).
Then, Z has binomial distribution
2 ~ Bnn, n 7
From Hoeffding's inequality, we have
71 12 ) exp (-2n (-n 7a n 8-21)
P(Z n - n²) exp -2n 1 - na
n
Set
In(1/8)
In(1/6)
B = 1+ log
n= +
= ya + -lgg
11 V
2n
2
Then, we have
In(1/5)
n 3-1
70
2n
so that
(n(1/8)
(2 < n n²) S exp
2m
6.
2n
This finishes the proof.
Lemma 2. For any y > 0, let the random variable the number of poles of G(z) inside D(0, 7) Let n y be given. Then, with conditional probability (given k) at least 1 - 6, we have
(n-b)=n<42 S O (VO(VV (vn++((n(1/8))11 e ((((m1))
where the constant in O is universal.
Proof. Let ,,,...,22 2g be the poles of G(2) inside D n 7)))
k
-))) +
C
2 2
where (z) is degree-(n k) rational function with poles inside the annulus of inner radius n - and outer radius and 0's are i.i.d. random variables with distribution N(0, 1). We can further write
b
8
Σ
Σ
c2
2z
1=0
j=1
By the AAK theory, for any > 0, we have
20
(n-A)+K S sup Σ
G2
|c z
|11
|||||
Σ
|z
12
jm
where c c= -c1 c1] and z lzf...., TT and the last step follows from Hölder's inequality. Since ||c|[3 follows the x distribution, for M > n. we have that
P([|c]| > M) s exp ( n M
M
In
n
17

---

Published as a conference paper at ICLR 2025
Hence, there exists universal constant C such that when M 2 ((I((1/8) +n)², we have
M 6.
P([e 2 > M) S exp
2 n
Moreover, since | $ (1 n y for all S I k, we have
2z' 1|2 S Vn(1 n 7...
That is, with probability least 1 8, we have
(n- & O (vii(11/0)+)) Vn (1-n~ =0 (V(])(((((((/))))) v1-
j=k
Suppose K 2 n² + Then, we have
())o-))))))) ((6933 (au
(1 (1- k- S (1-n (1-n7))aa)) = ( (11-
Since (1-n~ + el + 0c, if > 7/ then (1-n~ k2 decays faster than any negative
power of n. Hence, we have
(n-k)) SO (1 (nlom)))
as desired.
Lemma 3. With probability at least
8, the leading Hankel singular value on satisfies
01 2 O(vnd),
where the constant in O is universal.
Proof. The leading Hankel singular value os is equivalent to the spectral norm of the Hankel matrix
CB
CAB CAAB B
CA
2
B
CAB
...
CA B
Hence, we have
91 CB
where CB/VB- N(O01), 1). Hence, if set M C Cv/ for universal constant C have
P(a s M) < P[CCB < M) P CB
/ S M/V S8.
This completes the proof.
Now, let's assemble our ultimate statement.
Proof of Theorem I. By Lemma 2 and Lemma 3, with probability at least 1 - -8/2, we have that
(m-kknn+2) < 0 < (Vi)((((1/0)++)))))) ((n(--1))
Hence, we set k so that
n 2 n Vn m)) nnIn (0 (0-33112 (1 (1((t1(()))
Here, is guarantee that M >
18

---

Published as a conference paper at ICLR 2025
for sufficiently large universal constant C O, then we guarantee that
(x=k+n=42) S.
01
By Lemma 1, we have that with probability at least - -8/2.
In(2/0)
Snn
B + logn
" na +
2n
Set 7 1/(1 a). Then, we have
)
In (2//88) 2n2-2-ya
In(2/8)
8 1 1
na 1++
1 ya logn
1+
2n1-29a
< 1
1 In(2 + V /In(1/0)/2)
+ logn (1 + /ln(2/))/2) <
14a
1+a
In(n)
Since
n +2 + 0 (n (8 (0-30(1/)-111) so so(n0 (0 (8-3/2(-111)
The claim is proved.
F PROOF OF THEOREM 2
In this section, we prove Theorem 2. Our proof focuses on the worst-case perturbation by construc- tion. As consequence, it simultaneously proves the sharpness of the result. Intuitively, consider rational function
bc
since we only care about its values on the imaginary axis, the closer the pole a is the imaginary axis, the less stable it is. On the other hand, it is obvious that the size of be also controls the (absolute) conditioning of the rational function. We state the rigorous proof below.
Proof of Theorem 2. Without loss of generality, we assume that B = B = 11 transfer functions of I and i are
1] The
G(s) Σ
and
G(s)
j=1 83
8j
respectively. Then, for any the imaginary axis, have
Cj
C 3,) 2, s;)
Cj8 C38 E,s -)) (8 82)
2,33 + -2,33 255
8j
83
(s 88)(8 8,)
Ccj Es 3,1 + 10
[3 - 3,1
Cj Eg1
12,1 [sj 3,1
+
|s 851 1s 3j
8j
1s 53 83
AB
2 ccl AA
[e(ss))
Re( (e(ss))2/22
Hence, we have
AB
lc,1 AA
|| 01 Σ
+4 R2(
Re((;;]
cyl
< BAB max
+ AAndA max 3
Re(ss)
[R((,)) 2-
'Otherwise, we redefine B B redefined transfer functions unchanged.
[1
T B
C. and C = BT o č. and the
19

---

Published as a conference paper at ICLR 2025
This proves the upper bound. To prove the lower bound, let jı be index that maximizes 1/ 1/|Re(s;)) and j2 be an index that maximizes lcyl (e())Re(ss)]= Define I'B by perturbing oj2 oj2 ÁB. Then, we have
AB
1
|| - GBllx
AB max
$j
Re(ss)
Define A by perturbing 8ja to 8jz +
A Then, we have
|| GAlloo -c3al
c AA
$j2 Sj
8jo
A
(s
8jz)
8jz + AA
lcjl
DA
A
max
[
[
This proves the sharpness of the theorem.
Next, we show that the factor n in Theorem 2 is in fact also tight.
Proposition 1. For any n, there exists system I' of size and two systems I' and F' perturbed from I, with transfer functions G, GA. and GB, respectively, that satisfy the perturbation conditions in Theorem 2 and have
|| GAll 2 AAA max 1b
1
||G GBlo 2 ndB max
[Re(a)))?
[Re(ay))
Proof. We take the single partial fraction from the proof the lower bounds in Theorem and repeat it for times to construct r. This would multiply the size of the transfer function perturbation by a factor of n.
G PROOF OF THEOREM AND THEOREM 4
The proof of Theorem 3 is straightforward assembly of two results in random matrix theory. The first result, due to Nekrutkin (2013), controls the Hankel norm a (H.) of a random Hankel matrix, whereas the second result by Bryc et al. (2006) studies the distribution of all absolute singular values o (H,) of random Hankel matrix. Our study of the relative Hankel singular values is achieved by taking the quotient of the subjects of the two prior works.
Proof of Theurem 3. By Nekrutkin (2013), with probability 1, we have that
H.,) H. O O(vnlan).
Define K,, H,, (1: (1:(11),,::: Then, by Bryc et al. (2006), with probability have that u(Ka// /n) converges in distribution fixed probability measure, where
nn/2]
1
m(Kn// (Kn/Vn)
8 (x.(K.//V)
n/22
is the spectral measure of K, nn. Since K, is symmetric. the singular values of K,, are the moduli of the eigenvalues of K,, Hence, fix some 0, we have that
[ ( (K, H e/ [n(n))] M(T.).
Since Kn is a submatrix of H,, we have o, (H,) 2 oz (K,) for all S S [n/2]. Hence, its (c/ (i(()) -rak can be controlled as
o HH.) (H.)) e/ e/vin(n))
(Kl, >e//i(e)))))) =Q(n).
This finishes the proof.
20

---

Published as a conference paper at ICLR 2025
We remark that in the statement of Theorem 3, study the e/ (ln(n))((aaaa)a of the Hankel matrix instead of the e-rank. The reason is that, unlike the singular values random matrix, the spectral measure of normalized random Hankel matrix H,/vh has unbounded support. In order to pull the 1/vIn(f factor out and make into the (mn) bound, need study the distribution of the spectral measure of H / As pointed out by Bose (2018), however, this seems to be hard problem. Nevertheless, we can empirically test the statement by numerical experiments.
Next, provide the proof of Theorem 4, which is almost immediate from Hölder's inequality.
Proof of Theorem 4. By Hölder's inequality, we have
|| - =l = | - G S max
h -,
hl12y/n.
H SOME NUMERICAL. EXPERIMENTS ON HANKEL MATRICES
H.1 NUMERICAL RANKS OF RANDOM LTI SYSTEMS RANDOM HANKEL MATRICES PRACTICE
While the theoretical part of our paper focuses on the e-rank of an LTT system, in the main text, we showed the distribution of all Hankel singular values of different LTI systems. The main reason for showing the histograms instead of a single number (i.c., the e-rank) is that the histogram gives us more information while the c-rank is merely cutoff. In this section, empirically compute the c-rank to verify the two theorems (i.e., Theorem and Theorem 3).
In this experiment, always set 0.01. For every n in experiment, first randomly initialize a random n x n Hankel matrix
he
h
h2
hn
h1
h2
hn
0
H
h2
hn-1
hn-1
where hy are i..d. random Gaussian variables with variance of 1. We compute its e-rank and we repeat the experiment for 1000 trials. Similarly, for every n, we randomly initialize an LTI system with
A = diag(a),....... an), aj Uniform(D).
where the open unit disk in the complex plane and the elements of B C are sampled i.i.d. from (0, 1). We compute its e-rank and also repeat the experiment for 1000 trials. From Figure 8, we see that random LTT system has a low rank, whereas a random Hankel matrix has high rank in the sense that it is about proportional to n. This observation aligns with our theory in Theorem and Thcorem 3,
H.2 HANKEL MATRICES ARE STABLE TO PERTURBATION IN PRACTICE
Theorem predicts that the Hankel matrices are very stable when being perturbed. In this section, we run experiments in parallel with those Figure where we perturb Hankel matrix H. As in Figure 4, we also set the size of the random perturbation to be 1% and 0.1%, respectively, of the original system. Theorem is corroborated by Figure where we see that a small perturbation has minimal effect on the Hankel singular values.
H.3 HANKEL SINGULAR VALUES AFTER TRAINING
In the main text, we showed the distributions of the Hankel singular values at initialization and after 10 epochs. In this section, we show the distribution the Hankel singular values after the training done.
21

---

Published as a conference paper at ICLR 2025
Random Hankel
Flandom LTI System
Ret.. Line (slope
Ref. Line (slope 1/2)
rank, (T)
10
10
10
71
Figure 8: The c-rank of random LTI system of size n, where 0.01. The random systems parameterized by Hankel matrix or by the matrices A, B, and C. The lines are the average rank and the shaded regions indicate the 10%-90% range over 1000 trials.
10
A =0
4,
4, - 1%
10
0 0
10
10.8
10
30
50
60
Figure 9: A random perturbation is added to H. The magnitude of the perturbation is set 0.1% and 1% of the original matrix. We show the relative Hankel singular values 0 of the original and perturbed systems. In this case, the three curves are almost overlapping.
init
initz
After Training
initg
HOPE
After Training
072
109
165
407
(H)
(H)
Figure 10: The distribution Hankel singular values after training.
22

---

Published as a conference paper at ICLR 2025
I ADJUSTING THE DISCRETIZATION STEP VIA NUFFT
In this section, we derive Algorithm 1. If we set At = 1 and discretize r, the convolutional kernel exactly h padded with L- zeros, where L is the length of the sequential input. However, usually want to discretize with a different At. We can do so via resampling the transfer functions of I' and I, which equal (Peller, 2003)
G(s)
Σ f=0
hy ((1 + s)((1 s)) 5-1
+
G(2)
Σ j=0
hyz
(11)
(1))
be the vector of the Lth roots of unity. Given an input u E C of lenghh L, when At 1, the outputs can be evaluated as
(L)
WD
y = iFFT(FFT) o )(w)L))
-(w(4)= (( ((ub))
c(
For different At, one way to think of it is that we have compressed or dilated the time domain of by a factor At. Hence, the frequency domain its Fourier transform ú is dilated or compressed by a factor of 1/At. That is, should relocate our samplers in the frequency domain
1 85 8 /A. w
w
(L,A0))
w (1,00
"LA w L-11
(L)
1 1- (-) (1) /4
w (1)
+1
(12)
(L,A1) are the scaled samplers the time and angular domain, respectively. Then, the output sequence y can be computed, from the nonuniform samples ((w(L,)))) as
where 8) / and wj
y iFFT(FFT(U) G(w)))))))
G(w(LL))) c (1,00)
)iwl- (13)
To understand why eq. (12) holds, assume there exists a continuous function u on the unit circle HD where the discrete inputs u are sampled from. Then, FFT allows us to write into the Fourier expansion:
L-1
[iFFT(u))s exp (-2mi L =
u(2) =
==0
By the property of the transfer function eq. (3), we know that the output function y is equal to
u(2) = Σ (FFT(U)], ((w) exp
(22i 1
L
8,
To compute the discrete output y, one samples at = wb ..... wh which is equivalent to an inverse FFT FFT(U) ((w)()).
Now, if we want to change At, one way to think of it is as if our LTI system is unchanged, but the time domain of u(z) is scaled by factor of At. That is, now have
(2) Σ [F)]( exp (-2mi (-2mit2/(00)
2(A0)
1 8/A
8/ A/A
+
The output function ((At) is now equal to
L-1
(2) = Σ (FFTTWW), (()l))))) exp 1-2Ti (-2mi
==
'Note that we could alternatively scale the angular domain instead of the time domain, i.e. 2(0)) = a/At. The difference is the level of discretization. However, we find that discretizing the time domain gives us better performance in general.
23

---

Published as a conference paper at ICLR 2025
Ar =
vet) and u
v(f) and y
glon(e) and you
(1) Joees
Figure 11: A visualization of appendix I.
The only real difficulty that when we sample ااار at = w/ (L)
w obtain y(A)), we note
that z(Ar) (L,)))) L-1
(L are uniform on the unit circle. Hence, it cannot be achieved via inverse FFT. However, this sampling can be done via the so-called nonuniform FFT (NUFFT), which also takes Ol. L). In general, one can interpret FFT as the procedure of evaluating function
f(w) = Σ fee (-jw), j=0
at the degree-L roots of unity (WL-)...WLI.) The NUFFT is the procedure of evaluating exactly the same function f. but at potentially nonuniform nodes w * w. We remark that NUFFT only used to simplify the representation of our derivation of Algorithm 1. It is not explicitly used in the algorithm, even though the numerical stability of the NUFFT procedure is studied in Barnett (2022); Yu & Townsend (2023); Austin (2023), and fast algorithms can be found in Greengard & Lee (2004); Barnett (2022); Wilber et al. (2024).
Using the NUFFT at the uneven samples (4.A0), obtain
((t) NUFFT(FFT(U) ((w()))))).
Now, consider the following function
L-1
(z) (2) (())) (=((20))
Σ
[FFT(U)]; c(uf(-01) exp (-2mi
1=0
This output function scaled version of (())) where we scale the time domain by factor of 1/ A/. One can sample g(Dو) at = w/t (L)
using iFFT:
أ(ار) iFFT(FFT(U) ((W()))))).
This leads us to eq. (13).
J CONVERGENCE OF HOPE
Assume that there exists target dynamical system F, = BA, C.) that would like to learn using a HOPE system parameterized by h, where our objective is to minimize the - of the transfer functions. Let G. and G₁ be the transfer functions of the target system and the HOPE
24

---

Published as a conference paper at ICLR 2025
system, respectively. This least-square system can be written as follows:
h1
h2
2 2
2
G
Z
where Z is quasimatrix. Hence, optimizing h is a convex problem. Moreover, the columns of Z are orthogonal!
Proposition 2. Suppose we apply gradient descent on with learning rate 7 < to minimize G 1ll.-G.lee l1. where the 2-norm is taken over the unit circle. Let h()) be the parameter after the k-th iteration. Then, we have
GGan - 2- S (1- (1-1) - G.Il2 S S (1-1))(+1
12
Proof. The proof is immediate from convex optimization theory by noting that the condition number R2 (Z) =
In our setting, we optimize on continuous level. We can also analyze the optimization discrete level, where one takes the samples of G. and Gb. In that case, the matrix Z is no longer a quasi- matrix but instead true NUFFT matrix. Its conditioning has been widely studied in the literature (see (Yu & Townsend, 2023; Barnett, 2022)), making analogues of Proposition 2 easy to derive.
K EXPERIMENTAL DETAILS
In this section, we provide the details of the three experiments presented in the main text.
K.1 ANALYZING HANKEL SINGULAR VALUES USING THE SCIFAR-10 TASK
As mentioned in section 3, in the experiments presented in Figure 2 and Figure 6, we always train an SSM with 4 layers and 128 channels. Each channel in a layer is modeled by an LTI system with 64 states. When rate of 0.001 to A and of 0.01 to the rest. When we freeze the system matrices, then we set the learning rate of A, B and C while keeping that of D be 0.01. Note that the matrix D does not affect the Hankel singular values. All other model parameters are trained with a learning rate of 0.01. For an LTI system parameterized by the Hankel matrix H, we adopt the same setting, except that H is trained with a non-reduced learning rate of 0.01. To compute the Hankel singular values of LTT system (A, B, C, D), we use its balanced realization (see Appendix B). To compute the Hankel singular values of system parameterized by H, apply SVD the matrix H.
parameterize the LTT systems using A, B, C, and D, we assign learning
K.2 TESTING HOPE-SSMS LONG MEMORY USING NOISY-SCIFAR
In this experiment (see Figure 7), modify the sequential CIFAR-10 dataset by padding random sequences to the right. For each sequence of length 1024 from the original dataset, we pad another sequence of length 1024 to the end of it. The entries are sampled independently from the Gaussian distribution on the same magnitude as the entries in the original sequences. We adopt the same model architectures and learning rates described in Appendix K.1 but make two exceptions. First, we fix the discretization size to be At = 0.1, and therefore, it does not need a learning rate. In addition, a canonical SSM decodes the output sequence by first doing a pooling. Here, instead of pooling over all 2048 output vectors, to make the problem more challenging and require longer memory, we only pool over the last 1024 output vectors. These correspond to the output vectors when the noises are fed. We also test the models using different discretization sizes At. We see that when At = 1, the S4D model fails to converge while our HOPE-SSM performs relatively well; on the other hand, when At 0.01, both models tend to have relatively good performance. These observations align with our theory because a larger At means that we put the discrete data on a continuous time domain with longer span; hence, longer memory capacity is needed.
25

---

Published as a conference paper at ICLR 2025
Al = 1
A = 0.1
AL = 0.01
100
100
100
HOPE-SSM SSM
Accuracy
80
540
Accuracy
80
Accuracy
80
60
60
60
40
40
40
20
20
20
HOPE-SSM
840
540
0-
0
20
80
20
60
80
100
20
60
80
100
Epochs
Epochs
Epochs
Figure 12: Performance of the HOPE-SSM and the S4D model on the noise-padded sCIFAR-10 10
task using different values of A.
K.3 HYPERPARAMETERS HOPE-SSMS LONG-RANGE ARENA
In this section, present the table of hyperparametens used to train our HOPE-SSM the LRA tasks (Tay et al., 2021) (Apache License, Version 2.0). (See Table 2.) Our codes are adapted from the code associated with the original $4 and S4D papers (Gu et al., 2022b;a) (Apache License, Version 2.0). Note that compared to the hyperparameters used to train S4 and S4D, we use the same model hyperparameters and only slightly tune the training hyperparameters. All experiments are done on a NVIDIA A30 Tensor Core GPU with 24 GB of memory. The time efficiency of our model is roughly the same as that of the S4D model.
Task
Depth
#Features
Norm
Prenorm
DO
LR
BS
Epochs
WD
Range
ListOps
256
BN
False
0.
0.01
20
100
0.03
(0.001,0.1)
Text
256
BN
True
0.01
0.01
16
150
0.05
(0.001,0.1)
Retrieval
128
True
0.
0.008
0.03
(0.001,0.1)
Image
6
128
LN
False
0.1
0.004
32
1500
0.01
(0.001,10)
Pathfinder
256
True
0.
0.001
0.03
(0.0001,0.1)
Path-X
6 128
BN
True
0.
0.001
16
100
0.04
(0.0001,1)
Table 2: Configurations of the HOPE-SSM model, where DO, LR, BS, and WD stand for dropout
rate, learning rate, batch size, and weight decay, respectively.
K.4 FURTHER ABLATION
We study the role of At in the discretization of HOPE-SSM. Here, we show that is key to have tunable A/ in the model of HOPE. This justifies our continuous-level parameterization of the convolutional kernel.
Table 3: An ablation the HOPE-SSM that shows A/ is essential for good performance of model.
Model
Tistops
Text
Retrieva
Tmage Pathfinder Path-X
Avg.
HOPE-SSM 62.60
89.83
91.80
88.68
95.73
98.45
87.85
HOPE-SSM (At 1)
55.50
86.63
86.12
79.92
91.20
50.00
74.90
L SUPPLEMENTARY EXPERIMENTS: RECENCY BIAS OF HOPE
The HOPE parameterization does not introduce a natural inductive bias over the inputs that fit into the [0, ni] memory window (see Figure 5). In some cases, however, recency bias is desired solve the tasks. In this section, we discuss how the recency bias can be tuned in our model. The first method is change At to ask for more less bias. That if At is set to be larger, then fewer inputs can be fit into the memory window [0, nl., so recency bias is advocated. We also propose different way to tune the bias by introducing an explicit decay to the Markov parameters. That is, For example,
instead of setting H.j- h we use H G+ hits for some Gj 0
26

---

Published as a conference paper at ICLR 2025
9 = (1+ + ,) for some hyperparameter 0. This would introduce natural "memory decay" over the interval [0, n| and hence tune the bias.
We now use synthetic experiment to show that input sequences of length 1000, where the first 990 entries are sampled from i.id. random Gaussian distributions, and the last 10 are sampled from ccos(st) st)) for some random The goal is to predict the frequency & given the noisy input. We train our model using different and the hyperparameters, This task clearly requires recency bias because only the recent 10 inputs are relevant to the output.
tune the recency bias. Our datasets contain
[0, and E [0, 1].
Table 4: The mean-square error in predicting the frequency s given different training hyperparam- eters.
At
0.1
5
10
50
100
0.084
0.053
0.020
0.006
0.006
0.015
-0.25
0.053
0.046
0.022
0.004
0.008
0.015
-0.5
0.055
0.048
0.021
0.008
0.013
0.016
-0.75
0.050
0.027
0.025
0.010
0.014
0.016
0.047
0.025
0.023
0.009
0.014
0.017
-1.5
0.041
0.018
0.022
0.013
0.017
0.020
-2
0.042
0.022
0.024
0.021
0.019
0.023
We observe that as At increases and a gets more negative, the model indeed favors the recent inputs. set 64. Hence, about 64/At At inputs can be fit into the memory window.
In this experiment, setting At = 10 allows the noises to be ignored by the model. In Table 4, we indeed see that it leads the best performance of the model. We remark that since our setting requires hard-threshold recency bias (i.e., we ideally want equal memory on only the last 10 inputs). it is more effective to tune the recency bias by changing At than a. However, the first two columns indeed show that can tune the bias also by changing a. Changing a could be more effective on other tasks that require a soft recency bias
27


Reviews:
[{"review_id": "quNaSRPcFc", "reviewer": "Reviewer_iUDX", "summary": "This work proposes an alternative parameterization for SSMs using the Hankel operator of the dynamical system, called HOPE. HOPE learns the Hankel operator of a linear dynamical system, instead of directly learning the dynamics matrices as in other SSMs. By using techniques and results in Hankel operator theory, authors show that HOPE is more robust to noise and has long memory. Finally, experiments on LRA show that HOPE is competitive with other SSMs and outperforms baselines on several tasks.", "questions": "1. In section 3 before 3.1, how should I think about $\\epsilon$? Under init3, if $\\epsilon=$1e-4, then the frozen model has a higher numerical rank, since there is considerable mass below 1e-4 for the trained model, but the frozen model has worse performance?\n2. Why is numerical rank the correct metric instead of the sum of the smallest eigenvalues? ROM quantifies the approximation error using the latter.\n3. Theorem 2's upper and lower bounds are off by n, which is significant when the hidden dimension is large (regime of interest for high-order LTIs). In addition, Theorem 4 has a $\\sqrt{n}$ on the right hand side, but it's not clear whether the worse $n$ scaling for default SSM parameterization is tight. Can authors comment on this?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper proposes a theoretical framework for analyzing SSMs, and there are many supporting graphs and experiments. The plots are well-executed, and the experiments are LRA has a good set of baselines. I also appreciate the noise-padded sCIFAR-10 experiment as an ablation. The algorithm is clearly written.", "weaknesses": "1. Motivation: random init in models like Mamba also works, so the initialization issues seem to be limited to certain SSMs.\n2. HOPE-SSM does not have non-decaying memory: these are asymptotically stable systems, instead of marginally stable systems, so they cannot have arbitrarily long memory. This point is not clarified upfront in the paper.\n3. HOPE-SSM on Path-X, which is the task with the longest memory in LRA, does not outperform S5. This raises some concerns on the long-memory capability of HOPE-SSM in practice.\n4. Though authors provide expressivity results on HOPE, there is no guarantee on learning with this parameterization (convergence, etc). \n\nPlease also see questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "N10xU00uMM", "reviewer": "Reviewer_JzxW", "summary": "The paper first examines the stability of SSM training and the recently used initialization method through the lens of Hankel operator theory. The authors argue that by decreasing the effective rank of the Hankel operator, the system loses its expressivity for modeling complex sequences. They then propose a new parametrization of LTI systems based on the Hankel operator, which improves robustness and performance due to the stable spectrum of the Hankel operator during training. Finally, they demonstrate that with this parametrization, memory remains practically constant within a fixed time window. They test this framework on the sCIFAR-10 dataset.", "questions": "1. If Mamba achieves SOTA performance, could you explain why there is no experimental comparison with it? If there are no technical limitations and the comparison is meaningful, including it could further enhance the quality of the paper.\n\n2. Could you please explain how Theorem 4 guarantees the numerical stability of HOPE?\n\n3. In Figure 6 (right), why does the memory decay of HOPE still appear significantly smaller than that of S4D after $t=n=64$? Shouldn't HOPE have no memory after $n$?\n\n4. The Hankel matrix looks very similar to the SSM convolution kernel. Could you please explain the differences between the two?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. I believe HOPE is very well motivated by Section 3. The analysis presented in that section clearly illustrates all the issues with current methods based on standard parametrization. In a nutshell, Figures 2 and 3 perfectly summarize the entire section.\n\n2. The three advantages of HOPE are well explained and essential. It is impressive that the authors managed to achieve all three benefits with a simple new parametrization.\n\n3. The entire framework seems very simple, yet powerful.", "weaknesses": "Some results lack sufficient motivation. For example, the setup introduced before Theorem 1 could be better explained—why is it reasonable to sample entries of $A$ from $F_a$​ and entries of $\\overline{B}\\circ\\overline{C}^\\top$ from a standard normal distribution? Similarly, the discussion preceding Algorithm 1, as well as the algorithm itself, appears more complicated than necessary, with essentially the same information repeated three times. I would prefer having only Algorithm 1 with the full expressions for variables, as in the current prelude to Algorithm 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "8VGwNBEr5W", "reviewer": "Reviewer_BdQ1", "summary": "This paper proposes a new parametrisation, named HOPE, for Linear Time Invariant (LTI) State Space Models (SSMs), based on the Hankel operator, that improves the performance and makes training more stable. The proposed parametrisation reduces the SSM parameters to 1/3 of the original and works in the frequency domain, hence the Fast Fourier Transform (FFT) and its inverse need to be used during the forward pass. Fortunately, the time and memory complexity of the forward pass remains the same as that of standard LTI SSMs using the convolutional form. The authors first show how current parameterisations can perform poorly both at initialisation or during training and how this can be explained by their corresponding Henkel operator being low-rank (Theorem 1, Figure 3) and the parameterisation being numerically unstable (Theorem 2, Figure 4). Then, they show how their parameterisation effectively mitigates both issues (Theorems 3-4, Figure 5) and does not have an exponentially decaying memory (Advantage III). Each claim Is supported both theoretically and empirically. Empirically, the authors test different parameterisation, initialisation and training schemes on the (noisy-padded) sequential CIFAR dataset, and on the Long Range Arena, also showing how HOPE outperforms previous LTI parameterisations in terms of Test Accuracy.", "questions": "1. How does the parameterisation behave in tasks where a recency bias can be beneficial? For example this is the case for generative Language Modelling.\n2. Can the authors comment on the relationship between the learned discretization parameter $\\Delta_t$ and the size of the window of non-discarded inputs of the HOPE SSM? Is the full input always considered? How does this change during training? Such discussion and potential experimental evidence could strengthen the paper.\n\nComments:\n1. Information on the actual runtime could be moved the main paper since now it is quite hard to find (it is in the last page of the appendix). \n2. The paper could benefit from having a discussion on how HOPE differs from spectral SSMs (Agarwal et al.2023) and the stable parameterisation proposed by Wang & Li (2023), which are probably the closest works This could be placed in the appendix. Such discussion could potentially address pros and cons of each approach in addition to the brief discussion in the introduction.\n\nMinor: \n- Line 159-161: Can the authors provide a definition of the function space $\\ell^2(\\mathbb{N})$   and $L^2([0,\\infty])$?\n- Line 208: imaginal axis -> imaginary axis", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Strong empirical and theoretical evidence in favour of the proposed parameterisation.\n2. Clearly written.\n3. The algorithm is novel, albeit SSM working in the frequency domain have been proposed by (Agarwal et al. 2023).", "weaknesses": "1. Some limitations are not experimentally investigated. In particular, the method seems to weigh the input time steps belonging to a fixed window equally and discard the others. This could be a limitation but all tasks considered in the experiments do not seem to benefit from a recency bias (see also the first question). \n2. Limited discussion of Related works (Minor).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "YE5ABwHAHR", "reviewer": "Reviewer_1q8g", "summary": "This paper develops a new parameterization scheme to help improve training of state space models (SSMs) in sequence modeling. The new parameterization method is based on Hankel operator theory, which resolves the low-rank and numerical instability issues of an LTI system, and the parameterized SSMs could enjoy non-decaying memory. Numerical experiments are conducted on the long range arena benchmark.", "questions": "* Why do the authors choose to show the Hankel singular values of SSMs trained after 10 epochs instead of after the whole training process (e.g. Figure 3 & 5)?\n\n* How do the authors validate the assumption on the distribution of the diagonal entry of $\\bar{A}$ in Theorem 1? For linear recurrent unit [1], $\\bar{A}$ is initialized such that $a_j$ is uniformly distributed in a disc $[r_{\\min}, r_{\\max}]$ where $r_{\\min}, r_{\\max}$ are both close to $1$.\n\n* Also for Theorem 1, the theoretical bound does not indicate $\\beta < 1$, but $\\beta \\leq 1$ instead. Is there a way to mitigate the logarithmic term in theory?\n\n\n\n\n\n[1] Orvieto, Antonio, et al. \"Resurrecting recurrent neural networks for long sequences.\" International Conference on Machine Learning. PMLR, 2023.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "* The paper is written clearly and the ideas have been presented in the proper order.\n\n* The idea using Hankel operator theory to parameterize state space models is novel, which can provide more insights for other recurrent architectures on sequence modeling.", "weaknesses": "* The connections of the Hankel rank/stability and the SSM performance seem not that positively correlated in this paper. For example, from Figure we see that the numerical rank of HOPE-SSM is even lower than init3 before and after training, but these two initializations produce similar numerical performance on the sCIFAR-10 task. Does it mean that even slightly low rank Hankel matrix can achieve good results? \n\n* From Algorithm1, the Hankel operator method looks very similar to the convolution method, it would be better if the authors could add more discussion on these two methods. For example, [1] can be a good reference. \n\n* The notations for $A$ and $\\bar{A}$ are not consistently used in this paper. From my understanding, $A$ is the hidden matrix for the continuous system and $\\bar{A}$ is the hidden matrix for the discrete system. The HiPPO-Legs initialization is for $A$ matrix, and $\\bar{A}$ contains the information of the timescale $\\Delta t$. It would be better to distinguish these two notations when making statements. For example, in Figure 4, the perturbation is added to the continuous system while the Hankel singular values are calculated  for the discrete system, and the discrete system contains the information for $\\Delta t$. It seems that $\\Delta t$ is set to be $1$ in this paper, but in practice, the timescale is scaled based on the sequence length. So what is the reason to take $\\Delta t = 1$?\nAlso, it would be better if the authors could add more details on how the perturbation is added here.\n\n[1] Li, Yuhong, et al. \"What Makes Convolutional Models Great on Long Sequence Modeling?.\" The Eleventh International Conference on Learning Representations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "B7qTJvYL9S", "reviewer": "Reviewer_TW3G", "summary": "This paper proposes an alternative parameterisation of the state space models, where the SSM layer's dynamics is replaced by parameterising rows of the Hankel matrix. It is shown that classical SSM parameterisation tends to give rise to Hankel matrices with fast decaying Hankel singular values, and is posited to correlate with poor performance for long memory tasks. The proposed parameterisation does not involve repeated multiplication of the state space matrix, hence avoiding this shortcoming. These are supported by theoretical results, and the proposed method is shown to improve upon existing SSM variants on sCIFAR and long range arena.", "questions": "1. Can the authors clarify what is the fundamental difference, if any, of the HOPE-SSM and classical convolutional models that directly parameterises a truncated impulse response function? Looking at Alg 1, the only possible departure appears to be in the for loop in steps 6-7. \n2. Can the authors clarify how (or if) the proposed model can process long sequences without increasing the filter size, while still meaningfully extract memory structures? \n3. If different, can the authors comment and demonstrate both theoretically and numerically their advantage against convolutional-type sequence models (e.g. WaveNet/temporal CNNs, and directly paramterising the impulse response function)?\n4. Is the conclusion of Theorem 1 verified by results in Fig 3 quantitatively?\n\nPost rebuttal/revision: Appreciate the comparison with discrete convolutional models to assess the model's performance. I think while the novelty is still limited (it is at most a rescaled temporal convolution model with large filters), the performance appears good and the paper is well written. I have increased my score.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "While the paper's identified limitation (i.e. favoring exponential decay in memory)  of SSM is widely known and studied, its use of the Hankel numerical rank to study it is interesting. The theoretical results are carefully derived and the practical results show good promise. Finally, the paper is carefully written and the explanations of their approach and results are excellent.", "weaknesses": "The main weakness, to my understanding, is the premise of the proposed approach. In classical LTI and SSM literature on system identification (e.g. Tangirala, A. K. *Principles of System Identification: Theory and Practice*), the very reason why SSMs were introduced in favor of convolutional models is its ability to handle infinite sequences with a finite parameterisation. The present approach appears to go in the reverse direction:\n\n1. In particular, I cannot see what is the difference between HOPE-SSM and the classical convolutional model (the most basic sequence to sequence model in LTI literature, where one directly parameterises the impulse response function), with the filter size $n$ is chosen as the same the original SSM's hidden state dimension. In fact,  the parameterisation (5) via $h$ seems to be exactly the convolution filter (impulse response), since each row of the Hankel matrix is just the impulse response (shifted by 1 for each subsequent row). If this were the case, the method has little to do with Hankel matrix, but is rather just a convolutional model based on parameterising the impulse response function.\n2. The HOPE-SSM model's size scales with sequence length if it must process long sequences. In particular, all memory functions that can be represented are finitely supported, so it is not accurate to say that this improves upon SSM parameterisation, which is used in preference to convolutional models *precisely* because it allows the parameterisation of memory of infinite support with finite number of parameters (albeit introducing curse of memory due to forcing an exponential decay, as observed in previous literature). \n3. The observed strengths of HOPE-SSM (non-exponential decay) are also present in convolutional networks (e.g. WaveNet with small filters but multiple layers, or single layer direct parameterisation of the impulse response), thus the numerical comparison should be made with those models, instead of just SSM variants.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)