How to Train your HIPPO: State Space Models with Generalized Orthogonal Basis Projections
Authors: Albert Gu
Isys Johnson
Aman Timalsina
Atri Rudra
Christopher Re
Venue: ICLR 2023 poster (2023)
Keywords: Deep learning
sequence model
state space model
S4
HiPPO

Abstract: Linear time-invariant state space models (SSM) are a classical model from engineering and statistics, that have recently been shown to be very promising in machine learning through the Structured State Space sequence model (S4). A core component of S4 involves initializing the SSM state matrix to a particular matrix called a HiPPO matrix, which was empirically important for S4's ability to handle long sequences. However, the specific matrix that S4 uses was actually derived in previous work for a particular *time-varying* dynamical system, and the use of this matrix as a *time-invariant* SSM had no known mathematical interpretation. Consequently, the theoretical mechanism by which S4 models long-range dependencies actually remains unexplained. We derive a more general and intuitive formulation of the HiPPO framework, which provides a simple mathematical interpretation of S4 as a decomposition onto exponentially-warped Legendre polynomials, explaining its ability to capture long dependencies. Our generalization introduces a theoretically rich class of SSMs that also lets us derive more intuitive S4 variants for other bases such as the Fourier basis, and explains other aspects of training S4, such as how to initialize the important timescale parameter. These insights improve S4's performance to 86% on the Long Range Arena benchmark, with 96% on the most difficult Path-X task.


HOw TO TRAIN YOUR HIPPO: STATE SPACE MODELS WITH GENERALIZED ORTHOGONAL BASIS PROJECTIONS
A Anonymous authors Paper under double-blind review
ABSTRACT
Linear time-invariant state space models (SSM) are classical model from engineering and statistics, that have recently been shown be very promis- ing in machine learning through the Structured State Space sequence model (S4). A core component of $4 involves initializing the SSM state matrix to a particular matrix called a HiPPO matrix, which was empirically important for S4's ability to handle long soquences. However, the specific matrix that S4 uses was actually derived in previous work for a particular time-corying dynamical system, and the use of this matrix as time-invariant SSM had no known mathematical interpretation. Consequently, the theoretical mechanism by which S4 models long-range dependencies actually remains unexplained. We derive a more general and intuitive formulation of the HiPPO framework, which provides a simple mathematical interpretation S4 as a decomposition onto exponentially wardedd Legendre polynomials, explaining its ability to capture long dependencies. Our generalization introduces a theoretically rich class of SSMs that also lets us derive more intuitive S4 variants for other bases such the Fourier basis, and explains other aspects of training S4, such as how to initialize the important timescale parameter. These insights improve S4's performance to 86% on the Long Range Arena benchmark, with 96% on the most difficult Path-X task.
INTRODUCTION
The Structured State Space model (S4) is a recent deep learning model based continuous- time dynamical systems that has shown promisc on a wide variety of sequence modeling tasks (Gu et al., 2022a). It is defined as particular linear time-invariant (LTT) state space model (SSM), which give it multiple properties (Gu et al., 2021): as an SSM, $4 can be simulated as discrete-time recurrence for elliciency in online LTI model, S4 can be converted into convolution for parallelizability and computational elficiency at training time. These properties give S4 remarkable computational elficiency and performance, especially when modeling continuous signal data and long sequences.
autoregressive sellings, and as
Despite its potential, several aspects of the S4 model remain poorly understood. Most notably, Gu et al. (2022a) claim that the long range abilities of S4 arise from instantiating it with par- ticular "HiPPO matrix" (Gu et al., 2020). However, this matrix was actually derived in prior work for different (time-varying) setting, and the use of this matrix in S4 (a time-invarion SSM) did not have a mathematical interpretation. Consoquently, the mochanism by which S4 truly models long-range dependencies is actually not known. Beyond this initialization, sev- eral other aspects of parameterizing and training S4 remain poorly understood. For example, S4 involves an important timescale parameter A, and suggests a method for parameterizing and initializing this parameter, but does not discuss its meaning or provide justification.
This work aims to provide a comprehensive theoretical exposition of several aspects of S4. The major contribution of this work is a cleaner, more intuitive, and much more general formulation of the HiPPO framework. This result directly generalizes all previous known results in this line of work (Voelker et al., 2019; Gu el al., 2020; 2021; 2022a). As immediate consequences of this framework:

---

We prove theoretical interpretation of S4's state matrix A, explaining S4's ability to capture long-range dependencies via decomposing the input with respect to an infinitely long, exponentially-decayinng measure.
We derive new HiPPO matrices and corresponding S4 variants that generalize other nice basis functions. For example, our new method S4-Fou'T produces truncated Fourier basis functions. This method thus automatically captures sliding Fourier transforms (c.g. the STFT and spectrograms), which are ubiquitous as a hand-crafted signal processing tool, and can also represent any local convolution, thus generalizing conventional CNNs.
We provide an intuitive explanation of the timescale A, which has a precise interpretation as controlling the length of dependencies that the model captures. Our framework makes it transparent how to initialize A for a given task, as well as how to initialize the other parameters (in particular, the last SSM parameter C) to make a deep SSM variance-preserving and stable.
Emppricallly, we validate our theory on synthetic function reconstruction and memorization tasks, showing that empirical performance of state space models in several settings is predicted by the theory. For example, our new S4-FouT method, which can provably encode spike function as its convolution kernel, performs best on a continuous memorization task compared to other SSMs and other models, when A is initialized correctly. Finally, we show that the original S4 method is still best on very long range dependencies, achieving a new state of the art of 86% average on Long Range Arena, with 96% on the most difficult Path-X task that even the other SSM variants struggle with.
FRAMEWORK
We present our improved framework for state space models and online reconstruction of signals. Section 2.1 discusses background SSMs, including their connection to convolutions for time- invariant systems. Section 2.2 defines new subclasses of SSMs with special properties that can be used for online function reconstruction, simplifying and generalizing the original HiPPO framework. An extended background and related work section can be found in Appendix A.
2.1 STATE SPACE MODELS: A CONTINUOUS TIME LATENT STATE MODEL
The stale space model (SSM) is defined by the differential equation (1) and (2). Given an input sequence of length N, it maps a 1-D input signal u(l) to an N-D latent state a(l) before projecting to a 1-D output signal v().
x'(t) = (t)) y(t = ((t)
(1)
K(t)=Cee* A y(t) = (K)))
(3)
(2)
We will generally assume D-OER and omit it for simplicity, unless explicitly mentioned.
SSMs can in general have dynamics that change over time, i.e. the matrix AER NNN, and vectors B e xx1 C E RIxN are a function of t in (1) and (2). However, when they are constant the system is linear time invariant (LTI), and is equivalent to a convolutional system (3). The function K(I) is called the impulse response which can also be defined as the output of the system when the input u(I)= ((t) is the impulse or Dirac delta function. We will call these time-invariant state space models (TSSM). These are particularly important because the equivalence to a convolution makes TSSMs parallelizable and very fast to compute, which is critical for S4's efficiency.
Our treatment of SSMs will consider the (A,B) parameters separately from C. We will refer to an SSM as either the tuple (A,BCC) (referring to (3)) or (A,B) (referring to Definition 1) when the context is unambiguous. We also drop the T in TSSM when the context is clearly time-invariant.
Definition 1. Given a TSSM (A, A is a vector of N functions which we call the SSM basis. The individual basis functions are denoted K,( = elA,AAB, which satisfy z, (t) = (w)))) Kn (t-s))(uss)ds Here e,, is the one-hot basis vector.
This definition is motivated by noting that the SSM convolutional kernel is a lincar com- bination of the SSM basis controlled by the vector of coefficients C, K(I)= - Cn K,))).
2

---

We note that Definition 1 has not appeared in prior works deep SSMs, but is new perspective laken by this work for underslanding and visualizing these models.
Discrete SSM with Timescales. To be applied on discrete input sequence (uo.u1....) instead of contimuous function w(t), (1) must be discretized by a step size A that represents the resolution of the input. A poorly understood question from prior work is how to interpret and choose this A parameter, especially when the input 24 does not actually arise from uniformly sampling initialize in the range (mmin:Aarr) = (0.001,0.3) ), but does not provide a concrete justification. In Section 3.3 we show a simpler interpretation of A directly in terms of the length of dependencics in a discrete input sequence.
underlying continuous signal. S4 specifies to log-uniformly
2.2 HIPPО: HIGH-ORDER POLYNOMIAL PROJECTION OPERATORS
$4 is defined as a TSSM where (A, is initialized with a particular formula (4). This was called the HiPPO matrix in (Gu et al., 2022a), but is actually just one of several such special matrices dcrived in (Gu al., 2020). To disambiguate other variants of S4, we refer to the full S4 method using this HiPPO SSM as S4-LegS. Other cases considered in this work include LegT from prior work (5) and FouT that we introduce this work (6).
(HiPPO-FouT)
(HiPPO-LegS)
==k=0 0 n=0,k odd k= 0,n odd
> k
Ans = - (22+1)
N+1
n=
(4)
222
2n+1
2/2
0
n k
A.k
-4
n.kk odd
B, B2n(2n+1)]
2
n k- 1,k odd
(6)
(HiPPO-LegT)
22nn
n-n= 1,n odd
0
otherwise
{1
kSn
A.s (2n
(-11)=+
k
(5)
2
n=0
B.
2v2
odd
B, (2n+11
0
otherwise
These matrices were originally motivated by the question of "online memorization" of imput signal. In the following, we present an improved version of the HiPPO framework that addresses this problem.
The key idea is that for suitably chosen SSM basis A,B, B, any time t, the current state æ(t) can be used to approximately reconstruct the entire input u up to time t. In Appendix A. describe the full HiPPO framework as described in (Gu et al., 2020). In particular, suppose that the basis functions satisfy Definition 2.
We call an SSM ((()),((t)) an orthogonal SSM (OSSM) for the basis (t,t,)) and measure w(t,s) 20 if the functions
Definition 2.
(t,,s) satisfy, at all times t,
(mn(1)= (Is)))((s))
Pr (1,s) (1.smmm(()))wWss) &m
(7)
In the case of a innarian OSSM (TOSSM), K, (t,s) (t- s) (depends only on s), giving us Definition with measure w(t s) :t.(t) and basis pn (t 8) := (t.s).
t t-s),
To be more specifie about terminology, Pa and wn are called the basis and measure for orlhog- onal SSMs (Definition 2), while K,, called the SSM basis kernels which applies more gener- ally to all SSMs (Definition 1). The distinction will be made clear from context, notation, and the word "kernel" referring to Kn- Note that for OSSMs, (Pn, and Kn are uniquely deter- mined by each other (Proposition in Appendix C.2), so we can refer to an OSSM by either.
(1) (s) = (1.8) and similarly (x) = (1,8) for every fixed I, the bases ph are Defining pu
orthonormal in the Hilbert space with inner product (p-4)= (on))f(((sqq (s)(()((s))(( By equation (7), we have z,, (t) f K,, ( (u.ph"))ac > Thus all times t, the state vector a(t) is simply the projections ofulse onto a orthonormal basis, so that u can be reconstructed from z(t). In the HiPPO framework, this reconstruction is called the online function approximation problem (Gu et al., 2020).
3

---

Proposition 1. Consider OSSM that satisfies (7) and suppose that in the limit N D0, for fized timet, the pa are complete on the support ofw. Then
(t)p(n((t,, for all S
HiPPO thus be viewed as framework for deriving specific SSMs that do satisfy (7). The original HiPPO methods and its gencralizations (Gu et al., 2020; 2021) primarily focused on the case when the Pn are orthogonal polynomials, and specifically looked for solutions to (7), which turn out to be SSMs. We have rephrased the HiPPO definition in Definition to start directly from SSMs and hence is more general. (See Appendix A.1 for overview of the original HiPPO setup.) We discuss the two most important cases previously introduced.
HiPPO-LegT. (5) is a TOSSM that approximates the Legendre polynomials.
Definition 3. Let I((I) be the indicator function for the wnil intereal [0,1]. Let (1) be the Legendre polynomials rescaled to be orthonormal on [0,1], i.e,, L m (c) Im (I)I(I)dl Ón,m-
Proposition 2. As N -0, the SSM (5) is TOSSM with w(()=I(()) Pn (1) Ln)=
This particular system was the precursor to HiPPO and has also been variously called the Legendre Delay Network (LDN) or Legendre Memory Unit (LMU) (Voelker, 2019; Voelker et al., 2019). The original motivation of this system was not through the online fuuction approximation formulation of HiPPO, but through finding optimal SSM approximation to the delay network that has impulse response x(t)=o(t-1) representing a time-lagged output by time unit. This is visualized in Appendix C.4.4 Fig. 7. We state and provide an alternate proof of this result in Appendix C.4.4, Theorem 10.
HiPPO-LegS. Unlike the HiPPO-LegT case, which is an LTT system (1) (i.e. TOSSM), the HiPPO-LegS matrix (4) was meant to be used in a time-varying system x A Bu(() (Gu et al., 2020). In contrast to HiPPO-LegT, which reconstructs onto the truncated Leg- endre polynomials in sliding windows [t it-1,th -,t]], HiPPO-LegS reconstructs onto Legendre polynomials "scaled" windows [0.t]; since the window changes across time, the system is not iime-invariant. Specifically, we have:
Theorem 3. The SSM
(,A. B) for (A.B) in (4) an OSSM with w(t.s) - (s/tt)
Ln,tt))=L((s/t)
However, the S4 model applies the exact same formula (4) inside the fime-inwariant SSM (1), ie. dropped the 1 term, which had no mathematical interpretation (see Appendix A.1 for more details). In other words, while ; an OSSM, it was not known whether the TSSM (A.B) is a TOSSM. Given that the performance of SSM models very sensitive to these matrices A (Gu et al., 2022a; Gupta, 2022), it remained a mystery why this works. In Section we will prove that (4) actually does correspond to a TOSSM.
Naming convention. We use HiPPO-[SSM] online function approximation, where [SSM] is a suffix (e.g. LegS, LegTT) that abbreviates the corresponding basis functions (e.g. scaled Legendre, truncated Legendre). S4-[SSM] refers to the corresponding trainable layer (A,B.C) with randomly initialized C, trained with S4's representation and computational algorithm (Gu al., 2022a).
refer to fixed OSSM (A.B) suitable for
Other SSMs. Several variants of S4 have been introduced, including several simpler di- agonal SSMs (DSS (Gupta, 2022), S4D (Gu et al., 2022b), S5 (Smith et al., 2022)). Notably, these methods are all based on approximations of HiPPO-LeyS, and our new theory explains why they perform well (Gu et al., 2022b). However, they are not OSSMs, and in Section 4 we show several settings where the full $4 variants based on OSSMs outperform these variants.
3 GENERALIZED HiPPO: GENERAL ORTHOGONAL BASIS PROJECTIONS
In Section 3.1, we prove that the LTI HiPPO-LegS is actually a TOSSM and show closed formulas for its basis functions. In Section 3.2, we include more specific results on finite- window SSMs, including introducing a new method HiPPO-FouT based on truncated Fourier functions, and proving previously established conjectures. Section 3.3 shows more general properties of TOSSMs, which establish guidelines for interpreting and initializing SSM parameters such as the timescale A.
4

---

Figure 1: (Teft:: LegS) We prove that the particular A matrix chosen in S4 produces Legendre polynomials under an exponential re-scaling, resulting in smooth basis functions with closed form formula. (Middlee Right: FouT) We derive new SSM that produces approximations to the truncated Fourier basis, perhaps the most intuitive and ubiquitous set of basis functions. This method generalizes sliding Fourier Transforms and local convolutions (i.e. CNNs), and can also encode spike functions to solve classic memorization tasks.
Our main, fully general. result is Theorem in Appendix C.2, which describes a very gen- eral way derive OSSMs for various SSM basis functions K₂ (t.s). This result can be instantiated in many ways to generalize all previous results in this line of work.
3.1 EXPLANATION OF S4-LEGS
We showcase the generality of Theorem 8 by stating the following special case containing sub-class of time varying OSSMs (which are themselves rich enough to explain both S4-LegS and HiPPO-LegS):
Corollary 3.1. Define (xx())))))((())-))00)))))))))))) for any differentiable function The SSM Add (I) is an OSSM with w(1,s) = I( (I,s))aa (+))o(()
Pr =las==Tml Ln (m,,))==((((((.s))
We show the matrices B) in (4) are deeply related to the Legendre polynomials L, defined in Definition 3. In particular, as more specific corollaries of Corollary 3.1, we recover both the original time-varying interpretation of the matrix in (4), as well as the instantiation of LegS time-invariant system. If we set a' = t, then recover the scale-invariin invariant HiPPO-LegS OSSM in Theorem 3:
Corollary 3.2 (Scale-Invariant HiPPO-LegS, Theorem 3). The SSM B) is TOSSM for basis functions K,, ( and - where A and are defined as in (4).
And if we set a' a'(t)=1, this shows new result for the time-invariant HiPPO-LegS TOSSM: Corollary 3.3 (Time-Invariant HiPPO-LegS). The SSM (A,B) is a TOSSM with
w(t)= =
(t.=
This explains why removing the factor from HiPPO-LegS still works: it is orthogonalizing onto the Legendre polynomials with an exponential "warping" or change basis on the time axis (Fig. I.(eett)).
3.2 FINITE WINDOW IOME-INVARIAN ÖRTHOGGNNAL SSMs
For the remainder this section, we restrict to the time-invariant SSM setting (3). sec- ond important instantiation of Thcorem 8 covers basis functions (t), which requires infiiie-dimensionn important type of discontinuity occurs when ((( is supported finite window, so that these TSSMs represent sliding window transforms.
with discontinuity in the SSM
SSMs to represent. The most
3.2.1 S4-FouT
Using the more general framework (Thcorem 8) that does not necessarily require polynomials as basis functions, we derive a TOSSM that projects onto truncated Fourier functions.
Theorem 4. As N + oo, the SSM for (6) is a TOSSM with w(t) = I(tt, and {pa )n21 are the truncated Fourier basis functions orthonormal on [0,1], ordered in the form {pm Jn (1))) where 8m (1) = (esin(2nmmm and c. (1) =0)=0u (2cos(2mmm) for m=.....,NN/2
5

---

This SSM corresponds to Fourier series decompositions, ubiquitous tool in signal process- ing, but represented as a state space model. The basis is visualized in Fig. (middde) for state size 1024
A benefit of using these well-behaved basis functions is that we can leverage classic results from Fourier analysis. For example, it is clear that taking linear combinations of the trun- cated Fourier basis represent any function [0.1], and thus S4-FouT can represent any local convolution (i.e. the layers of modern CNNs) (ef. Theorem Appendix C.4).
3.2.2 APPROXIMATING DELAY NETWORKS
An interesting property of these finite window TSSMs is that they can approximate delay functions. This is defined as system with impulse response ((t)=d(t-1)) Any HiPPO method involving finite windows should have this capability, in particular, the finite window methods LegT and FouT:
Theorem 5. For the FouT system A and B (6), let C be (twice) the vector of evaluations
of the basis functions Cn = =2pP.(11 and let D= 1. For the LegT T system A and B (5), let C be the vector of evaluations of the basis functions C, = Pm (.-=Pa(1) =1 (1)= 21 (-1)" and let D 0.
Then the SSM kernel C(t)=CelAB+DD
limits to ((1) 5( as N 00.
Theorem 5 is visualized in Fig. for FouT, and Fig. 7 in Appendix C.4. Further, the result for LegT can be characterized even more tightly for finite N (cf. Theorem 10 in Appendix C.4). The above result provides theoretical justification for why S4-FouTT excels at dense memorization tasks (see Section 4).
3.3 PROPERTIES OF TIME-INVARIANT ORTHOGONAL SSMs
We describe several general properties of TOSSMs, which let us answer the following ques- tions: What does A intuitively represent, and how should be set an SSM model? So far, this had been done in ad-hoc way. It turns out that for TOSSMs, these two questions are closely related and have intuitive interpretations. See Appendix C.5 for more details on other properties of TOSSMs related to their closure and normalization.
Timescales. As discussed in Section 2, converting from continuous to discrete time involves a parameter that represents the step size of the discretization. This is an unintuitive quantity when working directly with discrete data, especially if it is not sampled from underlying continuous process.
We observe the following fact:
for all standard discretization methods (e.g. Euler, backward Euler, generalized bilinear transform, zero-order hold (Gu et al., 2021)), the discretized sys- tem depends on (A,B), and A only through their products (AA,AB). This implies that the SSM (A.B) discretized at step size A is computationally equivalent to the SSM (AA,BB) discretized at step size
Therefore, can be viewed just as a scalar scaling of the base SSM instead of changing the rate of the input. In the context of TOSSMs, this just stretches the underlying basis and mcasure (Scalar Scaling).
The most intuitive example of this is for a finite window TOSSM such as LogT or FouT. Dis- cretizing this system with step size A is equivalent to considering the system (AA,AB) with step size 1, which produces basis functions supported exactly on [0, 1- The interpretation of the timescale A lends to simple discrete-time corollaries of the previous continuous-time re- sults. For example, LegT and FouT represent sliding windows of / elements in discrete time.
Corollary 3.4. By Theorem 5, N - o0, the discrete convolutional kernel K e[A-1]; i.e. the discrete delay network with lag 3
Corollary 3.5. For HiPPO-Fou' T matrices (A,B), by Theorem 4, as N - the discrele con- volutional kernel K (over the choice of C) can represent any local convolution of length |A |A-I
This discussion motivates the following definition. Properly normalized TOSSMs (A,B) will model dependencies of expected length 1, and A modulates it to model dependencies of length 1. allowing fine-grained control of the context size of a TOSSM.

---

Table 1: (Long Range Arena) Accuracy (std.) full suite of LRA tasks. Hyperparameters in Appendix B. denotes failure to learn better than random gnessing, following convention from Tay al. (2021); Gu al. (2022a).
MODEL
LiSTOPS
TEXT
RETRIEVAL
IMACE
PATHPINDER
PATH--
AVG
S4-LegS
59.60 (0.07)
86.82 (0.13)
90.90 (0.15)
88.65 (0.23)
94.20 (0.25)
96.35 (-)
86.09
S4-FouTT
57.88 (1.90)
86.34 (0.31)
89.66 (0.88)
89.07 (0.19)
94.46 (0.24)
X
77.90
S4-T.eSSFouT
60.45 (0.75)
86.78 (0.26)
90.30 (0.28)
89.00 (0.26)
94.44 (0.08)
X
78.50
S4 (original)
58.35
76.02
87.09
87.26
86.05
88.10
80.48
Transformer 36.37
64.27
57.46
42.44
71.40
X
53.66
Definition 4 (Timescale of TOSSM). Define Elu] ["w(())
Jo w())t to be the timescale of
TOSSM having measure w(I). A TOSSM is timescale normalized if il has limescale 1.
By this definition, HiPPO-LegS timescale normalized. This motivates S4's initialization of A log-umiformie in (0.001.0.1) covering geometric range of sensible timescales (expected length 10 to 1000). In Section we show that the timescale can be chosen more precisely when lengths of dependencies are known.
EXPERIMENTS
We study the empirical tradeoffs of our proposed S4 variants. We compare several S4 vari- ants based on the TOSSMs introduced in this work, as well as to simpler diagonal SSMs called S4D that not orthogonal SSMs (Gu et al., 2022b). Corresponding to our main contributions, we hypothesize that
S4-LegS excels at sparse memorization tasks because it represents very smooth convo- lution kernels that memorize the input against an infinitely-long measure (Corollary 3.3, Fig. 1). Conversely, it is less appropriate at short-range lasks with dense information because smooths out the signal.
S4-FouT excels at dense memorization tasks because it can represent spike functions that pick out past elements at particular ranges (Section 3.2.2). However, it is less appropriate at very long range tasks because represents finite (local) window.
A can be initialized precisely based known time dependencies in given task.
4.1 LONG RANGE ARENA
The Long Range Arena (LRA) benchmark is suite of sequence classification tasks designed to stress test sequence models on modeling long sequences. We improve $4's previous state of the art by another 6 points (Table 1). Validating our hypothesis, S4-LegS is extremely strong at the hardest long-range task (Path-X) involving sparse dependencies of length 16384, which FouT cannot solve because is a finite window method.
Compared to the original S4 model, the S4-LegS method in Table is the same model but differs by improving some sensible hyperparameters; the main differences are (i) using bidirectional instead of autoregressive model, since the tasks do not require causality (ii) adopting more standard cosine learning rate scheduler rather than decaying validation platcau, and (iii) increasing weight decay regularization.
On top of these general changes, the primary source of improvements on Path-X performance arises from applying the theory of timescales in Section 3.3. Fig. 2 illustrates the importance of setting A correctly. Instead of the standard initialization of (Amin, = 00.001,0.1), these results were obtained by lowering the initialization of A by factor of 10 in accordance with known length of dependencies in the Path-X task.
4.2 THEORY: FUNCTION RECONSTRUCTION TIMESCALES, NORMALIZATION
Fig. 3 confirms the HiPPO theory of ouline function reconstruction (Proposition 1) for the proposed TOSSMs LegS and FouT. A followup question is whether the theory is necessary to develop methods that have this functionality, whether other SSMs still learn this

---

Pathi Amin 10
PathX Ant -00
0.9
Val Accuracy
0.8
Val Accuracy
0.8
0.7
0.7
54-Leg5 4ew
54-Leg5
Aew 10
54-LegS
Aewu 10
54-Leg5
Ausa 10-3
54-Leg5 Aew 10-2
54-leg5
Avor 10-4
S4D-inv Dewr 10-2
0.5
0.5
20
30
Epoch
Epoch
Figure 2: (Validation curves on Path-X.) (Left) Setting Amin too small can solve task, but inconsistent. ( (Right) A good setting Amin can consistently solve task. Note that the timescale of each feature is up to I = 10", which is on the order of (but not exceeding) the length of the task L= 16384. Empirically, performance is best when spreading out the range of with a larger Amaz that covers wider range of timescales and can potentially learn features at different resolutions, which are combined by multi-layer deep neural network. We also show diagonal variant of S4-LegS called S4D-Inv introduced in (Gu et al., 2022b) which approximates S4-Legs, but is still worse
/ Ma My wwwpw//wwwwwwttoyooooooooooowwe
Engrutt
Inggus Nescrrotracc
2000
10000 2000
5000 10000
Figure 3: (New HiPPO methods) Function reconstruction predicted by our general theory. An input signal of length 10000 is processed sequentially, maintaining a state vector of size only a(t) e IR which is then used to approximately reconstruct the entire history of the input. (Left) HiPPO-LegS (as an LTI system) orthogonalizes on the Legendre polynomials warped by exponential change of basis, smoothening them out. This basis orthogonal with respect to an exponentially decaying measure. Matching the intuition, the reconstruction is very accurate for the recent past and degrades further out, but still maintains information about the full history of the input, endowing it with long-rang modeling capacity. This is the same as S4. (Right) HiPPO-FouT orthogonalizes on the truncated Fourier basis, similar to the original HiPPO-LegT LMU.
task when trained. Appendix B.1, Fig. analyzes synthetic Reconstruction Task against uniform measure, which validates that S4-LegT and S4-Fou'T are far better than other SSM variants, particularly when A is initialized properly based on the length of the task.
4.3 MEMORIZATION: THE DELAY (CONTINUOUS COPYING) TASK
Next, we study how the synthetic reconstruction ability transfers to other tasks. The Delay Task requires models to learn a eoquenco-to-scquenee map whose output the input lagged by fixed time period (Fig. 4a). For recurrent models, this task can be interpreted as requir- ing models to maintain a memory buffer that continually remembers the latest clements it sees. This capability was the original motivation for the Legendre Memory Unit, the predeces- sor to HiPPO-LegT, which was explicitly designed spike kernel (Fig. 7). In Fig. 4b, we see that our new S4-FouT actually out perforrmss S4-LegT, which both outperform all other methods when the timescale A set correctly. We note that this task with a lag of just 1000 time steps is too hard for baselines such as an LSTM and Transformer, which empirically did not learn better than random guessing (RMSE 0.43).
solve this task because can encode
8

---

Dalay (Continuous Copying)
Output yiti
0
Inout utt)
1000
2000
3000
4000
(a) (Delay Task) Models perform mapping from I 4000 where the target output is lagged by 1000 steps, with error measured by RMSE. The input white noise signal bandlimited to 1000/Tz.
We use single layer SSMs with state size N 1024.
min, max)
(A,
(A
40-44)5044 5)
0.2891
0.2832
(A min, A max) (1e-3, 1e-1)
(A min, A max)
(2e-3,2e33
(1e-31e-3)
0.1471
0.1414
Trainable B)
B)
(A,
(2e-3.2e-3)
0.0584
0.0078
54-LegS
0.3072
0.0379
0.2969
0.0130
(4e-3, 4e-3)
0.4227
0,1262
54-LegT
0.2599
0.1204
0.0225
0.0129
(Be:3. Be-3)
0.4550
0,2928
54-FouT
0.2151
0.1474
0.0804
0.0078
(5e-4, 1e-1)
0,2048
0:1537
54-LegS+FouT
0814
0.0309
0.0080
(1e:3.1e11
0,2017
0.1474
54D-LegS
1378
0.0337
0.0466
0.0140
(e13)
0.3234
0,2262
S4D-Inv
0.1489
0.0248
0.0605
0.0188
1e-13.1e-1)
0,4313
0.5417
S4D-Lin
0.1876
0.1653
0.0421
0.0144
(ee1))
0:4330
0.4026
(b) (RMSE) (Left) Setting A appropriately makes a large difference. For Fou' (A,B), which encode finite window basis functions (Fig. 1), the model setting A too large means the model cannot 1000 steps the past, and performs Performance best at the theoretcaally optimal value of 2- which can encode a spike kernel at distance exactly 1000 steps (Corollary 3.4). (Right) When A is set optimally, the proposed S4- Fou'T method is the best SSM as the theory predicts. When A is not set optimally, other methods perform better, including the simple diagonal methods proposed in (Gu et al., 2022b).
history of length up to A. For example, chance.
Figure 4: (Delay Task.) synthetic memorization task: definition (Fig. 4a) and results (Fig, 4b).
DISCUSSION
This work improves the HiPPO framework, generalizing it to any set of orthonormal basis functions as projection operators. This led better understanding of existing models (clarification the mechanisms underlying the original S4 model) as well as new variants (SSMs producing Fourier basis functions). In addition, principled explanations of other components such as the timescale and initialization, leading to improved empirical results.
new framework to give
The theoretical insights provided by this work have been used to improve and extend SSMs in several directions. We showed that S4 produces exponentially-ddeaaye to precise formulas (Corollary C.6), and Li et al. (2022) designed alternative exponentially- decaying CNN kernels inspired by this property. Another line work on diagonal approx- imations to S4 all use insights from our theory to simplify and improve $4. DSS (Gupta, 2022) introduced a particular diagonal approximation which was empirically effective, and S4D (Gu et al., 2022b) proved that it produced the same kernels asymptotically as S4 (Corollary C.6). S5 (Smith al., 2022) extended this to multi-input multi-output (MIMO) SSMs and showed that our rocommendations for initialization of C and A are important even in the MIMO setting. We believe that the insights in this work will be useful both to understand the original S4 model, and produce better and simpler state space models.
kernels according

---

REFERENCES
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arv preprint 1607.066500 50, 2016.
T. S. Chihara. An introduction to orthogonal polynomials. Dover Books on Mathematics. Dover Publications, 2011. ISBN 9780486479293.
Jared Quiney Davis, Albert Gu, Tri Dao, Krzysztof Choromanski, Christopher Ré, Percy Liang, and Chellcaa Finn. Catformer: Designing stable transformers via sensitivity anal- ysis. In The International Conference on Machine Learning (ICML), 2021.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep leedforward neural networks. In Proceedings of the thirteenth international conference on artificial intel- ligence and statistics, pages 249-256. JMLR Workshop and Conference Proceedings, 2010.
Albert Gu, Tri Dao, Stefano Ermon, Atri Rudra, and Christopher Ré. Hippo: Recurrent memory with optimal polynomial projections. In Aduonces in Neural Information Pro- cessing Systems (NeurIPS), 2020.
Albert Gu, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher Ré. Combining recurrent, convolutional, and continuous-time models with the structured learnable linear state space layer. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
Albert Gu, Karan Goel, and Christopher Ré. Efficiently modcling long sequences with structured state spaces. In The International Conference on Learning Representations (ICLR), 2022a.
Albert Gu, Ankit Gupta, Karan Goel, and Christopher Ré, On the parameterization and initialization of diagonal state space models. In Advances in Newral Information Processing Systems (NeurIPS), 2022b.
Ankit Gupta. Diagonal state spaces are as effective as structured state spaces. In Advances in Neural Information Processing Systems (NewrIPS), 2022.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, 2015.
Sepp Hochreiter. Untersuchungen zu dynamischen neuronalen netzen. Diploma, Technische Universität München, (1),,, 1991.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network train- ing by reducing internal covariate shift. In International conference on mochine learning. pages 448-456. PMLR, 2015.
Yuhong Li, Tianle Cai, Yi Zhang, Deming Chen, and Debadeepta Dey. What makes convo- lutional models great on long sequence modeling? arXiv preprint ar Xr1::221000000 09299,, 2022.
Jimmy TH Smith, Andrew Warrington, and Scott W Linderman. Simplified state space layers for sequence modeling. arXiv preprint Xix:2220 220.000000 2022.
Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benchmark for efficient transformers. In International Conference on Learning Representations, 2021. URL
grCkk.
Aaron Voelker, Ivana Kajić, and Chris Eliasmith. Legendre memory units: Continnous-tin representation in recureet neural networks. In Advances in Neural Information Processing Systems, pages 15544 15541-15553, 2019.
Aaron Russell Voelker. Dynamical systems in spiking neuromorphic hardware. PhD thesis, University of Waterloo, 2019.
10

---

n Moy / Vallie bork hwwp
VISUU IIPPO Recondtruction
Inguut
PPO Reconnttrut
Measure
10000
Figure 5: (Prior HiPPO methods) Given an imput function u(I) (black), HiPPO compresses it online into state vector xff) ETR M via equation (1). Specific cases of HiPPO matrices A.B are derived so that at every time I, the history of up to time can reconstructed linearly from r1) (red), according to measure (green). (Teft) The HiPPO-LegT method orthogonalizes onto the Legendre polynomials against a Lime-invariant uniform measure, Le. sliding windows. (Highh) The original HiPPO-LegS
method is not Linee-nvariant system. When used a Lime-varying ODE x A Bu, sr(1) represents the projection the entire history of onto the Legendre polynomials. It was previously unknown how to interpret the time-invariant version of this ODE using the same (A.B) matrices.
A RELATED WORK
We discuss in more detail the differences between this work and the previous results in this line of work.
A.1 HIPPO OSSMs WITH ORTHOGONAL POLYNOMIAL KERNELS
HiPPO is an online function reconstruction framework theoretically motivated and described in (Gu et al., 2020) and expanded on in (Gu et al., 2021). By projecting sequence data. onto polynomial bases, a function's 's history can be represented in a latent space.
Every measure (with some mild restrictions) in the finite' interval [-1,1] induces
unique sequences of orthogonal polynomials (OPs) po(z).Pi.... satisfying deg(p.) = and
(prPP)) =
dy for all i.j,
(8)
where 11
if i-j and 0 otherwise.
This sequence forms an OP family. For a function u, HiPPO gives a compressed represen- tation the history of u in the interval ((),() in the N coefficients given by (0>
/ (tstttt...
xr (t) =t=(t)//
(-8())
where Pn (t,s) and p(t,s) are transformations of the OP family onto the interval [0.t]. Specif- ically, one can choose pr (t,s) = Pm (((--t +1) and pu(t,s) u 2(s
0(1) +1). Note that Eq. (9)
0(2)
and Eq. (8) correspond exactly to Eq. (7).
When A(t) = 0 for a fixed 0, this corresponds to the 'truncated' window from (Gu et al., 2020) while the case of ((t)=t considers the entire [0.t] is the 'scaled' window case from (Gu ct al., 2020). This is illustrated in Fig. 5.
(Gu et al., 2020) only considered the above for the case of μ(x:) = for which the corresponding OP family is the Legendre polynomials. For ((t)=0 and ((t) =t we get the LegT and LogS respectively in (Gu et al., 2020).
From the viewpoint of Definition 2, it is easy to see that choosing an OP family pi(x) and its measure μ defines an OSSM (())..(()). However, both (Gu et al., 2020) and (Gu et al.,
The results on orthogonal polynomials also work for the infinite interval (0,00 via the Laguerre polynomials but we ignore this case for simplicity but point out that (Gu et al., 2020) handles this case.
"In this work presented everything for the finite interval [0.1] but since [-1,1] is more standard in the orthogonal polynomials and what used in (Gu et al., 2020) stick with [-1,1] in this section. It is easy move from to another by an appropriate linear scaling of the argument.
11

---

2021) start from Eq. (9) and show that by differentiating Eq. (9) wrt one can derive the corresponding SSM:
z' A(t)=
Specifically, for the case of p(z)=1 =1 (i.e. Legendre) the above simplifies to:
1. For 0(t)=0 (i.e. LegT) one gets
x' =(()= Ar(t)+ Bu(t),
(10)
where A and B are as in Eq. (5).
2. For =(t)=t (i.c. LegS) one gets
d' (1) =1)= Ar(1)+ 1 -.u(()),
(11)
where and B are as Eq. (4).
A.2 THE MYSTERY OF S4
The S4 paper (Gu et al., 2022b), used weird 'mixture' of LegS and LegT. Specifically, in its experiments, used the ODE in Eq. (10) but instead of using A and B are as Eq. (5) it used A and B as in Eq. (4). However, LegS A and B from Eq. (4) had been derived for 0(1)= instead of ((1)= =0. In other words, there was NO mathematical justification for the ODE used in S4. One of our main results is to provide a solid mathematical justification for the ODE used S4 (see Section 3.1).
A.3 WHY OP KERNELS?
A crucial insight of the HiPPO framework is that the coefficients x(t) is sufficient to recover u. This enables online predictions for end-to-end models. The intuition for this is basically that OPs form a complete basis for functions over [-1.1]. Specifically, given -m-smooth function u: u:1-1,1]
which is seen online, we wish to maintain compressed representation of its history u(s)ge = =u(s) at every time t.
For any infinite dimensional polynomial basis po.Pi get the polynomial expansion of
n1()= Σ vn (()()))))))) n=
The truncated approximation u(t) at time t= N is:
N-1 a(t) Σ (t). n=D
(12)
pt is an OP family, then our approximation ū(t) is guaranteed to be optimal. That is, as N - 0o, û(t) becomes perfect reconstruction of u (i.e. the error with respect to the mcasure μ goes to 0 as N->o0 oo). Furthor, given the mcasure μιœ)) it is known that the OP family corresponding to μ gives the best possible approximation among all degree N polynomial approximations.
The main insight of HiPPO (Gu et al., 2020) to extend the framework above from the interval [-1,1] to [0,t] such that the approximation of Eq. (12) can be updated efficiently as t increases.
In Appendix C.2, we expand the HiPPO framework any set of differentiable orthogonal functions with respect to a given measure, and generalize the concepts behind LegS using the time-warping function We use this to derive general form for time-varying OSSMs, and give a mathematical interpretation of the LegS's state matrix.
A.4 HIPPO vs LSSL.
As discussed above, HiPPO be thought of framework for deriving state space mod- els corresponding to specific polynomial bases. The original paper (Gu et al., 2020) did not explicitly draw the connection to state space models, and also developed systems only
12

---

for few particular cases which were called LegS (a time-varying system involving Legendre polynomials), LegT (a time-invariant system with the truncaled Legendre polynomials), and LagT (involving Laguerre polynomials).
A fullow-up paper Linear State Space Layers (LSSL) (Gu et al., 2021) generalized these results to all orthogonal polynomial families, and also generalized the flexibility of the time- varying component. They produced SSMs [tt]=(((txt)+ a(t) can be viewed as the projection of the history of u(s) last onto orthogonal polynomials Pn rescaled onto the interval [t (E-O((),),, where ((t) is an arbitrary factor. (Indeed this is the form we outlined above.) This generalized all 3 cases of the original HiPPO paper.
where at all times t,
A.5 LEGENDRE MEMORY UNIT (LEGENDRE DELAY NETWORK)
The HiPPO-LegT matrix (5) was first introduced the LMU (Voelker, 2019; Voelker et al., 2019). The original motivation was to produce a state space model that approximates the Delay Network, which can be defined as the LTI system that transforms u(t) into u(t-1), i.c lags the input by time unit. This can also be defined as the system with impulse response ((t)= 1), Le. it convolves by the convolutional kernel with 8 spike at time 1.
The connection between the Delay Network and Legendre polynomials was made in two steps. First, the transfer function of the ideal system is (0((t-1)) (s) =e and must be approximated by proper rational function to be represented an SSM. Taking Padé approximants of this function yields "optimal" approximations by rational functions, which can then be distilled into SSM (A,B,C) whose transfer function C(sI-A) A) B matches it. Second, the SSM basis e'A B for this system can be computed and found to match Legen- dre polynomials. However, despite making this connection and writing out formulas for this SSM, (Voelker, 2019) did not provide a complete proof of either of these two connections.
The procoding two steps that motivated the LDN can be informally written as the chain of transformations (i) transfer function e - (ii) SSM (A,B,C) - (iii) Legendre polynomials e'A The HiPPO framework in a sense proceeded in the opposite direction. (Gu et al., 2020) started by defining the system that convolves with truncated Legendre polynomi- als, and with particular differentiation technique showed that it could be written as particular SSM which they called HiPPO-LegT, This SSM turned out to be the same (up to minor change in scaling) as the original (A.B) defined by the LMU, thus proving the second of the two steps relating this particular SSM to the Legendre polynomials.
In this work, we show the final piece in this reverse chain of equivalences. In particular, we start from the LegT SSM (A, and directly prove that its transfer function pro- duces Padé approximants of the exponential. Our proof introduces new techniques in an inductive argument that can be applied to HiPPO SSMs beyond the LegTT case, and relates them to continued fraction expansions of the exponential.
We comment on a minor difference between the parametcrization of HiPPO-LogT and the LMU. The LMU is originally defined as
1 x' azt))) 2
where 0 is a hyperparameter that controls the length of the window. However, we point out that such constant scaling of the SSM is also controlled by the step size A as discussed in Section 3.3. Therefore 0 is redundant with A, the LegT matrices defined in (Gu et al., 2020) and in this work do not have a concept of 0. Additionally, in this work we redefine the LegT matrices (A, to be scaled by factor of 2 to make them properly timescale normalized, using the theory developed in Section 3.3.
A.6 OUR FRAMEWORK
Compared to these works, our framework (Definition 2) simplifies and generalizes the con- cepts directly in terms of (lime-varying) state space models. We define a more natural concept of orthogonal SSM, derive very general instantiations of it (Section 3.1), and flesh out its properties (Section 3.3). Our general result subsumes all prior cases including all cases of the L.STL direct corollary. Some concrete advantages include:
It allows more flexible transformations of polynomial bases, such as including a change-of-basis inside the polynomials. The previously expained case of LegS is
13

---

an instance of this, which has basis functions L(e-)) with an exponential change basis, instead of vanilla polynomials.
It can be applied to non-polynomial bases, such as the truncated Fourier basis FouT.
It does not require considering multiple cases depending where the basis func- tions are supported. Instead, we handle this by considering discontinuities in the basis functions.
A.7 APPLICATION IN DEEP LEARNING SYSTEMS
While the preceding discussion covers theoretical interpretations of SSMs, S4 (Gu et al., 2022a) (and its predecessor LSSL (Gu et al., 2021)) are the application of these SSMs to deep learning. In comparison to prior works such as the LMU and HiPPO which require pre-determined system (A,B) and incorporate them naively into an RNN, LSSL and S4 use a full state space model (A, as completely trainable deep learning layer. Doing this required resolving computational problems with the SSM, which was the main focus of S4. Specifically, the results in HiPPO (Gu et al., 2020) and LSSL (Gu et al., 2021) only guaranteed theoretical efficiency: in particular, they showed how the various computations can be done with near-linear number of arithmetic operations and does not specifically guar- anteee any sort of numerical stability- the main theoretical contribution of S4 (Gu et al., 2022a) was to give numerically stable algorithm.
In this work, we make a distinction between НiРPO, which the theoretical derivation and interpretation of particular SSMs (A,B), and S4, which is the incorporation of those SSMs as a trainable deep learning layer with particular algorithm.
B EXPERIMENT DETAILS AND ADDITIONAL. EXPERIMENTS
B.1 SYNTHETIC RECONSTRUCTION TASK
We construct synthetic Reconstruction Task against a uniform measure. The input is a white noise sequence ue R 4000 We use single layer linear S4 model with state size N 256 and H = 256 hidden units. Models are required to use their output at the last time step, vector y4000 E R 256 reconstruet the last 1000 elements of the input with linear probe. Concretely, the loss function is to minimize ||43000:4000 W W400ool lž, where W E I 1000 256 is learned matrix. Models are trained with the Adam optimizer with learning rate 0.001 for 20 epochs.
Fig. 6 shows that S4-LegT and S4-FouTT, the methods that theoretically reconstruct against uniform measure, are far better than other medhods. We include the new diagonal vari- ants (S4D) proposed in (Gu et al., 2022b), which are simpler SSM methods that generally perform well but do not learn the right function on this task. We also include method S4-(LegS/ /FouT)) which combines both LegS and FouT measures by simply initializing half of the SSM kernels to each. Despite having fewer S4-Fou' kernels, this still performs as well as the pure S4-FouT initializing.
B.2 DELAY (CONTINUOUS COPYING) TASK
The Delay Task consists of onput-output pairs where the input is white noise signal of length 4000 bandlimited to 1000 Hz. The output is the same signal shifted by 1000 steps (Fig. 4a). We use single layer linear SSMs with H = 4 hidden units and state size = 1024. Models are trained with the Adam optimizer with learning rate 0.001 for 20 epochs.
B.3 LONG RANGE ARENA
The settings for LRA use the same hyperparameters in (Gu et al., 2022b). A more detailed protocol can be found in (Gu et al., 2022b). To be self-contained, we recreate the same table of parameters in Table 2.
C PROOF DETAILS
We furnish the missing proofs from Section 2 in Appendix C.I. We will describe our general framework and results in Appendix C.2, and prove the results in Sections 3.1 to 3.3 in Appendices C.3 to C.5 respectively.
14

---

(A min, max)
(A min, A max)
(1e-3, 2e-3)
(2e-3, 2e-3)
(1e-3, 1e-1)
(2e-3, 1e-1)
S4-Leg5
66.581
-6.6388
-3.5055
-3.3017
S4-LegT
-7.4987
-8.1056
-2.9729
-2.6557
S4-FouT
-7.4889
8.3296
-3.0062
-2.6976
(Le(SSSS/Fo)T)
-7.4992
8.3162
-3.4784
-3.2628
S4D-LegS
-6.1288
-6.184
-3.8773
-3.3317
S4D-Inv
-5.9362
-6.0986
-4,1402
-3.7912
S4D-Lin
-7.1233
-6.6483
-3,973
-3.5991
S4D-(Inv/Lin)
-6.839
-6.705
-4.325
-3.8389
Figure 6: Log-MSE after training the Reconstruction Task. (Left) When the timescales A appropriately for this task, the methods that thcoretically reconstruct against a uniform measure (LegT and FouT) are much better than alternatives, achieving MSE more orders of magnitude lower than other SSM initializations. (Right) Interestingly, when the timescales are not set correctly, these methods (LegT and FouT) actually perform worst and the diagonal methods introduced in (Gu et al., 2022b) perform best.
Table 2:
The values of the best hyperparameters found for LRA. LR learning rate and WD is weight decay. BN and LN refer to Batch Normalization and Layer Normalization.
Depth Features !! Norm
Pre-norm
Dropout
LR
Batch Size
Epochs
WD
(Amis (amas)
OistOps 256
128
BN
False
0
0.01
50
40
0.05
(0.001.0.)
Text
16
(0.001.0.1)
Retrieval
256
BN
True
0
0.01
64
20
0.05
(0.001.0.)
Image
50
(0.001.0.1)
Pathfiuder
256
BN
True
0
0.004
64
200
0.03
(0.001,0.1)
Path-X
256
(0.0001,0.01)
C.1 PROOFS FROM BACKGROUND
This corresponds to results from Section
Recall that for OSSMs, (p,w) and are uniquely determined by each other, so we can refer to OSSM by cither. One direction is obvious: (p.w) determine K via K,, =p,
Proposition 6. If set of kernel functions satisfies K (t.))) (t))) where the func- tions Pr. are complete and orthogonal w.r.t. ws (equation (7) right), p and are unique.
Proof of Proposition 6. Suppose for the sake of contradiction that there is second basis and measure In.Hl such that 9n is complete and orthogonal w.r.t. μ, and K,, 9nf.. By completeness, there are coefficients Ce& such that
Dt = Euaa
Then
J ppa)H= / C X Ecenddk =ces.
But qju=Kı K, -Pjw,
/ pegju= pepjw=ōe:
So at ct - which implies that pt =t ge for all É, desired.
The main barrier to using Proposition 1 for function reconstruction is that SSMs are in general not OSSMs. For example, even though we will show that (4) is TOSSM, and that unitary conjugation of a TOSSM is TOSSM (Section 3.3), its diagonal matrix of eigenvalues is not TOSSM. This both shows the existence of an SSM that is not an OSSM, and also implies that general conjugation does not preserve TOSSMs.
Proposition 7. There is TOSSM with the diagonal state matrir A = =diag -1,--,,,--
15

---

Proof of Proposition 7. The SSM kernels ( the kernels are not degenerale.
1((44)) Bn. Assume B, + 0 so that
Suppose for the sake of contradiction that this was a TOSSM with measure w(t). Then must have
/ Kn (m)))))(()))(()7ddd 8n,m
Plugging in n= 1, m= =1 and n= 0=0m==22 gives
1 -
B,B, 21 e (Iw (1 ds- d / (())
f
(B-" Bae 3t (1) dss / (()((())
This is clearly a contradiction.
C.2 GENERAL THEORY
Consider measure supported [0,1] with density (())((t), where T(t) is the indicator function for membership in the interval [0,1]. Let the measure be equipped with a set of orthonormal basis functions Po,...N-11 i.e.
(13)
where the integrals in this paper are over the range oo,,, unless stated otherwise.
This sufficient to derive an OSSM based on the HiPPO technique. The generalized HiPPO framework demonstrates how to build (T)OSSMs utilizing time worping to shape the time interval and tilting construct new sets of orthogonal basis functions.
Given an general interval [er]] we will use the notation T[(.r] to denote the indicator function for the interval [f,r]- we will drop the interval if 0-0
We will need the notion of "time warping" function as follows:
Definition 5. A time warping function is defined as
-(t,s))(-oo,)))]
such that -1,t)=11
We will be using special case of time-warping funciinnnn which we say has discontinuity at to for some to E (-oo,t]:
[(l.)))[((.))((...)))
(14)
such that
2 (t,s)) Øt To (. =c(t) )
(15)
Os
We allow for =---00 in which
think of the interval [to.t] as (-oo,t].
Before procooding, let us clarify our notation. We will use d and a, to denote the partial derivatives Be (t,s)) and 5. (t,s)) respectively. We will drop the parameters (t,s) and use instead of ft,,s) when it is clear from context to reduce notational clutter. Further, we will extend this notation to function composition, i.c. write (t.s)) as g(f) and function prod- uet, i.e. use fgh instead of ((t.s) Finally, we'll shorten fghoo(t,s) as fgh(o).
We also define the tilting X and show that regardless of warping, can construct a new orthogonal basis (note that the result holds for warping functions as (14) and not just those as in (15)).
Lemma C.1. For the set of orthonormal functionns W= orthogonal over measure wl, the set of basis functions
orthogonal over the measure (((o(t.s))==((t)))p(((((
for time-warping function satisfying (14) and any x(1.5) that is non-zero in ils support.
16

---

Proof. Consider the following sequence of equalities:
f
Py(o)p/ooW((ojodd
(a())))
(1(
(o(t))
(
((..o))
Py ()()))(())w())))
Ps (y
6zp-
In the above, the second equality follows from the substitution y (t,s) and hence dy=o,de and the final equality follows from (13). Then since x(t,s) is always non-zero, have
f [wwpse/)tccoooooooooooolooooooo dd==
as desired.
Without loss of generality, split x into product
x(t,s) ((o((,)))(((ss)
(16)
of one part that depends on and another arbitrary component.
Time Warped НiРPO. Since we have an orthonormal basis and measure, we can try
to derive the (T)OSSM. For given input signal u(t), the HiPPO coefficients defined as the projections.
(t) = (u.XPm))
= =f j(()) (p.x)))x)..)
defined as inner product of u(t) with the tilted basis functions XPa with respect to the mcasure a defined in Lemma C.1. For additional convenience, we use the decomposition
x o- from (16) to get:
In (t) (t)= 100=uut (O
(17)
The HiPPO technique is to differentiate through this integral in a way such that it can be related back to (t) and other (t). We require for every we require that there are set of coefficients (Tink N-1 such that
Σ k=0
Ink (pnewr))
(18)
and for tilting component Φ
d
(((.))=d(((((..)
(19)
Theorem 8. Consider a set of basis functions Pm. orthogonal over w, time warping o (1,s) as
in (14), (15), and tilling x in (16) and (19) with the functions o w.Da obeying (18). IJ
17

---

de +0, further assume that for some vector A', have N N 00,
u(to)= = 5
A T
(20)
k=0
Then (A (c(t) (a)) ,B D) is an OSSM for basis functions XPn (P)( with measure ollt -2 where
nn Pink
with Tak as in (18),
D D== dt
dt
and
B, (0=0000))((00))))
Proof. Applying the Loibniz rule to (17), we get
(t) - (t)+ (a+a (t),
where
(.(0) (t) u(s) o (p (o)
[[to o. øds
(t) (p.r)))))
Øt (o.0) ds
and the 20 (t)+
(3) (t) terms capture the term we get when differentiating I[to.]].
Let us consider each term separately. The first term
(t)= u(s) or (prani) (o flo
(21)
corresponds to the differentiation of the basis functions and measure. In order to relate this to {*x(t); it suffices that of (p, satisfies (18) which implies that when we vectorize this, we get (t)=
For additional warping and tilting terms, we consider
1 (1) f (0)=) (pnn)))))
0 Øt (0.
ds.
To reduce this term to Fn (1), recall from (15) that
0,(o,)=c(t)o.
Then the above and (19) imply
=(0=0)
where c((),((t) are defined as in (15) and (19).
We will end up with x (t) (c(t) + ((t))=x((). This leads to the the vectorized form
(t) (t)) ((t)
We now need to handle
O Ito.t] (ar0)ds. s (2) (1)+ (p) Ot
(22)
For the above note that
I[to,t](s) - (s- -
where H(x) is the "heaviside step function." " It is know that = ='(x)=((z) which implics
dla
6(s-t) : [|o.t]] =
di 6(s-
πt
Using the above in RHS of (22), separate out _ (1) and x: (t) follows. First, define
18

---

< (t) u(s)
u(t))
In the last equality, we have used the fact that ((,1)= =1 by definition. It follows that in vectorized form we have x (t) Bu(t). Finally, define
2/ (t) - ( ( (p) to) dtg
o, dt
dia
= utt( (ttoo)
dt
If dta =0, then we have D= and hence we have x =0 (A= x(t)-aDu(t)
dt
If dia de f0, then N ~0, from (20), the above comes out to
(1r.w dia 2 (1) - Σ a Al
N-1
(dd+)()))
dl It follows that in vectorized form we have (1)) -DD(= a(()) aDu(t). The result follows after combining the terms.
km=0
We see that the behavior of is the model is dictated by to. In particular, in this paper, will consider two special cases.
Corollary C.2 (to independent of t). The SSM ((d)))))) of Theorem 8 with to independent of t, is an OSSM for basis functions (Pn(a) with measure wIll tolto.t where A Ann as in (18) and B, (1)
satisfying conditions
Proof. Follows from Theorem Since to is independent of t, then di =0, and D=0.
de
Corollary C.3 (ln=1-0). The SSM (A (()))))() B salisfying con- dilions of Theorem 8 with to 1 for fleed 0, is an OSSM with basis functions XPa(a) with measure tll, where A nk Yokk in (18), D (o 0), and
B,
Proof. This follows directly from Theorem 8 by setting to =t =t
C.3 TIME-VARYING VARYING WINDOWS
C.3.1
EXPLANATION OF S4-LEGS
Consider the case when
a=w
Le. the measure is completely "tilted" away, and let
a(t=))= Øt Let's consider the special case of (23) where =(t)=0. This is most generally satisfied by a(1,s)= =xx=))==xp((()+=(()))
(23)
Note that the condition ((,1)=1 lorces == Hence, we have
a(l,s)= =xp(()))))(
(24)
We consider the following special of Corollary C.2:
19

---

Corollary C.4. n20 The SSM of I, is an OSSM for basis functions and measure
where to is independent
w(o)
w(t,s)=I(()) al (s())22nt1
Pn(
0
w(o)
where a salisfies (24),
exp((==ss)sa = =
(25)
A = ank such that
vP Σ ankPk(l)
(26)
k=0
and
B, Bn=-
Proof. Given a orthonormal basis Po.PI....PN. with respect to measure w. Note that time-warphn tame-warping function satistying (24) implies that o, (s)o.
We fix tilting x(t,,) - an which in turn follows by setting
We show shortly that satisfy the pro-conditions of Corollary C.2, which implics (with our w(a) choice of x and σ) that we have an OSSM with basis functions Pn (t,s)= on Pr((o) and measure
((t)))= =I[to,t] a' (
w(o)
To complete the proof, we show that out choice of parameters above satisfies the conditions of Corollary C.2 (by showing they satisfy the conditions of Theorem 8). We verify that a and é satisfy (15) and (19), noting that
==.a))=-'((
and
01(0) - (t) This implies that setting o(t)=aa'd and d(t) nja (t) is enough to satisfy (15) and (19). Further, note that (24) and the fact that == imply that
o (()r)))
It follows that (18) is satisfied as long
(0 Σ Cmnipaor
for some of coefficients {aak k which is exactly (26). This implies the Ynk Corol- lary C.2 satisfy.
Ink Tnk= (t)a Let A be the matrix such that Ank -Onk and then note that -a'(t((A is exactly the first parameter the SSM in Corollary C.2. Similarly, recall in Corollary C.2
B, (t) (1)''
where the final equality follows since in our case, as (1,1)= ())xp)((()))((( Over- loading notation and letting B,, Bm=p.(1), all conditions of Corollary C.2 hold, from which the claimed result follows.
20

---

We are particularly interested in the following two special cases of Corollary C.4. Corollary C.5. The SSM (A) B) is OSSM for bosis functions Pa (w()) with measure {I(to.t(($) w(( where A ank in (26) and B, P..)..
Proof. Letting (t = & implies that a(t) Int. Then we can observe that is case of Corollary C.4 with time warping
= =xp, cxp((Int++Ins)) = =exp(n(<<())
We set 7=0 in Corollary C.4, which in turn sets ==00=1. This gives the tilting
x=
=w.
Then by Corollary C.4, it follows that that we can use a and x to build an OSSM with basis functions
w(o)
pm( -(
σ
with measure
I(o) a' a'(s)22141 w(o)
I(o) w())
Then the result follows.
Corollary C.6. The SSM (-(A+)),B) OSSM for basis functions pro Praee--)uul (w(=-)) with measure w= [=]]ttot](e* Tj where A = ank as in (26) and B,, (1).
Proof. This case of Corollary C.4 where d((t)=1)) o exp(s t), and we pick n 0, implying that Φ= p=o==1 =1 It follows that
x= -
=w.
Utilizing Corollary C.4,
and x to build an OSSM with basis functions
w(a)
a Pm (a) (()==)(( ())
with measure
I(a) a' d'(s)22041
I[o) exp(s-1) t) w(o) w(exp(s- t))
This gives us our final result.
Next we instantiate Corollary C.4 to prove Corollary 3.1. (Even though strictly not needed, instantiate Corollary C.6 and Corollary C.5 to prove Theorem 3 and Corollary 3.3.) To that end, we will need the following result:
Lemma C.7. Let the Legendre polynomials orthonormal over the interval [0.1] be denoled as Ln. Then
Σ 2k 122+ILL(()) ILa())
-
2
(27)
21

---

- 2n+11
E
22 1La (v)
(28)
Lnnknn-ln-k is odd
and
(2)))=(2+1)) and
(29)
Proof. The Legendre polynomials satisly the following orthogonality condition over 1-1,1]:
[ Pnn())Pa(z)d=== 2n+1 6mn
2
Let denote the normalized Legendre polynomials orthogonal over [-1,1] as Am
where Xn / To orthogonalize them over [0,1], let y= - It follows that == 2y 1 d== 2dy. Note that we then have
[ (z)))) / 2P. (2,.(2y))))
This implies that
2n+1
22 (2 - 8mm
2
Then if let
(30)
then we have an a set of functions over [0,1] such that
L Lm Ln (y) 8mn
From (Chihara, 2011, (2.8), (2.9)), note that (o(-1)=(-1)" and Pa(1)= This implies that
- ( =1
Finally note that (30) implics:
= 1)
=2/2n+1PP
From (Gu et al., 2020, 7), we gel
p²())=
Σ
(2k=1)
OSkSn- 1,n- is odd
Using (30) on the above, we get (28).
We now consider
-L2,00=20222-1PPCCC
=(L+2)V2n+1P(())
From (Gu et al., 2020, 8), we get
n-1 Σ
(2=
(2k+ 1)
k=0
22

---

Then the above becomes
(1) - 101--2100 2m+1 nPn(22+ - Σ 12k 1))()))))))))))
k=0
(30) implies that (z(z)
Ln(u) V2n+I thus
22k +2k++10(2)) -Lu(e)
Σ km
We now re-state and prove Corollary 3.1:
Corollary C.8 (Corollary 3.1, restated). Let Ln be the Legendre polynomials orthonormal over the interval [0,1]. Define (t.s) =exp(a())=a()) The SSM A, is OSSM with ((, (s)o(t,s) (s))()
Po Ln
where A and B are defined as in (4).
Proof. We consider our basis functions, the Legendre polynomials, which are orthogonal with respect to unit measure. This allows us to invoke Corollary C.4 with = 1. Further, here we have to = 00 and 1=0. Now we have an SSM:
(A +
where A ank in (26) and B, (1).
From (29) observe that B, 12 From (27), we have
(2n+1) (2k+1) k<n k=n otherwise
Onk
We write that A= -AA (A*+I) Indeed,
if k<n k= n. (2n+1)
-(A nk
n+1
k>n n Thus the A and B match those in (4), which completes claim.
0
We now ro-state and prove Theorem 3:
Corollary C.9 (Thcorem 3, restated), Let Ln the Legendre polynomials orthonormal over the interval [0,1]. Then the SSM ( A, B) is a OSSM for basis functions L..()) and measure [[to. where and B are defined as in (4).
Proof. We consider basis functions, the Legendre polynomials, which orthogonal with respect to unit mcasure. This allows uss to invoke Corollary C.5 with w w.1. Now we have
a' (1) = 1 [- (x00)
where A Osnk in (26) and B, - (T).
From (29) observe that B, (2n+11 1, From (27), we have
(2 (2k+1) k<n k=n otherwise
Onk
We write that A 4 I). Indeed,
23

---

(2n (2n+1)
k <<n k= n,, if k >> n
- -1)
n+1
0
which completes our claim.
We now restate and prove Corollary 3.3.
Corollary C.10 (Corollary 3.3, restated). Let L, be the Legendre polynomials orthonormal over the interval [0.1]. Then the SSM (A,B) is TOSSM for basis functions (e(e with measure = I[t, where A,B are defined as in (4).
Proof. We consider basis functions, the Legendre polynomials, which orthogonal with respect to unit measure, warping function o = exp(s- t), and with tilting X= w. We note that =xpxpss t) satisfies (24) with, (t) =1 This allows to invoke Corollary C.5.
Then <t) (A 1) (tt() Bu(t) orthogonalizes against the basis functions In(e²=²) with measure to- K, (t,s) (n (5 t), hence get the claimed SSM form utilizing the same argument for A,B as the proof of Corollary C.9
where = Onk as in 26. Note that the SSM basis functions
This explains why removing the 1. factor from HiPPO-LegS still works: it is orthogonalizing onto the Legendre polynomials with an exponential "warping".
C.4 FINITE WINDOWS
C.4.1 LEGT DERIVATION
Corollary C.11. Let Ln be the Legendre polynomials orthonormal over the interval [0,1] and let =1 f for constant 0. Then the SSM (1 B) is a OSSM for basis functions (o) with measure [(())t((o) where A,B are defined as in (5).
Proof. Out plan is to apply Corollary C.3, for which must show that the basis functions (t,s), time warping (t,s), and tilting x(t,s)= = -6 1-6-16 (tt,s) satisfy (18), (15), and (19), respectively. We first set some parameters note that because w= 1 and set -====1
The above implies that we have
Te =((=)w)\\()=--1111
The above along with (28), we see that the Legendre polynomials satisfy (18) with
1 2- (2n+1))((2++1)
k <<n and n-k is odd otherwise
Ynnk
(31)
0
We also note that o. = 1 It follows that
0.
d
-0-00 di
satisfying (15) trivially by setting =0t)=0. Similarly, since 6=1 (19) is also satisfied trivially by setting d(t) = O. Finally we note that the Ln forms a complete basis over [0,1], hence N -G, have
N-1 ult 8)
N-1 Σ da (0). k=0
Σ k=0
(o(tt)))(((
The above defines A' by setting A', = (0) (as well as c=1 and d=0.) Now by Corollary C.3, we have an SSM
24

---

(A"-D(A') ,
where D, (,)) and by (27) A inn (as in (31)) and = (m
From (29), we have Dn a (2n 1) (-1)" and B, / (2n+1)
Thus, we have
f - (2n+ 1) (2k+1) (2+(-1)^~h) ht <<n and n-k is odd otherwise
A - -DA)')
nk 0 - (2n+ 1) (2k+ (-1)) (-1)a=
The proof complete by noting that A -DA) A and B.
We note that Corollary C.11 implies Proposition 2. More specifically, Proposition fol- lows by setting 0 = in Corollary C.11 and noticing that the OSSM there is actually TOSSM. (Technically we get basis function (1- for mcasure ((1-t) but this is OK since (11)
fo (tdd)))
We first give proof of Theorem 4. Then, we prove Theorem 9 as a function approximation result pertaining S4-FouT.
C.4.2 EXPLANATION OF S4-FoUT
Proof of Theorem 4. We seek to derive A and B' from (6) using Corollary C.3:
We use the time-warping function (f,,s) = 1 - (t-s), which implies that we have
[t. s) =1,
(32)
0 (t,s)= =0
(33)
0t
Thus, take
0 (t,s)) c(t)o,
c(t)=0 in
(34)
ot
We then have x(1,8)= =1 as we set
(t,,s) = =tt,))
(35)
d ((t.s) =0.
(36)
So, we can take
a(t)=0) in d ottss) = d(t))(tts).
(37)
dt
We also have =1 and we order our bases in the form Pa = (L where the basis functions have derivatives:
(1)(()==0)
(c.)((a) 2TTs
(s,) (
Consequently, we can define Yak as follows:
2nn
1 - 1, i odd
Ink
2
n-n=1, 1, n odd.
(38)
otherwise
Further, the discontinuity at to =t-0, 0, 0 0=1 which implies that de -1 We now seek to the stored approximation to at time to compute u(t-
Note that this (-indexed.
25

---

First, denote the latent state z(t) with coefficients x= (=="""().(((()))(()))))))a) define the functions o(s) and w(()) such that we have
and
- (()))=(21-8-)) 8-11-88111 and wrs) +u(s) for (
2
Now, let û.O, and v denote the reconstruction of u, and w, where we have a(t,s) (u(s), E [u(ssssaaoottt)))sss(tttt)) (uua
(39)
((tss)=(v(s),.))) (1(s)).s((0((ts)))))).)))) (/tp:/sss((((t)))>>((>(>>s>>)>))
(40)
(w (wtt)) (41)
Then, we claim that
a(t,f) =(()+((() (000=a(((====(((((=aaaaaaa u(1)+u(1-1)
(42)
2
2
Towards that end, we examine the sine and cosine coefficients of u and v as follows:
(v,cx) (
1.tlds
(
(43)
( (w,
(v,8%) (()))((((()))[[[[-1]--- 1o0000d==/(111s11110
(44)
s \
(u
Here, for (43) and (44), we use the change of variables s' t- 2- s- which gives us (tt.))=1((t- (t-s) =1 (1+t 11 (2t-
=1 (+ (1--
Then, we use the fact that c, - ott, = (ottts)) but s, (1 (t.,s') - (ottss))) That is, both and v have the same cosine coefficients but negated sine coefficients of each other. But, we know that both (t, 1)) = (1- 1))) = (0) 0 and (a((t)))) sn (t (t-t))- = sn (1)=0,
=0 O, and hence, the reconstruction of á at the endpoints and (tt.t) = 1 depends only on the cosine coefficients, whence we assert that the reconstruction à agrees with 0 at both endpoints. Therefore, we have = that vi((,I)=ū(L.)
implying
Note that w continuous and periodic, for which the basis S1,c,.sh). is complete, and hence, we know that as N + xc, i + w. Thus, at s =tt, we have @(t,t) = wt,tt) = w(t) = u(t)+vit)) +(t)+((t-1) which completes the proof of the claim in (42).
Recall from (39) that we can express the stored approximation of u(t), given by a(t,s), as follows:
a(t.s) = (u()) ((()))))))(())))ss((((()))))()))
+ Σ (uts))cc(otts)))ccootttss
For the value at t, the approximation ((t,t) is then given by
a(t,t)=x* (1) + Σ (1())c((1)+ Σ =1== Σv22(()
Due to (42), we know ult - 1) 2ū(t,t) - ut)), which combined with the above yields: u(t - 1) = 2x (t) +2v > #t(() uu().
(45)
26

---

Finally, with regards to Corollary C.3, for Theorem 8, (34) satisfies (15) and (37) satisfies (19) with (38) satisfying (18) for A Moreover, from (45), can take == 1,d = -1, and k ==0
A/.
2v2 & odd otherwise
to satisfy (20).
Invoking Corollary C.3 now yields the following OSSM:1
(A + (c((+)(())==)D(A))))) B B-dD),
where A Ynk with D, and B, specified as follows:
n=0
D
V2 n odd otherwise
(46)
n 00 22, odd otherwise
B,
(47)
Here, the values are derived from the expressions of Corollary C.3:
= (.--
and B, - (),
and from (32) and (35), as(t,s) = with (1,ss) ((t,s) =1. 1. Thus, (46) is due to 1 (0)- but c, -1 v2. Similarly,
Recall that we have Pa E (n,
(47) is because (00)-1=1,s, (1)-1=0 but again (1)-11-
Now, we have
2
æ=k=0
1
n=
[D(A') Iin
Ink
2/2
n=0, k odd k=0, odd
dD
/2 odd
4
ni, odd
otherwise
0
otherwise
As dd()= 0, we define A+ A" ADD('"" and B+ BDd, given by
2
n=k=0
-2v2
n n=0, 0, odd or k=0, n odd
n=0 0
-4
n.k odd
An
B,
2
n odd otherwise
2nn
n-k= 1,k odd k-n=1,n odd otherwise
0
-2
0
C.4.3 FUNCTION APPROXIMATION ERROR
Theorem 9. Let K(t) be a differentiable kernel on [0. 1], and let K(t be its represen- tation by the FouT system (Theorem 4) with state size N. If K is L-Lipcchitz, then for <> O.N 4)² +22 have | S.. If K has k- derieaattee bounded by L, then we can take N2 (2 ( 2 +2.
Proof of Theorem 9. First, the state size being N dietates that there are [N/2] 8, and c, basis functions each. We fix time and denote z and x; to be the respective coefficients for 8n and en basis corresponding to S4-Fou. Since (sn,Cann2 forms an orthonormal basis, by Parseval's identity, we have
K KI
Σ
+t)++)+;
(48)
[N/2
'Recall that, like the coefficients, the matrices 0-indexed.
27

---

Thus, in order to bound the error, it suffices to bound the high-order coefficients by inte- gration by parts as follows:
=f - (K,en) ((t)ca(1)dt
(t)
Sn (t)
- -imn (f)))s
2T
2nn J. K' (t)))(ttt)
The quantity in the bracket vanishes 8n is periodic. Therefore
(t)tss,.t) 1 2 / [((())lss(ttddt 2nn 2o
where we use the fact that is I. I.-iisshitz. For on a similar argument holds and we get:
1 (t(t),,(t)dt
L
- 2n Jo
(t)))llc
2T Ju
2mn.
Due to (48), this then implies that
K - 1
xn (1)+ (t)
Σ
(t)
=
1= N//2
n= N/2
2L
2L
2L
(2T))²
(2T)
(2x)² [Av/2]
[N/2]
[N/2
2
(49)
72(N-2)
We use (49) to get the following estimate on || - KK]]:
|| - 11- TV (N
Thus, suffices for N to satisfy the following inequality:
L
T,
VN-22
N
+2.
(NN-2
xC
πC
We now use the same argument as above to the fact that has order-k bounded derivative. By iteration, get:
= S (2mT)* L' k(1) (1)s I (2mT)* L (Is (2mm)*
L
Again, due to (48), this then gives us the following estimate the square error:
|| K - R ===
x2)))
[2 (())
[N/2]
N/2
20
21
2122
OC
21
(2m )
(2T)
2k
(2
([N/2_)
== [1/2]
n=
N/2
I
(50)
n 22k (N 11-211 2)2k-1
If K has order b-bounded derivatives, then we use (50) to get the following estimate on [K-K] K]]
1K-klla 72
Again, it suffices for N to satisfy the following inequality:
L
x²= ThE
I
-N x+1/2 Sc 22
N2
+
the
28

---

21
0.4
0.2
0.0
Figure 7: (HiPPO-LegT.) (Left) First 4 basis functions (t) for state size N = 1024 (Proposition 2).
(Right) Choosing a particular C' produces spike kernel or "delay network" (Theorem 10).
C.4.4 APPROXIMATING DELAY NETWORKS
The original motivation for the LDN/LM /MU (Voclker, 2019; Voelker al., 2019) worked back- ward from the transfer function of the desired delay function impulse response K(t)= 1), and noticed that the SSM for Padé approximations to this were linked to Legendre poly- nomials. This was not fully proven, and we state it here and provide a full proof.
Theorem 10. For A,B,C.D in the Leg'T system described in Theorem 5, the transfer func- tion (()()))s) is the [N-1/N] Padé approzimant to = ({)(t-1))(s).
We remark that although LegT (LMU) is designed be an "optimal" approximation to the delay function via Padé approximants, it actually produces weaker spike function than FouT (Fig. 7 vs. Fig. 1) and empirically performs slightly worse on synthetic tasks testing this ability (Section 4.3). This may be because Padé approximation in the Laplace domain does not necessarily translate localization in the time domain.
Finally, we prove Theorem 10. Note that this a stronger version of the LegT portion of Theorem 5, while the FouT portion is corollary of the proof of Theorem 4.
We start by working out some calculations concretely to provide an example. The SSM corresponding HiPPO-LegT is
-1
A= p
1
p
-1
1
B= B=P
C=ZTp²
P diag 1+2n]
Z = -1 -1]
The transfer function is
C(sI- BB
(In the RHS and for the rest of this part, we will redefine A to be the #1 matrix found above for convenience.)
Case N We have A= and the transfer function is C(sI-A) 143
29

---

Case N=2. The transfer function is
H
C(sI-A)-
sP
s+1
=11
-1]
[+1
1+
-1]
-
4s +2
1+s
3
3
2 24
3
48
+2
3
3 3
1 1-3
1
3
82
It can be verified that this is indeed [x/2]exp (-s).
A General Recursion. We will now sketch out method to relate these transfer func- tions recursively.
We will redefine to be the vector that ENDS +1. The main idea is to write
A Ap-1
Zn
A,
n-1
-1
[sP-1
An-1
-n--
(sPr n2 An)
1+
n-1
2n+1
Now we can use the block matrix inversion formula. 5 Ideally, this will produce recurrence where the desired transfer function (s An)-11, will depend on 1n-1(sPP n 1 However, looking at the block matrix inversion formula, it becomes clear that there are also dependencies on terms like (sP n-1 -An-1) 11,1 and 2 - An-1)-12,T_1
The solution is to track all of these terms simultaneously.
We will compute the 4 transfer functions
(s) H
Ha(s):
H**(s) H
1T An) -1Zm
[ 1 -1 1n
m2 n A
Zn (sP A.. -1
-
Z, (sP-1 A., A.,) 1
IT (sP-1-A,,) -A, 1,]
(sP,-
Z
Lemma C.12. Instead of using the explicit block matrir inversion formula, it will be casier to work with the following factorization used to derive it (block LDU decomposition")
A B
I
T
16
A-
C
D
CA-1
D-CA-11 B
1 1
A
B -1
[
-A-'B
[A-
(B- - 0 0
C
D
0
1
0
httpp////aaaaiiiiiiiooo////aaaad inversiion
30

---

Using Lemma C.12, we factor the inverse as
(sPa- A,) In (sP R-1
An-1) nn
(sP-) An-1)
+ +(-1)= (- (5)
2
I
T (s sP-1
An 1 1 n-
Now we compute
I-
(sP-1 n-1
An-1) 1 2n
1
I- (sP-1) AA Zn-1
n-l
I
1+
(8)
Z
1-
and
I n-1
Znn 1n]
n- ssP n-
A
1
I--1
Zn-1
1
- -T n-1
1
1
1
Zn-1
1 1-11
H (8)
1
H
31

---

Now can derive the full recurrence for all these functions.
H (8)
(s)
Hn(s)= =
H (s) (s)
(sP -An)- 1. 1n]
[n-1 (sP - An-1) Zn-
Z
PsPr n-1
1n-1)
H- 1 + 2 + H nー (5)
I
[zn 1n
(sP n-
1n 11
1 1+ 1+ H
-
1 H 23
(sP 1n-1)
1+ 2n+1
H n- (8)
Z n-1
1 n_
1 12
1 H 11
カ- (8)
(sP 1
1
1- 1n
n-
1+
8
+ -
[1+ 1-H!--
1+
2n
(s)
11
(3)
+ + -= (s)
[1+ [1+ 1s)
1- (s)
2n+1
Now we'll define few transformations which will simplfy the calculations. Define
(s) - [+ (1+ 11+ (s))
C (s)===11 =1 (s)
(s) =1 1- -
G (s)= (-1 H (8)
These satisfy the following recurrences:
Gh= G=) (s)
(s) (
Gl 1 (s) 2(2n+1)
G (s)
(s) = Gll [
Ch (8)+ + 2(2++1)
G ( Gl
(s)
G (s)
Gl= 2(2n+1)
G (5) n (s)
G Gz (-1n--
G (5) 2(2x+1)
We can analyze each term separately.
Case G1 (s).
32

---

This will be the most important term, as it determines the denominator of the expressions. Simplifying the recurrence slightly gives
G (5)
G (s) = 1 G (s)+ (s)
C (s) 212n+1)
(Gh 18) 2(2n+1)
Gl (8)
2(2n+1) 1J
1 (s) 2(3++1)
Now let (s)
(s) (1:(s) where P.Q are polynomials. Clearing the denominator Q yields
(s)(s)
(Pl= (8) 1[2++]] Q Q (8)) 2(++TJ P1 1*)
(s)(s)
1 (s) 2(2n+1) Q
This results in the recurrence
Q (8)+ 2(2n+1 1n-1(s)
8
pl (s)= (8) 2n +1)
pl= (8).
But this is exactly the fundamental recurrence formula for continuants of the continued fraction
1+
Therefore Q!=n()) are the denominators of the Pade approximants.
Note that by definition of P.Q,
Plx 11=1(8)+ 2(2n+1)
(1)(ss)
(s)+ 212
1
11=
Q1:
Going forward we will also suppress the superscript of Q, Qn-1 be evident that all terms have the same denominator (s)
1
as it will
Case G (s).
First note that - (s) is straightforward from the fact that their recurrences are identical. The recurrence is
(s) Gl1 (s) G (()
G 2(2+1]]
G11 11)1(s)
2(2+11)
G , (8) + 2(2++1)
2(21+1) 1 (s)Qn-1(3)
P, (8) 2(2n+1) Qn-1(s)
(8) 10)@n-144 (8) (n)s)
2(2++1)
Therefore
71
G (s) 2(2n+1)
G (5)
2(2i +1 1)
11 2(2+1)
G (s)
(s)
Case G#1 (s).
33

---

Define
P (s)
G (s)
Qn(s)
This term satisfies the formula
_ - (())
G (8) = G G
1 (s)-
_ (8) + 2(2n+11
p=l (s)
[1i=0 2[2++1]
n-1
(Q)-1(s)2
(-1)m-)
2n- (8)
Qn(()
Qn-1(8)
2
p: (=)
I1,-0 2
(-1))-1
Qn- (s-1(s)(m(s)
Qm
By definition of p=
P (-))))))-)-)
(s)(0))
2(2
But note that this is exactly satisfied by the Padé approximants, by the determinantal formula. of continued fractions. This shows that G)) are the Padé approximants of e as desired.
C.5 NORMALIZATION AND TIMESCALES
Proposition 11 (Closure properties of TOSSMs). Consider a TOSSM (A,B) for basis func- tions P.(t) (t) and measure w(t). Then, the following also TOSSMs with the corresponding basis functions and measure:
1. Constant scaling changes the limescale: (cA,cB) is TOSSM with basis p(cl) and measure w(tt)e.
2. Identity shift tilts by exponential: (A+cI,B) is TOSSM with basis p(t)e and measure 2t)e2at
3. Unitary change of basis preserves measure: (VAV* (V) is TOSSM with basis Vp(t) and measure w(t).
Proof. We define p(t) to be the vector of basis functions for the OSSM (A,B),
(o())
p(t)= =
(t)
Recall that the SSM kernels are (t) (t) that p(t) B.
1. The SSM kernels
McA)) (cB) B (( cp((t)au(c))
It remains to show that the (ele are orthonormal with respect to measure aw(c)):
py(c))p (c))
which follows immediately from the change of variables formula.
Using the commutativity of A and I, the SSM kernels are
(A(te))) B e et (
It remains show that (a) at are orthonormal with respect to measure 21)
f f1,()) -a ((()))()((())e"" (t(t) =f (())((())))(())====))))))))))))) 65)
3. The SSM basis
VV V B-V
34

---

It remains to show that the basis functions Vp(t) orthonormal with respect to (t).. Note that orthonormality of a set of basis functions can be expressed as [v(()((())())==== =I, 80 that
f (VD(t))((((V>((t)===
=v | p(t)w(t)p(t) V
I.
Normalization. A standard aspect of training deep learning models, in general, concerns the scale or variance activations. This has been the subject of much research on train- ing deep learning models, touching deep learning theory for the dynamics of training such as the exploding/van /ranishiinniiiggggg gradient problem (Hochreiter, 1991), and a large num- ber of normalization methods to ensure properly normalized methods, from the simple Xavier/Ht initializations (Glorot and Bengio, 2010; He et al., 2015) BatchNorm and LayerNorm (Ioffe and Szegedy, 2015; Ba et al., 2016) to many modern variants and analysos of these (Davis ct al., 2021).
The following proposition follows because for a TOSSM, s(I) can be interpreted as pro- jecting onto orthonormal functions in a Hilbert space (Proposition 1). Proposition 12 (Normalization of TOSSM). Consider an (infinite-dimmnsiionaa) TOSSM. For any input u(t), [[x(( - -| f ((s))w(t-ssddl
Corollary C.13. For a TOSSM with probability measure (t.e. fw(t)=1) and any constant imput u(t)= = c, the state has norm is the entries of C are mean 0 and variance 1.
||=((t]] c² and the output y(1 has mean 0, variance c?
Note that the probability mcasure requirement can be satisfied by simply rescaling B. Corollary C.13 says the TOSSM preserves the variance of inputs, the critical condition for properly normalized deep learning layer. Note that the initialization of C different than a standard Linear layer in deep neural networks, which usually rescale by factor depending on its dimensionality such as N- & (Glorot and Bengio, 2010).
35


Reviews:
[{"review_id": "mbcimh0GTP", "reviewer": "Reviewer_ZKrd", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors study the problem of learning continuous-time dynamical systems using NNs. They focus on the Structured State Space Sequence model (S4) and on a particular matrix for initializing the SSM called a HiPPO matrix. They used Legender polynomials to explain the ability of the HiPPO scheme to capture long dependencies. Their analysis helps them derive new guidelines and variants of the method that lead to performance improvement on Long Range Arena and Path X.", "summary_of_the_review": "Overall the paper is well-written and provides a nice contribution to the community. The HiPPO framework seems very promising, and the authors provide new analysis and new variations of the methods with Legender polynomials or Fourier Basis functions. This enables them to improve SOTA in several tasks.\nFor these reasons, I recommend accepting the paper. \n", "strength_and_weaknesses": "Strengths: The paper is mostly well-written, and the English level is satisfactory. The paper provides a contribution to an important problem by analyzing a leading method in this field. The analysis also leads to practical improvements in several challenging tasks that require modeling long dependencies with NNs.\n\nWeakness: The paper is very busy with information, without much space for intuitive explanations of some of the results. I would move some plots to the appendix, and add a conclusion and expand on some of the explanations to add intuition to the reader", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "dBAGB_YwgJ", "reviewer": "Reviewer_96u9", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper makes three key contributions: (1) theoretical understanding of the role of the state matrix in modeling long-term dependencies. (2) derivation of new HiPPO matrices and showing that it captures many of the existing variants. (3) explaining the role of time-scale $\\Delta$ in capturing the long-term dependencies.\n\n\n", "summary_of_the_review": "The paper makes three key contributions: (1) theoretical understanding of the role of the state matrix in modeling long-term dependencies. (2) derivation of new HiPPO matrices and showing that it captures many of the existing variants. (3) explaining the role of time-scale $\\Delta$ in capturing the long-term dependencies.\n\nThis paper is out of my area of expertise and I cannot judiciously assess the quality of the paper. Unfortunately, I read the paper late and I could not withdraw from reviewing it.", "strength_and_weaknesses": "The theoretical contributions of the paper seem interesting. The generalized HiPPO leads to better understanding of the role of initialization in the S4 models. It seems that the experiments can be improved with more baselines.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QYNtQQa_4LV", "reviewer": "Reviewer_RaMS", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper provides an intensive mathematical characterization of the S4 model introduced at the last ICLR conference. The paper contains a detailed explanation of the HiPPO initialization schema used in the S4 model and as the main result provides a proof that the seemingly ad-hoc approach of the original S4 is a time-invariant orthogonal SSM. Additionally, the paper provides interpretation of the timescale parameter of S4 and a guidelines on how to set it for a given task.\n", "summary_of_the_review": "The paper contains an important explanations of why the S4 model works and how to properly tune it, together with a modification that boosts performance of S4 a little. However, it is not written as a complete self-contained paper and needs improvements to be publishable.\n", "strength_and_weaknesses": "## Strengths\n- The paper is a well written exposition of the mathematical details behind the S4 model, although see my comments on the poor structure below.\n- Some additional results clarifying previously unjustified parameters of the S4 model.\n- Some experimental evidence that the corrections and modifications of S4 guided by the presented theoretical results may lead to improvements in performance.\n## Weaknesses\n- The paper is poorly structured and at times feels like a part of a chapter on results related to S4 simply pasted into the ICLR format:\n  - Discussion and conclusions are missing\n  - Figure 1 and Figure 5 are virtually the same and their purpose is not too clear\n  - Figure caption of Figure 1 reads like an abstract rather than figure description.\n  - Most figures and tables are difficult to interpret - lacking axis labels, subfigures are not addressed in a common way (e.g. Figure 1a ) but with a descriptive textual statements of their locations.\n  - As written, the paper is not ready for publication and needs substantial editing and modifications before it can be ready.\n- It is unclear whether the results provide enough increment over the S4 paper to warrant a separate publication\n  - Understandably, the manuscript consist a lot of background material on S4 and other prior and relevant work. S4 is a relatively recent model and without this background the paper would have been impossible to follow. However, this leads to my doubt of the format these result should be published in. Possibly a note to the original paper would be better.\n- Comparisons in Table 1 are lacking 1D CNN and LSTM models\n  - I understand that the claim is that these models do not work for long sequences, but a demonstration would be helpful, especially as the S4 model has inspired some boosts in CNN's performance: https://arxiv.org/abs/2206.03398 https://arxiv.org/abs/2210.09298", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "MhC8b5RRFn", "reviewer": "Reviewer_GLgC", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors consider theoretical properties of the Structured State Space model (S4) (i.e., a deep learning state space modeling framework) and propose a characterization in terms of exponentially-warped Legendre polynomials demonstrating its theoretical properties and generalizations including to existing S4 procedures thereby in particular enhancing the characterization of long range dependencies. The developed approach is found to be superior on six benchmark from Long Range Arena and naturally extends the work of Gu et al., 2020; 2021; 2022a to address limitations within the existing S4 frameworks.", "summary_of_the_review": "An extension on the work of S4 including improved initializations and extensions to account for long range dependencies using legendre polynomials. The paper extends existing recent work of Gu et al., 2020; 2021; 2022a addressing limitations of the S4 framework. These results improve upon the existing S4 but the novelty of the framework is somewhat limited, however, the derivations non-trivial and the innovations useful which can warrant publication.", "strength_and_weaknesses": "Strengths:\nThe paper is in general well written and provides strong theoretical insights into initialization procedures and generalizations of S4.\nThe approach provides enhanced inference highlighting the utility using exponentially-warped Legendre polynomials.\nInsights in regards to the setting of the time-scale parameter \\Delta.\n\nWeaknesses:\nThe paper is an extension of prior work on S4 of Gu et al., 2020; 2021; 2022a and although useful the novelty of the proposed approach appears somewhat limited. \n\nThe paper is very dense reverting much information to appendices whereas the paper lacks a discussion and conclusion section and ends somewhat abruptly with the experimental results. I understand the space limitations requires strong compromises but I would encourage the authors to discuss implications at the end to make the paper self-contained within the 9 pages.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster