Provable Benefits of Complex Parameterizations for Structured State Space Models
Authors: Yuval Ran-Milo
Eden Lumbroso
Edo Cohen-Karlik
Raja Giryes
Amir Globerson
Nadav Cohen
Venue: NeurIPS 2024 poster (2024)
Keywords: Neural Networks
Theory
Structured State Space Models
Mamba
S4
Complex parametrization
Primary area: learning_theory
TL;DR: We establish formal gaps between real and complex SSMs in terms of expressiveness and practical learnability

Abstract: Structured state space models (SSMs), the core engine behind prominent neural networks such as S4 and Mamba, are linear dynamical systems adhering to a specified structure, most notably diagonal. In contrast to typical neural network modules, whose parameterizations are real, SSMs often use complex parameterizations. Theoretically explaining the benefits of complex parameterizations for SSMs is an open problem. The current paper takes a step towards its resolution, by establishing formal gaps between real and complex diagonal SSMs. Firstly, we prove that while a moderate dimension suffices in order for a complex SSM to express all mappings of a real SSM, a much higher dimension is needed for a real SSM to express mappings of a complex SSM. Secondly, we prove that even if the dimension of a real SSM is high enough to express a given mapping, typically, doing so requires the parameters of the real SSM to hold exponentially large values, which cannot be learned in practice. In contrast, a complex SSM can express any given mapping with moderate parameter values. Experiments corroborate our theory, and suggest a potential extension of the theory that accounts for selectivity, a new architectural feature yielding state of the art performance.

Provable Benefits of Complex Parameterizations for Structured State Space Models
Yuval Ran-Milo'
Eden Lumbroso' Amir Globerson'
Edo Cohen-Karlik Nadav Cohen'
Raja Giryes!
Abstract
Structured state space models (SSMs), the core engine behind prominent neural networks such as S4 and Mamba, are linear dynamical systems adhering to a specified structure, most notably diagonal. In contrast to typical neural network modules, whose parameterizations are real, SSMs often use complex parameter- izations. Theoretically explaining the benefits of complex parameterizations for SSMs is an open problem. The current paper takes step towards its resolution, by establishing formal gaps between real and complex diagonal SSMs. Firstly, we prove that while a moderate dimension suffices in order for complex SSM express all mappings of a real SSM, much higher dimension is needed for a real SSM to express mappings of a complex SSM. Secondly, we prove that even if the dimension of a real SSM is high enough to express given mapping, typically, doing so requires the parameters of the real SSM to hold exponentially large values, which cannot be learned in practice. In contrast, complex SSM express any given mapping with moderate parameter values. Experiments corroborate our theory, and suggest a potential extension of the theory that accounts for selectivity, a new architectural feature yielding state of the art performance
Introduction
Structured state space models (SSMs) the engine behind prominent neural network architec-
tures such as $4 (21), Mamba (20). LRU [1). Mega [37]. S5 [50] and more (3
31
38
34]
their
typical form, SSMs can be thought of single-input single-output linear dynamical systems, wherein
the state transition matrix has specified structure, most notably diagonal [22) 23 41 [0 37 20] A
salient characteristic of SSMs that their parameterizations are often complex (take values in C), in contrast to typical neural network modules whose parameterizations are conventionally real (take values R).
There has been mixed evidence regarding benefits of complex parameterizations over real param- eterizations for SSMs. Some prior works have demonstrated that complex parameterizations
essential for strong performance 22 41]. whereas others have shown that in various settings real parameterizations lead to comparable (and in some cases better) performance 377 20 It conjec- tured (20) that in the context of diagonal SSMs (namely, SSMs with diagonal state transition matrix), complex parameterizations are preferable for continuous data modalities (e.g., audio, video), whereas for discrete data modalities (e.g., text, DNA) real parameterizations suffice. Unfortunately, to date, formal support for this conjecture is lacking. The extent to which complex parameterizations benefit diagonal SSMs remains to be open question.
In this paper, take a step towards theoretically addressing the foregoing question. Specifically, provide two theoretical contributions establishing provable benefits of complex parameterizations
'Tel Aviy University "Google. Correspondence to: Yuval Milo <yuvalmilo@ watttaiiil@mmil..uaa....... tau.aillau..c.ils.
'Due to lack of space, a portion of the paper is deferred to the appendices. We refer the reader self-contained version of the text.
44 for
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

for diagonal SSMs. Our first contribution establishes that, although both real and complex diagonal SSMs are universal- in the sense that both can precisely express any linear time-invarian (LTT) mapping up to any time I when their dimensions are equal to or greater than t-there is strong separation between the SSMs in terms of expressiveness. Namely, denoting the dimensions of the real and complex SSMs by fi and ric respectively, we prove that for any ncc, there are various oscillatory mappings expressible by the complex SSM which cannot be approximately expressed up to time t by the real SSM unless ng is on the order of t. which may be arbitrarily larger than ncc This is in stark contrast to the fact that all mappings expressible by the real SSM can be precisely expressed (up to any time) by the complex SSM whenever ne 2 nig-
Given the prevalence of overparameterization in machine learning, one may question how conse- quential the above separation (between the real and complex SSMs) is in practice. Indeed, in an overparameterized regime where a given L.T mapping is to be approximated up to a given time I and Rg, nic 2 f, universality implies that both the real and complex SSMs can precisely express the mapping up to time f. Accordingly, this overparameterized regime, it a priori unelear whether the complex SSM offers advantage over the real SSM. Our second contribution shows that it does. Specifically, we prove a surprising result by which, if the given mapping satisfies a mild condition, then in order to approximately express the mapping up to time 6, the real SSM must have dimension or parameter magnitude exponential in t. This is in stark contrast to the complex SSM, which can precisely express the given mapping up to time i with dimension and parameter magnitudes that are at most linear in t. The aforementioned mild condition is satisfied by the canonical copy mapping, by basic oscillatory mapping, and with high probability by random (generic) mapping. In such important cases, practical learning of the given mapping necessitates using a complex SSM
Our theory is corroborated by controlled experiments, demonstrating that complex parameterizations for SSMs significantly improve performance. We also evaluate SSMs with selectivity new architectural feature yielding state of the art performance 120 31 4 57 Our experiments with selectivity portray a more nuanced picture: complex parameterizations are beneficial for some tasks, whereas for others, selectivity allows real parameterizations to achieve comparable (and in some cases better) performance. These findings align with the mixed evidence reported in the literature. Moreover, they suggest potential extension of our theory that accounts for selectivity and may elucidate this evidence, thereby fully delincating the benefits of complex parameterizations for SSMs.
2 Preliminaries
2.1 Notations
We use non-boldface lowercase letters for denoting scalars (e.g. a E R, C, E N), boldface lowercase letters for denoting vectors (e.g. x E RR""" v E C"), and non-boldface uppercase letters for denoting matrices (e.g.
12 B E C".m). Series (finite or infinite) of scalars, vectors or matrices are viewed as functions of time and denoted accordingly (e.g. (x(t) E IT (RT),, (A(t) e C*.)) ).............). For series of scalars, we also use as notation boldface uppercase letters (e.g. S
(s(t) E R)EEN I = (i(t) E C)..1......). Given k E N and a series of scalars S whose length is greater than or equal to k. we use S to denote the ktth element of S, and S. to denote the truncation of S to length l: (i.e. the series comprising the first k elements of S), allowing ourselves to regard this truncated series as a vector of dimension k. For k E N U [oo), we use [k] as shorthand for the set (1, k... Given complex number c E C, we denote its magnitude by |c| E B22. its phase by arg(c) E [0, 2T), its real part by Rec) E IR, and its imaginary part by (c)) E R (meaning c= |c| exp(i arg(c)) Me) + (c)).. We let 0 and 1 stand for vectors whose entries are all zeros and all ones, respectively, with dimension to be inferred from context. The Hadamard (clement-wise product, defined between vectors or matrices of the same size, and between scalar series of the same length, is denoted by O. The convolution operator, defined between two (finite or infinite) scalar series, is denoted by *. Namely, given two scalar series S = (s(f))eE()) S = (s(t)) of lengths k, Te E Nu (oo} respectively, S x is the scalar series of length A + 1 whose math element, for m E [k [k+ k 1], is given by mminnm.kk
--1111 s(t)5(m + 1).
2.2 Structured State Space Models
Let K = R K = C. structured state space model (SSM) of dimension E N is parameterized by three matrices: A E IK".", a state transition matrix, which adheres to a predefined structure (e.g. is

---

constrained to be diagonal); B E K".,, an input matrix; and C' E KK an outpur matrix || Given the values of A, B and C. the SSM realizes mapping Pn,(A,,,C) : R + R which receives input a real scalar series (u()))tEN, and produces as output a real scalar series (u(())reN defined through the following recursive formula:
x(t) Ax(t - 1) + Bu(t). s(t) 3((
EeN,
(I)
where (x(t) E IK" JIEN is a vector series of states, and x() = 0 E IK", If = R we say that the SSM real, and if KK C we say that it complex We refer to the SSM as stable if all eigenvalues of A have magnitude strictly smaller than one; otherwise we refer to the SSM as unstable. For convenience, we often identify an SSM with the triplet (A, B, C) holding its parameter matrices, and regard the (single column) matrices B and CT as vectors.
Perhaps the most prominent form of structure imposed on SSMs is stable diagonality, i.e. stability combined with diagonality [22 23 37 20 Accordingly, unless stated otherwise, we assume that the state transition matrix A of an SSM is diagonal and has entries with magnitude strictly smaller than one.
2.3 Linear
Mappings
Let Φ : IN + R2 be a mapping from the space of (infinite) real scalar series to itself. We say that <(+) is linear for all a e E and S, S R holds that @ + S) = a + o(S). For every k E N, define the i step delay og R - R to be the operator that adds h preceding zeros the series it receives as input 5 We say that the mapping o(-) is linear time- lime-invariant (LTT) if it is linear, óu (o())) for every k N. is well known [40] that if (+)) is LTI then it is given by ((S) S (II), where I == (1, 0...O....) R is the impulse series, and (TT is referred to as the impulse response of o(.). Conversely, for any R E R., the mapping defined by S + S
and it commutes with (x)-) (meaning ((&)())
LTI, and its impulse response is R.
We will identify LTI mappings with their impulse responses. More specifically, for any & E N. we identify an LTI mapping up to time k, with the truncation of its impulse response to length k. Accordingly, for any LTI mappings o()),(( and any E Rzo. we say that 6(-) e-approximates Φ(-)
up to time l if [IT()).. - x()x=l S e. If the latter inequality holds with e = 0, we also say that xi-)) matches <(.) up to time k.
Let (A, B) be an SSM of dimension n E N, realizing the mapping (A,(A, R + R (see
Section 2.2h. It is straightforward to see that (n,(A, (+) is LTI, and that its impulse response is given by:
(L) = (RCC)). (CAB), MCAA
For real and complex settings (i.e. for K R and KK C) we will study the extent to which varying (A, B, C) as well as n, can lead (m,(A,B,c)(.)) to e-approximate different LTI mappings up to different times.
3 Theoretical Analysis
Throughout this section, we consider a real SSM (Ag, Bg. O2) of dimension ng realizing the map- ping Pna,(As,Ba Br, (a)( and complex SSM (Ac, Be, Gc) of dimension ne realizing the mapping &ne, (Ac,(Ac,Be,. Co) (-) (see Section 2.2)
which amounts to replacing parameter matrices by certain transformations that depend on additional parameter A E Rzo (e.g., replacing A by (I - A/2 A) A)- + A/2 A)
Variios SSMs include discretization 20 21
16
23 22)). ). With slight modifications, our main theoretical results apply to SSMs with
common discretizations see [ppendix(A.]]oor details.
*Some SSMs include additional feedihrough parameter D E K. 4T.. With feedthrough, the expression for y(t) in Equation (1) becomes RC(((t)) + Du(t)). Our theory essentially applies as is to SSMs with feedthrough- see Appendix(A22 [A.2 for details.
"It possible consider hybrid setting where A allowed to be complex while B and C' are restricted be real. This setting enjoys all provable benefits of the complex setting (IK- C)-see see Appendix A.3 for details.
'That is. for any S = (s(t))EeN E 1e" (S) E R. is the series whose mith element, for m E N. equals
s(m k)) if > k and 0 otherwise.
3

---

3.1 Universality
It is known (see, e.g., 144 that the real SSM is universal, in the sense that it can precisely express any LTT mapping up to any time I when its dimension is equal to or greater than t. Trivially, this implies the same for the complex SSM. Proposition below formalizes these facts for completeness.
Proposition 1. Let Ø: R. + R be arbitrary LTI mapping. and let E N. Then, the following holds for both IK = IR and K = C. ny 2 L. there exist assignments for (Ax, Bg, Cx) with which Amg.AAz Aan.(Ar.B,.Ca Gx) matches o(.) up time
Proof sketch (proof in Appendix D. Beginning with the real SSM (K= = R), the proof shows that (As. Aa. (x) Ba) (.) matches 6(.) up to time t V (Ag))(C @ BR) = (TT).. where ((AR) is a Van- dermonde matrix that has full rank when the diagonal entries of Ag are distinct. Assigning Ag this
way, there must exist v E R with which V(Ag)v = T(T)... Assigning Bg = v and C2 =1
concludes the proof for the real SSM. The complex SSM (K C) can be treated analogously.
3.2 Separation in Expressiveness
Proposition 2 and Theorem below together establish that although both the real and complex SSMs are universal (see Section 3.1 there is strong separation between the two in terms of expressiveness. Proposition formalizes an obvious fact: all mappings expressible by the real SSM can be precisely expressed (up to any time) by the complex SSM whenever ne 2 ng (i.e., whenever the dimension of the complex SSM is equal to or greater than the dimension of the real SSM). theorem[[prroee a much less obvious result: for any ng, there are various oscillatory mappings (i.e. mappings with oscillatory impulse responses) expressible by the complex SSM which cannot be approximately expressed up to time by the real SSM unless ng is the order of t, which may be arbitrarily larger than ne-
2
Proposition 2. Consider arbitrary assignment for (AR, BR, CR), and assume that ne 2 ng- Then, there exist assignments for (Ac, Be, Cc) with which (e = (ng.(Ax.Ba.Ca))
Proof. It suffices to prove the sought after result for og = fgg since one can effectively reduce the dimension of the complex SSM by zeroing out entries of Be (or Cc). Assuming that ncc nz, we may assign to (Ac, Bc, Cc) the values of (Ag, BR, CR.. Under this assignment Bc) Png. (Ag. Bg. C2) (+), as required.
Theorem 1. Let & E N and e E R22. Assume without loss of generality that nc = -1 1 in which case Ac. Br and Cg can be regarded as scalars. Suppose (anag(((A))] 2 0.2, |Ac 2 0.5 and B Ccl 1. Then, if @ne. (x,)() e-approximates Bc. (-) up time I it must
be that ny 2 [19 1 4c.
Proof sketch (proof in Appendix D.2j. The idea behind the proof is as follows. The complex SSM realizes an oscillatory mapping, in the sense that elements 1, ...... 2[t/2] of its impulse response alternate (t)) times between being greater than or equal to 1/4, and being smaller than or equal to - 1/4. The real SSM on the other hand is limited in its ability to realize oscillations, insofar as elements 1,3, ... 2[t/2] - of the impulse response it gives rise decaying exponentials, and therefore can change sign at most ((zR) times. Combining these two observations leads to the desired result.
linear combination of
3.3 Separation in Practical Learnability
Let δ : + Rd be an LTI mapping with bounded impulse response, which we would like to e-approximate up to time t for some e E Rzo and e N. Assume that the dimensions of the real and complex SSMs SSMs can express mappings that match ((-) up to time t, and in particular that achieve the desired approximation. The current subsection establishes that despite this parity in terms of expressiveness, there is a strong separation between the real and complex SSMs in terms of practical learnability.
greater than or equal to t. By Proposition 1 both the real and complex
'It is possible strengthen this result, egg. by showing that the requirement nu 2 t can be replaced by nxx > [tt + 1)/21 when K- = C. We omit details, as the current form of the result suffices for our purposes. "This does not limit generality since one can effectively reduce the dimension of the complex SSM by zeroing out entries of Be (or Cc).

---

Section 3.3.1
proves that under a mild condition on o(.,, in order for the real SSM to achieve the desired approximation, either its dimension or the magnitude of its parameters must exponential in t. Section 3.3.2 then explains that such exponentiality impedes practical learning via gradient descent. Finally, Section 3.3.3 proves that in stark contrast to the real SSM, the complex SSM can achieve the desired approximation with dimension and parameter magnitudes that are at most linear in t.
3.3.1 Real Parameterizations Suffer from Exponentiality
Definition Sacriioonneelol below formalizes the notion of forward difference for a real scalar series-a discrete analogue of derivative for differentiable real function. Our main theoretical result, Theorem then establishes that if forward differences associated with (hh)tthe impulse response S(ts-s certain condition, then in order for the real SSM to express mapping that c-approximates x(:) up to time i, either the dimension of the real SSM ng or the magnitude of parameters (BR. CR) must be exponential
in f. Roughly speaking, the aforementioned condition on forward differences associated with 6(I) is that there exists some d E (()) such that the dth forward difference of the restriction of (II) to either odd or even elements has magnitude greater than 2 Perhaps surprisingly, this condition is especially mild, as the magnitude of the dth forward difference of a real scalar series typically scales exponentially with d. Several important cases where the condition is satisfied are presented below.
Definition 1. Let S be real scalar series of length & E N U {oo}. The forward difference of S, denoted ((1), is the scalar series of length k - 1 whose mtth element, for m [K - 1]. is given by 1}. the dth forward difference of S, denoted S is recursively
Sm+1- Sm. For d E {2, 32.3..... ................................ defined to be the forward difference of ((d-1),
Theorem 2. Suppose (e (.) e-approximates (l)) up to time Then:
Tul CR T BRllo0
max d.MEN, d+ms L [t/2] of (fdd,, even)
2d 22 (2 (6(()))) -c)
(3)
where: (oT)odd and ((I) leven are the restrictions of the impulse response ((I) to odd and even (d) and (ø(I) leven))e)) ) stand for the muh element of the dth elements, respectively; and (Ø(T) odd)
forward difference of o(I) odd and @(I) leenn respectively.
Proof sketch (proof in Appendix D.3.. The idea behind the proof as follows. The restrictions of the impulse response of (Aa,(As Ba (.) ) to odd and even elements-i.e. (nz.(An.Be.C Ba) (o) and (Av. (I) lvenn respectively- are each a linear combination of ntg decaying exponentials, where the coefficients of the linear combination have absolute value greater than ||C& @ Bx lloc. Forward differences of decaying exponentials are exponentially small. Therefore, by linearity of forward differences, requiring (ng.(As,B,.Cu (I) load or (Aa. Bg. BB. (I) even to have a for- ward difference that is not exponentially small implies an exponentially large lower bound on ngl || CR @ BRll When @na, (A..Ba. (.) c-approximates <(-) up to time t, forward differences B2.Caa (D) and Ong, (Ag.Ba [eveen are close to those of @(T) and ((T) respectively. We thus conclude that if ((T) odd é(T) leven has forward difference that is especially small, then n=| Cr @ BRlloe must be exponentially large. This conclusion is formalized via Equation ( the sought after result.
of &ng. (A..
Special cases. Theorem implies that the real SSM suffers from exponentiality (namely, its dimension ny or the magnitude of its parameters (B2, CR) must be exponential in in order for it express a mapping that e-approximates o6-) up time in various important cases. Indeed, Corollaries
I and below respectively show that the real SSM suffers from exponentiality when o(-) is a canonical copy (delay) mapping, and with high probability when ((-) is random (generic) mapping. In light of Theorem (namely, of the inability of the real SSM to compactly approximate various oscillatory mappings expressible by the complex SSM), it natural to ask the real SSM suffers from exponentiality in cases where ob(-) is oscillatory, i.e. where its impulse response oscillates. Corollary 3 below shows that exponentiality indeed transpires a case where Φ(-) a basic oscillatory mapping. On the other hand, there are simple cases where Φ(-) is oscillatory yet exponentiality does not take
5

---

place, e.g. the case where the impulse response of 66.) is (1, -.....) Precise delineation of the type of oscillations that lead to exponentiality deferred to future work (see Section o
Corollary 1. Suppose 2 9 and o(.) = (2 (+), where as defined Section 2.3 ((1-1)/2) (1) the L(t 1)/2] step delay mapping. Assume also that S 1/(8Vt) Then, if (1,. c-approximates (f-) up time t, must hold that:
1iR | o BRllo0 2 2//2 (32V11)
(4)
Proof sketch (proof in Appendix D.4. The proof computes forward differences associated with (1t-1//2 (impulse response of [ ((t(1)/2] (-)) and plugs them into Theorem (Equation (3). n
Corollary 2. Let a E Bay. and let R E RRN be generated by a random process where each element Rf is independently drawn from uniform distribution over the interval [-a,a] Suppose that t 2 8 and that Φ(-) ) is the mapping whose impulse response is R (i.e., o(-) is defined by o(S) = S R). Let p E (0, 1), and assume that S cx/p/t. Then, with probability at least 1 if (d e-approximates (b) up to time i, must hold that:
ng Ca ④ Ballo 2 a2/
(5)
The proof derives lower bounds (holding with probability at le- ast 1-p) on forward differences associated with R, and plugs them into Theorem (Equation )3. O
Proof sketch (proof in Appendix D.5
Corollary 3. Suppose that o(1) = (+1, 0,-1, 0, +1, 0,-1, O,...) and S 0.5. Then, if
(a.. (:) c-approximates (-)) up time t, it must hold that:
nR CC Bxllx 2 231/4-4
(6)
Proof sketch (proof in Appendix D.6). The proof computes forward differences associated with the
series (+1, 0, 01, 0, +1, : 0, -1, 0 .....). and plugs them into Theorem 2 (Equation (3). n
3.3.2 Exponentiality Impedes Practical Learning
For any value of that is not especially small, exponentiality in for the real SSM as put forth in Section 3.3.1 -... exponentiality in of the dimension of the real SSM mi the magnitude of its parameters (BR, (ttd-impedes practical learning. This impediment is obvious in the case where exponential in (in this case, it is impractical to even store the parameters of the real SSM, let alone learn them). Appendix(Bjreet treats the complementary case, i.e. it shows that learning is impractical when the required values for the parameters (Bg,C,, are exponential
(this is deferred to an appendix due to space constraints). The results of Section 3.3.1 therefore imply that the real SSM cannot practically learn a mapping that e-approximates (()) up to time under important choices of ((-).
3.3.3 Complex Parameterizations Do Not Suffer from Exponentiality
Section 3.3.1 established that under a mild condition on o(-). in order for the real SSM to express mapping that e-approximates ø(-) up to time t, either the dimension of the real SSM nı or the magnitude of its parameters (Bs, OR) must be exponential in t. Proposition BJbllw proves that in stark contrast, for any choice of d6-) (whose impulse response o(I) bounded), the complex SSM can express mappings that match (()) up to time t with dimension ne and magnitude of parameters (Be, Ce) that are at most linear in f.
Proposition 3. For any choice of ne greater than or equal to t, there exist assiguments for (Ac, Bc, Ce) with which 2 21I0(I).. l2: and (ii) |ICT ||a
matches o(-) up to time t, and wherein: (i) || <
"To see that exponentiality does not take place when x(I) (1, .), note that in this case.
with any rig, &ne (Aa Cz) (-) c-approximates s6-) up to time whenever: C2 @ Ba holds one in its first
entry and zeros elsewhere; and A holds min (0, (-1 + e/{²)} } in its first diagonal entry.
'It is possible to develop variant of this result that only requires ne 2 [(t + 1)/21. We omit details, as the current form of the result suffices for our purposes.

---

Proof sketch (proof in Appendix D.7. The proof employs the theory of discrete Fourier transform (DFT). It begins by assigning (scaled versions of) the tth roots of unity to the diagonal entries of Aç-
Then, it uses the inverse DFT formula to derive assignments for Be and Cc leading (ne,(Ac, (e,,,,,e.CC) Cc) (+) to match ob-) up to time t. Finally, the proof applies Plancheral theorem to show that the derived assignments for Be and Ce satisfy the desired criteria.
4 Experiments
This section presents controlled experiments corroborating our theory. Section 4.1 demonstrates that complex parameterizations significantly improve performance of SSMs in the theoretically analyzed setting. Section 4.2 shows that this improvement extends to a real-world setting beyond our theory. Finally, Section 4.3 evaluates SSMs with selectivity a new architectural feature yielding state of the art performance [20] 31 4 57]. The experiments with selectivity portray a nuanced picture: complex parameterizations are beneficial for some tasks, whereas for others, selectivity allows real parameterizations to achieve comparable (and in some cases better) performance. These findings align with mixed evidence reported in the literature (see Section T Moreover, they suggest a potential extension of our theory that accounts for selectivity and may elucidate this evidence, thereby fully delineating the benefits of complex parameterizations for SSMs.
For conciseness, we defer some of the details behind our implementation to Appendix F Code for reproducing our experiments is available https:///ithhb. com/ www/edeeweeeeecocoooccceooeee.ee edennudnm um/ SSHComplexParrmmeeeee
4.1 Theoretically Analyzed Setting
To empirically demonstrate our theoretical findings, we trained the analyzed real and complex SSMs
(see Section 2.2) to approximate up to time t the mapping Φ(-) (see Section 2.3). with t varying and with the following choices for <6-): the canonical copy (delay) mapping from Corollary | the random (generic) mapping from Corollary [2] and the basic oscillatory mapping from Corollary 3 Throughout, the dimension of the real or complex SSM (ng or ne, respectively) was set to at least f, which, by universality (Section 3.1). implies that the SSM can express a mapping that precisely matches di-)) up to time I. Our theory (Section 3.3) establishes that despite this parity between the real and complex SSMs terms of expressiveness, there a strong separation between the SSMs in terms of practical learnability. In particular, with the above choices of Φ(-), there are exponential barriers that apply only to the real SSM, and prevent its training from being able to yield a mapping that closely approximates o(-) up to time t. Tables [ and 2 present results obtained with the real and complex SSMs, respectively. They confirm the predictions of our theory.
Table I: In accordance with our theory, the analyzed real SSM (see Section 2.2 cannot practically learn to closely approximate <(-) up to time under important choices of o(-), even when is moderate. This table reports the approximation error attained by the real SSM, i.e. the minimum e with which a mapping learned by the real SSM e-approximates Φ6-) up to time (see Section 2.3). when f = 32 and Φb-) varies over the following possibilities: the canonical copy (delay) mapping from Corollary [ the random (generic) mapping from Corollary [ and the basic oscillatory mapping from Corollary 3 Learning was implemented by applying of three possible gradient-based optimizers- -ddii Adam 29). AdamW (36) RAdam [33]
loss as in our theory (see Appendix C For each choice o(-), reported approximation errors are normalized (scaled) such that a value of one is attained by the trivial zero mapping. Each configuration was evaluated with five random seeds, and its reported approximation error is the minimum (best) that was attained. The dimension of the real SSM (ma) was set to 1024; other choices of dimension led to qualitatively identical results. For further implementation details see Appendix F.
Optimizer
Approx. of Copy
Approx. of Random
Approx. of Oscillatory
Adam AdamW
0.767
0.536
0.812
0.772
0.541
0.809
RAdam
0.767
0.538
0.811
4.2 Real-World Setting
To empirically demonstrate the benefits of complex parameterizations for SSMs in settings beyond our theory, we evaluated the prominent S4 neural network architecture [21 on the real-world sequential
7

---

Table 2: In contrast the analyzed real SSM, and in alignment with our theory, the analyzed complex SSM (see Section 2.2] can practically learn to closely approximate Φf-) up to time under important choices of d(.) and various choices of t. This table reports approximation errors attained by the complex SSM. It adheres to the description of [able with the following exceptions (all designed to stress the superiority of the complex SSM over the real SSM): (i) only Adam optimizer used; (ii) in addition 32, t also took the values 64, 128 and 256; (ži)) for each configuration, the reported approximation error the maximum (worst) that was achieved across the random seeds; and (iv) the dimension of the complex SSM (nc) was set to f (higher dimensions led to qualitatively identical results). For further implementation details see Appendix F.
Approx. of Copy
Approx. of Random
Approx. of Oscillatory
32
1.6 x 10-5
6.3 x 10-6
1.6 x 10
64
1.7 x 10-3
1.6 x 10-5
3.7 x 10-4
128
4.9 x 10-5
4.8 x 10-5
2.6 x 10-3
256
6.8 x 10-4
7.6 x 10-4
1.7 x 10-3
CIFAR-10 10 dataset from the widely recognized Long Range Arena benchmark [52] Our imple- mentation is based on the official S4 repository T0 where unless stated otherwise, hyperparameters (pertaining to the neural network architecture and its training) were kept at their default values. A single run with complex parameterization yielded a test accuracy of 89.10%, significantly higher than the highest test accuracy of 78.27% attained with real parameterization across three random seeds. Modifying the optimizer and initialization scheme with the real parameterization did not improve the test accuracy- see Appendix FrpendixFF22oo for details. The overarching conclusion from our theory namelyy that SSMs benefit from complex parameterizations thus extends to this real-world setting.
4.3 Selectivity
A new architectural feature for SSMs that yields state of the art performance is selectivity 120 31 4 [57.. In its original form proposed as part of the Mamba neural network architecture 120 selectivity amounts to replacing the parameters B and C' (see Section 2.2h. well as an additional discretization parameter A E R by certain functions of the input (u(t))seN. We empirically study the impact of complex parameterizations on SSMs with selectivity by evaluating Mamba neural network on two synthetic tasks regarded as canonical in the SSM literature [27] 20]: (i) copy, which was shown by our theory (Section 3.3) and earlier experiments (Section to pose difficulties for real parameterizations in SSMs with no selectivity; and (ii) induction-head which can be seen as a generalization of copy in which the delay is input-specified (rather than being fixed). Our implementation is based on a widely adopted Mamba repository easily amenable to modification [T] Unless stated otherwise, repository hyperparameters (pertaining to the neural network architecture and its training) were kept at their default values. Further details concerning our implementation. including detailed descriptions of the copy and induction-head tasks, can be found in Appendix F33
Our first experiment with the Mamba neural network compared real and complex parameterizations for the underlying SSMs, with selectivity included. On the copy task, across three random seeds for each configuration, the highest accuracy attained with the real parameterization was 80.17%. whereas the lowest accuracy attained with the complex parameterization was 93.05%. This gap in performance in favor of the complex parameterization aligns with our theoretical and empirical findings for SSMs without selectivity. In stark contrast, on the induction-head task, there is no such gap (in fact, there is a slight advantage to the real parameterization): across three random seeds for each configuration, accuracies attained with the real parameterization ranged between 97.35% and 98.3%, whereas those attained with the complex parameterization ranged between 93.93% and 97.64%. These results align with mixed evidence reported in the SSM literature, by which complex parameterizations are essential for strong performance on some tasks 122 41 22), whereas on others,
real parameterizations lead to comparable (and in some cases better) performance 37 20
To gain insight into the induction head task not benefiting from the complex parameterization, we conducted ablation experiment with partial versions of selectivity (i.e., where not all of the parameters B, C and A were replaced by functions of the input). The results of this experiment, reported in Table reveal that when selectivity is fully or partially removed (more precisely, when
I0 https://gitthub.comm/ http://cmmmmmmannn/rLLae py (MIT license).
(Appacceeeeee/(ppheeecccacaace (Apache-2.0 license).
8

---

Table 3: Ablation experiment demonstrating that real parameterizations compare (favorably) complex parameterizations for SSMs with selectivity, but complex parameterizations become superior when selectivity is fully or partially removed. This table reports test accuracies attained by a Mamba neural network (20) on a synthetic induction-heet task regarded as canonical in the SSM literature 2 200. Evaluation included multiple configurations for the SSMs underlying the neural network. Each configuration corresponds either real complex parameterization, and to a specific partial version of selectivity i.e. to a specific combination of parameters that are selective (replaced by functions the input), where the parameters that may be selective are: the input matrix B; the output matrix C: and a discretization parameter A. For each configum configuration, the highest and lowest accuracies attained across three random seeds are reported. Notice that when both B and C are selective, the real parameterization compares (favorably) the complex parameterization, whereas otherwise. the complex parameterization superior. For further implementation details see Appendix F3
Selective B Selective C Selective A
Real Accuracy (%)
Complex Accuracy (%)
Yes
Yes
Yes
97.35 98.3
93.93 to 97.64
Yes
Yes
No
97.9 to 98.62
90.18 to 95.86
Yes
No
Yes
61.82 to 71.28
91.93 to 96. 77
Yes
No
No
49.91 to 52.5
58.93 to 73.77
No
Yes
Yes
56.78 69.54
92.52 to 96.91
No
Yes
No
41.01 to 43.89
57.44 to 64.67
No
No
Yes
15.48 26.33
68.54 to 79.71
No
No
No
23.86 to 29.62
37.61 to 50.19
B, C' both not replaced by functions of the input), the complex parameterization regains its advantage. This suggests that selectivity, which is not covered by our theory, may be the key factor enabling real parameterizations to perform well as complex parameterizations for SSMs certain tasks. In other words, selectivity may be the dominant factor behind the aforementioned evidence in the SSM literature being mixed. In Section 7 we outline potential extension of our theory that accounts for selectivity and may elucidate this evidence, thereby fully delincating the benefits of complex parameterizations for SSMs.
5 Related Work
SSMs are closely related linear dynamical systems a classic object of study in areas such as systems theory (3] and control theory [5I). Although there exists extensive literature concerning properties of real and complex linear dynamical systems [00 5 6 9. this literature does not readily establish benefits of complex parameterizations for SSMs, primarily due to the following reasons: (i) the output a complex SSM is turned real by disregarding imaginary components (see Section 2.2). therefore it differs from a complex linear dynamical system; and (ii) the structures typically imposed on state transition matrices of SSMs (e.g. stable diagonality; see Section 2.2 are generally uncommon in the literature linear dynamical systems.
SSMs can be viewed special case of recurrent neural networks which received significant In this context, several works focused specifically on However, to our knowledge, the only prior work formally and explicitly treat benefits of complex parameterizations for SSMs is [42 The treatment of [42 considered a task that, using our notation (see Section 2.2 amounts to linearly reconstructing an input element uu() from the state x(t') of an SSM, where t, N, 2 t. This is equivalent to assigning the output matrix of the SSM C' such that the mapping realized by the SSM (n,(A,B,C) (-) is canonical copy (delay) mapping. Roughly speaking. [42] showed that this task requires linear operations with exponential parameters if the SSM is real, whereas linear operations with moderate parameters suffice if the SSM is complex. The same result follows from our Corollary and Proposition 3 We stress that our theory goes far beyond this result, for example in that it covers various mappings beyond copy, including random (generic) mapping- see Section 3.3 for details.
theoretical attention 46 SSMs 442
39
25
I1 553]
58 12
32
55).
(see Section 4.1 therein) can be viewed as special case ours. Indeed, 42
With regards to related empirical work, the literature includes several experimental comparisons between real and complex parameterizations for SSMs (0 22 42). Nonetheless, to our knowledge, the controlled experiments conducted (see Section
are reported herein for the first time.

---

6 Limitations
While this paper offers meaningful contributions regarding benefits of complex parameterizations for SSMs, it is important to acknowledge several of its limitations. First, while we establish a separation between real and complex parameterizations in terms of expressiveness (Section 3.2), we do not quantify how prevalent this separation is, i.e., what proportion of the mappings expressible with complex parameterizations cannot be compactly approximated with real parameterizations. Second, while we prove that real parameterizations suffer from exponentiality that impedes practical learning (Sections 3.3.T and 3.3.2). and that complex parameterizations do not suffer from exponentiality (Section 3. we do not formally establish practical learnability with complex parameterizations our evidence for this purely empirical (Section I Third, our theory does not treat all fundamental aspects of learning where real and complex parameterizations may differ, for example it does not treat implicit bias of gradient-based optimization 49). Fourth, our experiments (Section O include only a single real-world setting. Finally, while we establish that a separation between real and complex parameterizations in terms of practical learnability takes place in three important cases (see Corollaries I to B), these cases are likely far from being exhaustive. Indeed, Theorem provides mild sufficient condition for separation in terms of practical learnability-
that certain forward differences are not especially small-ane we believe it is possible to apply analytical tools (e.g., the Nørlund-Rice integral [77) for translating this condition into interpretable properties satisfied in various important cases beyond those considered. Pursuing the latter direction, and more broadly, addressing the aforementioned limitations, are regarded as important directions for future work.
7 Discussion
The extent to which complex parameterizations benefit SSMs is an important open question in machine learning. Evidence in the literature is mixed: while some works demonstrate that complex parameterizations are essential for strong performance, others show that in various settings, real pa- rameterizations lead to comparable (and in some cases better) performance. It was conjectured by Gu and Dao (20) that complex parameterizations are preferable for continuous data modalities (e.g., audio, video), whereas for discrete data modalities (e.g., text, DNA) real parameterizations suffice.
Since a complex SSM includes twice as many parameters as a real SSM of the same dimension, a priori, one might expect that real SSM would benefit from becoming complex similarly to how it would benefit from doubling its dimension. Our theory showed that this is not the case, and in fact the former benefit far exceeds the latter. Indeed, established separations between real and complex SSMs, by which a real SSM can only match a complex SSM if either the dimension of the real SSM or the number of iterations required for its training exponentially large. Experiments corroborated our theory, and suggested that selectivity-4 a new architectural feature yielding state of the art performance-may be the dominant factor behind the aforementioned evidence in the literature being mixed.
We now outline potential extension of our theory that accounts for selectivity. Roughly speaking, the separations we established between real and complex SSMs arise from gap in their ability to express oscillations, i.e., to express frequency components in their impulse response: while complex SSM can easily express any frequency, a real SSM struggles to do so. Adding selectivity to a real SSM makes its parameters input-dependent, resulting in what can be viewed an input-dependent impulse response. We hypothesize that this dependence allows importing frequency components from the input the impulse response. If confirmed, this hypothesis would imply that when the input data is sufficiently rich in frequency content, selectivity can endow real SSMs with all the benefits we proved for complex SSMs. Such an outcome aligns with the conjecture of Gu and Dao [20] continuous data modalities often consist of only low frequencies, whereas discrete data modalities typically have a "whiter spectrum," i.e.. a more uniform mix of frequencies (54)
We believe that extending our theory as described may elucidate the mixed evidence in the literature, therehy fully delineating the benefits of complex parameterizations for SSMs.
Acknowledgments and Disclosure of Funding
We thank Itamar Zimerman for illuminating discussions. This work was supported the European Research Council (ERC) grants HOLI 81 $19080 and NN4C 101 164614, a Google Research Scholar Award, a Google Research Gift, Meta, the Yandex Initiative in Machine Learning, the Israel Science
10

---

Foundation (ISF) grant 1780/21, the Tel Aviv University Center for Al and Data Science, the Adelis Research Fund for Artificial Intelligence, Len Blavatnik and the Blavatnik Family Foundation, and Amnon and Anat Shashua.
References
[1] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, lan Goodfellow, Andrew Harp. Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke. Yuan Yu, and Xiaogiang Zheng. TensorFlow: Large-scale machine learning heterogeneous systems, 2015. URL https: tensorflor org/ Software available from lensorflow.org,
[2] Ameen Ali, Itamar Zimerman, and Lior Wolf. The hidden attention of mamba models, 2024.
[3] Kathleen T Alligood. Tim D Sauer, James A Yorke, and David Chillingworth. Chaos: an introduction to dynamical systems. SIAM Review, 40(3)-732-732, 1998.
[4] Quentin Anthony, Yury Tokpanov, Paolo Glorioso, and Beren Millidge. Blackmamba: Mixture of experts for state-space models, 2024.
[5] Panos J. Antsaklis. Linear systems/ / Panos J. Antsaklis, Anthony N. Michel. McGraw-Hill, New York, 1997. ISBN 0070414335 (alk. paper).
[6] Masanao Aoki. State space modeling of time series. Springer Science & Business Media, 2013.
[7] Sanjeev Arora, Zhiyuan Li, and Abhishek Panigrahi. Understanding gradient descent on edge of stability in deep learning, 2022.
[8] Assaf Ben-Kish, Itamar Zimerman, Shady Abu-Hussein, Nadav Cohen, Amir Globerson, Lior Wolf, and Raja Giryes. Decimamba: Exploring the length extrapolation potential of mamba, 2024. URL httpa://arxiv. wwwpsii..rrgg/bae. www.ooggg/aa//ooooeeee 14528
[9] Roger W Brockett. Finite dimensional linear systems. STAM, 2015.
[10] John L Casti. Linear dynamicul systems. Academic Press Professional, Inc., 1986.
[11] Minshuo Chen, Xingguo Li, and Tuo Zhao. On generalization bounds a family recurrent neural networks, 2019. Utt.httpss/// tttps::/a///// httpa:////aaai..ooaa///////////e 1atp//991...1111 12947
[12] Nicola Muca Cirone, Antonio Orvieto, Benjamin Walker, Cristopher Salvi, and Temry Lyons. Theoretical foundations of deep selective state-space models, 2024. httpppttaa///axivvccom wwwp:/oorg/bbaae wwwp://////a/00/////// 2202 19047
[13] Jeremy M. Cohen, Simran Kaur, Yuanzhi Li, J. Zico Kolter, and Ameet Talwalkar. Gradient descent on neural networks typically occurs at the edge of stability. ArXiv, abs/2103.00065, 2021. URL https
flapi.ssmanticcchee
wrg/Corpr/rC.......o.... :2: 232076011
[14] Edo Cohen-Karlik, Itamar SeenhinnGrummnn Raja Giryes, Nadav Cohen, and Amir Gloherson. Learning low dimensional state spaces with overparameterized recurrent neural nets. International Conference on Learning Reprexentations, 2023.
[15] Alexandru Damian, Eshaan Nichani, and Jason D. Lee. Self-stabilization: The implicit bias of gradient descent the edge of stability. ArXiv, (ttp//229.111999 2022. URL httptsttttpppp.... semanti cacholar org/CorpusID ID: 252668622
[16] Tri Dao and Albert Gu. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality, 2024. htttpp://aaxxiv.or///bbass
21060
[17] Philippe Flajolet and Robert Sedgewick. Mellin transforms and asymptotics: Finite differences and rice's integrals. Theoretical Computer Science, 144():101-124, 1995, ISSN 0304-3975. doi: hups://doi.org 000016000044337559440088888 030439759400281M
[18] Daniel Fu. Tri Dao, Khaled Kamal Saab, Armin W Thomas, Atri Rudra, and Christopher Re. Hungry hungry hippos: Towards language modeling with state space models. In The Eleventh International Conference Learning Representations, 2022.

---

[19] Karan Goel, Albert Gu, Chris Donahue, and Christopher Ré. It's raw! audio generation with state-space models, 2022.
[20] Alhert Gu and Tri Dao. Mamba: Linear-time sequence modeling with selective state spaces, 2023.
[21] Albert Gu, Karan Goel, and Christopher Ré. Efficiently modeling long sequenees with structured state spaces, 2022.
[22] Albert Gu, Ankit Gupta, Karan Goel, and Christopher Ré. On the paramcterization and initialization of diagonal state space models, 2022.
[23] Ankit Gupta, Albert Gu, and Jonathan Berant. Diagonal state spaces are as effective as structured state spaces, 2022.
[24] Joshua Hanson and Maxim Raginsky. Universal approximation of input-output maps by temporal convolu- tional nets, 2019.
[25] Joshua Hanson and Maxim Raginsky. Universal simulation of stable dynamical systems by recurrent neural nets. In A Alexandre M. Bayen, Ali Jadhahaie, George Pappas, Pablo A. Parrilo, Benjamin Recht, Claire Tomlin, and Melanie Zeilinger, editors, Proceedings of the 2nd Conference Leamiing for Dynamics and Contro,, volume 120 Proceedings of Machine Learning Research, pages 384-392. PMI.R 10-11 Jun 2020. URL htttttt:///ooceeeatttee
mlr, pwwss/v120//aaaeeepe htt.2200/aason2aa. html
[26] IEEE. 754-2019- ieee standard for floating-point arithmetic, July 2019.
[27] Samy Jelassi, David Brandfonbrener, Sham M. Kakade, and Eran Malach. Repeat after me: Transformers are better than state space models at copying, 2024. httpp::/a//aaxxiit www./og//////////////..//.eeeee/ 2402./242..00 01032
[28] Sekitoshi Kanai, Yasutoshi Ida, Kazuki Adachi, Mihiro Uchida, Tsukasa Yoshida, and Shin'y: ya Yamaguchi. Evaluating time-series training dataset through lens of spectrum deep state space models, 2024. URL.
actps://arxiin .rgg abs/ 2408 16261
[29] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2017.
[30] Zhong Li. Jiequn Han, Weinan E, and Qianxiao Li. Approximation and optimization theory for linear continuous time recurrent neural networks. Journal of Machine Learning Research, 23(4)):1-85 2022.
htRp:tt::////mt org/ wwtpppperg//aaaeeeoooo Seaaperssv33/225 22////11222223233222222 htmmmmtmm1 html
[31] Opher Lieber, Barak Lenz, Hofit Bata, Gal Cohen, Jhonathan Osin, Itay Dalmedigos, Erez Safahi, Shaked Meirom, Yonatan Belinkov, Shai Shalev-Shwartz, Omri Abend, Raz Alon, Tomer Asida. Amir Bergman, Roman Glozman, Michael Gokhman, Avashalom Manevich, Nir Ratner, Noam Rozen, Frez Shwartz, Mor Zusman, and Yoav Shoham. Jamba: A hybrid transformer-mamba language model, 2024.
[32] Fusheng Liu and Qianxiao Li. From generalization analysis to optimization designs for state space models, 2024. URL URL
[33] Liyuan Liu, Haoming Jiang, Pengcheng He, Weizhu Chen, Xiaodong Liu. Jianfeng Gao, and Jiawei Han. On the variance of the adaptive learning rate and heyond, 2021. URL, httpttt:ttat....rtrrrrreee aba/ 1908
03265
[34] Yue Liu, Yunjie Tian, Yuzhong Zhao, Hongtian Yu. Lingxi Xie, Yaowei Wang, Qixiang Ye, and Yunfan Liu. Vmamba: Visual state space model, 2024.
[35] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts, 2017, URL 03983
https:///arxiv.or//bbb//
[36] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization, 2019. URL https://arxiv arg/abs/1711.0510
[37] Xuezhe Ma, Chunting Zhou, Xiang Kong, Junxian He, Liangke Gui, Graham Neubig, Jonathan May, and Luke Zettlemoyer. Mega: Moving average equipped gated attention, 2023.
[38] Xuezhe Ma. Xiaomeng Yang, Wenhan Xiong. Beidi Chen. Lili Yu. Hao Zhang, Jonathan May. Luke Zettlemoyer, Omer Levy, and Chunting Zhou. Megalodon: Efficient IIm pretraining and inference with unlimited context length, 2024. URL //axiiv.////iiv///// wrg/abs. 2/////4444088888
[39] Yuichi Nakamura and Masahiro Nakagawa. Approximation capability of continuous time recurrent neural networks for http::t////// stw.aiissmmmtnnccho....... org/ CCorpss Networks, 2009. URL
dynamical systems. In International Conference on Artificial Neural
12

---

[40] Alan V. Oppenheim and Alan S. Willsky with S. Hamid Nawab. Signals and Systems. Prentice Hall, Upper Saddle River, NJ, edition, 1997. ISBN 978-0138147570.
[41] Antonio Orvieto, Samuel I. Smith, Albert Gu, Anushan Fernando, Caglar Gulcehre, Razvan Pascanu, and Soham De. Resurrecting recurrent neural networks for long sequences, 2023.
[42] Antonio Orvieto, Soham De, Caglar Gulcehre. Razvan Pascanu, and Samuel L. Smith. Universality of linear recurrences followed by non-linear projections: Finite-width guarantees and benefits of complex cigenvalues, 2024.
[43] PyTorch Contributors. Pytorch documentation, 2023. URL https::t////pttrccccccm httppppt///pppooc.cc.//////s//ap Accessed: 2024-09-22.
[44] Yuval Ran-Milo, Eden Lumbroso, Edo Cohen-Karlik, Raja Giryes, Amir Gloherson, and Nadav Cohen. Provable benefits complex parameterizations for structured state space models, 2024. URL https
//axxiv. .eriiioorge org/abs ha////b////// /4100 14067
[45] Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
[46] Anton Maximilian Schäfer and Hans Georg Zimmermann. Recurrent neural networks are universal approximators. In Stefanos D. Kollias, Andreas Stafylopatis, Wlodzislaw Duch, and Erkki Oja, editors, Artificial Neural Networks ICANN 2006, pages 632-644 Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-38627-1 38627-8--
[47] Yair Schiff, Chia-Hsiang Kao, Aaron Gokaslan, Tri Dao, Albert Gu, and Volodymyr Kuleshov. Caduceus: Bi-directional equivariant long-range dna sequence modeling, 2024. URL htttps://arxiv.orr///// 03234
[48] Alex Sherstinsky. Fundamentals of recurrent neural network (rnn) and long short-term memory (lstm) network. Physica Nonlinear Phenomena, 104:13 March 2020. ISSN 0167-2789 doi: 10.1016/j. Srssd.2019.132300 URL http:t/dxdd...oo doi org/ 10, 1016/] physd. 201ydd.209..... 2019. 132306
[49] Yonatan Slutzky, Yotam Alexander, Noam Razin, and Nadav Cohen. The implicit bias of structured state space models can be poisoned with clean labels. arxiv preprint, 2024.
[50] Jimmy T. H. Smith, Andrew Warrington, and Scott Linderman. Simplified state space layers for sequence modeling, 2023.
[51] Eduardo D Sontag. Mathematical control theory: deterministic finite dimensional systems, volume 6. Springer Science & Business Media, 2013.
[52] 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, 2020.
URL/https: //tpxv/aavv///////////a////aaava org/ abs/ 200...000000000
[53] Zhuozhuo Tu, Fengxiang He, and Dacheng Tao. Understanding generalization in recurrent neural networks. In International Conference on Learning Representations, 2020. URL httt/htts///ppp www.nticscoooll......
org/Corpus ID: 214346647
[54] Martin Vetterli, Jelena Kovačević, and Vivek K Goyal. Foundations of Signal Processing. Cambridge University Press, 2014.
[55] Shida Wang and Beichen Xue. state-space models with layer-wise nonlincaritn are universal approximators with exponential decaying memory. 2023. URL ltttt:://///ii/// wwtp:/iwwwr./ba/////aao/eooosss wwtp/o/ggwa.......////// 13414
[56] Bernard Widrow and István Kollár. Quantization Noise: Roundoff Error in Digital Computation. Signal Processing, Control, and Communications, Cambridge University Press, 2008
[57] Lianghui Zhu, Bencheng Liao, Qian Zhang, Xinlong Wang, Weayu Liu, and Xinggang Wang. Vision mamba: Efficient visual representation learning with bidirectional state space model, 2024.
[58] Nicolas Zucchet and Antonio Orvieto. Recurrent neural networks: vanishing and exploding gradients are not the end of the story, 2024. URL httLhttss:/// //tari/.////////// org/ hargg/bbs/2400 21064
13

---

A Extensions of Theoretical Analysis
A.1 Discretization
16]. which involves replacing parameter ma- trices with specific transformations that depend on an additional parameter A E Ry0. With slight modifications, our main theoretical results, Theorem I and Theorem 2 apply directly to SSMs with common discretizations. Below, we exemplify this for one of the most common discretizations. Other discretizations can be treated similarly.
Various SSMs incorporate discretization [20 21 23
One of the most common discretizations is the bilinear discretization 21 (Ax, BR, Cxx is parameterized in the following way:
22
in which an SSM
Ax = (1 4/2 Ax) (I + A/2 Ag),
(1- Ag) A
Cx
where E T the matrices Ag, Bx and CK share the same dimensions and are defined over the same fields Ag, Bx and Cx, respectively, and the real parts of the diagonal entries of Ag are negative. Since the set of functions expressible by a real or complex SSM remains unchanged under this discretization, Theorem [ holds without modification. Furthermore, Theorem aapolies applies this discretization if the left-hand side of Equation
B is replaced by Cg T @ Bgl
This follows
directly from Lemma 13 which shows that for any i [mg), we have | (BR), 2 (BR), I- The
latter inequality justifies replacing BR with A Bz on the left-hand side of Equation
33. leading to the
desired result.
A.2 Feedthrough
Some SSMs include an additional feedthrough parameter D E K [1]. With feedthrough, the expression for vtt in Equation (1) becomes R[Cx(() + Du(t)). Our theory essentially applies as is to SSMs with feedthrough, as explained below.
Obviously, an SSM of dimension n without feedthrough parameter can be emulated by an SSM of dimension n with a feedthrough parameter by setting D = O. Conversely, an SSM (A, B, C) of dimension with feedthrough parameter D can be emulated by an SSM (A', B', C²) of dimension n + 1 without a feedthrough parameter. This is achieved, for example, by setting the diagonal entries of A' to be those of A followed by zero, the entries of B' to be those of B followed by one, and the entries of C' to be those of followed by D. For any result where an SSM without feedthrough is assumed, corresponding result for an SSM with feedthrough holds. Such result can be attained by either emulating an SSM with feedthrough by an SSM without (while increasing dimension from ni to + 1) by emulating an SSM without feedthrough by an SSM with feedthrough, (while maintaining the dimension) depending on the context.
A.3 Complex A with Real B and C
is possible to consider hybrid SSMs where A is allowed to be complex while and C are restricted to be real. Below we show that such hybrid SSMs enjoy all provable benefits of complex SSMs (i.e., of SSMs where A, B and C' can all be complex).
There are four results concerning complex SSMs: Proposition Proposition 2 Theorem | and Proposition 3 The first three results can be trivially extended to the setting where only is complex, as their proofs do not assume complex B or C. An extension of Proposition 3 is also straightforward. Indeed, the proof of Proposition Butilizes the fact that for complex SSM (Ac, Be, Cc) of dimension nec the impulse response can be any linear combination of ng arbitrary decaying sine and cosine waves, which, by Fourier theory, can approximate any sequence of length ne. If only Ac is allowed to be complex, the impulse response can consist of any linear combination of nc arbitrary decaying cosine waves, which can still represent any sequence of length ng via the discrete cosine transform. Thus, the setting remains fundamentally similar, allowing for the extension of Proposition 3 to hybrid SSMs.
B Exponentiality Impedes Practical Learning
In this appendix, we show that learning the parameters of the real SSM, i.e. (AR, BR, Cx), is impractical when the required values for (Bz, CR) are exponential in I. We account for two aspects of this impracticality: the number of iterations required by gradient descent; and the precision (number
14

---

of bits) required for representing the parameters. Note that we will not preclude the possibility of overcoming the impracticality through development of new techniques (e.g. new parameterizations for B3 and CR). We believe our account herein may assist in such developments.
Exponential number of iterations. For the sake of illustration, suppose that training the real SSM to realize mapping (As, (s (.) that e-approximates d6()) up to time t, is implemented via gradient descent over loss function ((-) that measures the squared error of the output at time t, where input elements are drawn independently from the standard normal distribution:
(A BR: CR. E UEBR, U, U2.U2... . 1e N(0,) [( Br Ba (U))))
(7)
o(D therefore By a simple derivation (see Appendix C ((As, BR. CR) = (A, Bz.
sufficient minimization of the loss {()) (namely, minimization of {(-) to or below the value e² /t)
indeed guarantees that Png, (As.BB. BxyCk)) e-approximates o(.)) up to time 1. Assume the following regularity conditions on gradient descent: (i) the step sizes (learning rates) for all iterations are upper bounded by constant (independent of t); (ži) the step size for each iteration is stable, in the sense that it is upper bounded by 2/ Amazz. where Xmaz represents the maximum eigenvalue of the Hessian of ((-) at the respective iteration [13 75: and (iti) the values of E(-) throughout all iterations are upper bounded by a constant (independent of t) times the value of E(-) at initialization. Proposition 4 below establishes that under said regularity conditions, during gradient descent, the magnitude of the parameters (Bg, CR) grows at most linearly in the number of iterations. Accordingly, if the required values for (Bg, Cg) are exponential in t and the initialization of (Bx, Cg)) not, attaining the required values necessitates an exponential (in t) number of iterations.
Proposition 4. Consider an application of gradient descent to the loss E(-) in Equation 7
(Ak" Blo c(00) = "A BBi C - 10
VE( VE(AA=1)
B " iEN,
where (A D c(O)) is a chosen iritialization, and r7(0) E E>0 represents the step size selected for iteration E N. Assume 3c, E B25o such that Vi E N : (8) S Ct. Assume also:
(0)
ViE N: (0 $ max {mmaz (V"((A (i-1) B ckk
where Amaz (M)z(MM,, (M). for a symmetric matrix M. is the maximum eigenvalue of M. Finally, assume:
3ee E Ex such that Vi E EN:: ((A B(0) ((u) S c2 {(A _ , c
Then:
Vie N: max
||B 1. [|(c 11
S max | Ic ||(C (0) |
+ i (4crezt (AA
(0) _ C 0.5
Proof sketch (proof in Appendix D.S. Taking into account the form of E(-) (see Appendix C and the assumptions made, the proof shows that at each iteration of gradient descent, each entry in Bg or CR changes by at most (4c102t ((AR) _ C ))).,, This readily leads to the desired result.
Prohibitive precision. With conventional resented as s k 2nh where: s E (-1, 13 (the sign) is represented by one bit; i E N U {0} (the significand) is represented by by E N bits; and m E Z (the exponent) is represented by bm E N bits. The precision of the floating-por ppint representation is the total number of bits used for 8, and m. i.e. it is + by + bm- For example, with the widespread IEFE 754 standard [66: single precision corresponds to 32 bits with by = 23, bm = 88 and double precision corresponds to 64 bits with 6% 52, by. 11. It is customary to model quantization error as additive random vari- able uniformly distributed over the interval [-5/2, where Ş E R> is the quantization step size (56). With the floating-poin point representation of p. the best (lowest) achievable quantization step size is on the order of [p] b-b thus we may model quantization error as a multiplicative random variable uniformly distributed over [1 - g/2, + g/2), where y = O(2-bx). Definition 2 below employs this model to formalize the notion of robustness to quantization for values of (AR, BR. Cz)
sraating-poin representation, a real number is rep-
with which Pra (Aa. Co. (.) e-approximates xb.)) up to time Specifically, Definition 2 defines
robustness g-quantization for such values to be the probability that Ona, B2. (+) continues
15

---

to c-approximate <f-) up to time t. when the values are multiplied by random variables uniformly distributed over [1 -8-9/1 9/2, + q/2]. Proposition 5 below then proves that robustness to q-quantization (at most) inversely proportional to q times the magnitude of (BR, CR.. Recalling that g 022-bx) bx), we conclude that if the values of (BR. CR) are exponential in f, a non-negligible robustness to quanti- zation necessitates having by- St()), meaning floating-point precision that scales (at least) linearly in t. The latter requirement is prohibitive, since virtually all computing systems implementing neural networks entail fixed options for floating point precision (typically 16, 32 and 64
[ 43
all much
smaller than what the time & can be (tens of thousands or more 20 47 19 8)
Definition 2. Let 9 E [0, 1], and let QA QB. and Qcs be random matrices of the same sizes as Ag, Bg and Cg. respectively, wherein each entry independently drawn from the uniform distribution over [1 9/2,1 q/2]. Let (Ag. Bgg C*) be values for (AR, BR, C2) with which (Ag. (.) e-approximates (6.) up to time L. The robustness to q-quantization of (Ag, B C
the probability that (An, BB, Cx) e-approximates Φ(-) up time when (AR, Bg, CR) take the values (Aß Ag Bi O QB
a CR Qca).
Proposition 5. Suppose that (ag.(A c-approximates o(-) up to time t. Then, for any q E 10. the robustness q-quantization of the values held by (AR, BR, C2) is at most:
2// (qlICH o BBRllx).
Proof sketch (proof in Appendix D.9. Denote by (Ag. B3. C+) the values held by (Ax, BR, Oz).
and let Qa Q Bg and Qcs be random matrices in Definition When (Ag, BR, Cz) take the O Q Ba C (*oQc)) ). the first entry of the impulse response of ong. (dg. Ba.
values (Ag O Q Aus B
Ca) equals C O Qc ( @ Qn.): ). It suffices to restrict attention to this first entry, and show that [CCp @ Qcx (Bg @ QB. ((T), < with probability at most (g @ Bgll The proof establishes the latter unti-concentration result.
C Loss Functions
Consider loss function as in our theory (see Equation
77,, applied to both real and complex SSMs:
[(KK, BR, Cx) = E UERM, U... He AT(0.1)
[dnx. -(U).
where I- = R or K C. Below prove that:
t(Ag, BR, Ck) || -(V)
Indeed, as discussed in Section 2.3 for any U E R
(An, (U Onx (An. 6(U), (U o()),
Thus:
P -U) = Σ U, (0w. (acioooo())--- (())
j=1
It holds that:
27
{(A2, Bg, Ck) =E UERN U..U A..............
Σ
U, (Orea -DDe
(ene o(D)-1+1) EU [1]]
1=1
= (1
as required.
16

---

D Deferred Proofs
D.I Proof of Proposition
!
Beginning with the real SSM (K = R), assume that ng 2 t. We would like to show that there exist assignments for (Ag, BR. C2) with which:
((T:: = (Cx BR, OR
CRA
where (():: stands for the first i elements of the impulse response of (-)). Regarding o(T).t, Be and C (column) vectors, we may write the sought after equality ((Ax)(CR BB) ((I.rr where (AA) E |R is matrix whose (i, entry holds the jth diagonal entry of Ar exponentiated by i 1. Notice that V(Aa) is Vandermonde matrix comprising powers of the diagonal entries of Ag. Any assignment for Ag with distinct diagonal entries leads the Vandermonde matrix to have full rank, which in turn means that there exists vector R satisfying V(Ag)v= ((T).. Assigning B₃
and C 1 concludes the proof for the real SSM. The complex SSM (K = C) can be treated analogously, while assigning real values to Ac. Bc and Cc in order to allow disregarding the fact that only real parts of outputs taken (i.e., disregarding the operator R-) in Equation (2)
D.2 Proof of Theorem
To facilitate the proof of the theorem, we first outline essential definitions and lemmas to quanitify a lower bound for the number of times the impulse response alternates between being greater than or equal to 1/4, and being smaller than or equal to - 1/4. Building on this groundwork, we then unpack the main theorem's proof in Appendix D.2.2
D.2.1 Setup for the proof
Definition 3. For an angle we will say that is in the mostly positive region if
5m
i mod 2
0,
2T
3.
and we say that 0 is in the
region if
2xx 4x
0 mod 2nr E
3
3
Remark 1. Under this definition, non-zero complex number æ has that its argument is in the mostly-positive region if and only if R(x) > M mostly-negative region if and only R(x) E
Conversely, has that its argument is in the
Definition 4. We say that set is balanced if at least a sixth of its elements are in the mostly-positie region and at least sixth of its elements are the negattvv region.
Definition 5. The balancing number of complex number with argument 0 is defined as the minimum p E such that for any non-zero real number the set (b + 0,b + 20...., + p0} is balanced. If such p exists, we say that the balancing number of is infinity. We denote the balancing number of æ by ((x).
We will begin by establishing an upper bound on Bxx) for x in a specific region in the complex plane. Subsequently, we generalize this result give an upper bound of the balancing number for almost all complex numbers.
Lemma 1. For any natural number p 2 4, if non-zero complex number has argument 0 such that 0 is in 22x 2x then B(x) S p. Moreover, for any natural number 2 9, if x has an argument
33 2x As then ((x) p.
such that O [TT
Proof. Since the mostly-positinn and mostly- -eetly-negative regions are defined by looking the angle of complex number mod 2n,, to prove that ((x) < p, it is enough to show there exists some number p such that for any real the following set
{b + 0) mod 2T,, (b + 2 0) mod 2 ...., (b + A 0) mod 2T)
is balanced.
Indeed, let there be some real b.
17

---

1. Is in 2x 2x and 2 4, Let à be the natural number such that 2 < <b S 2x - 8. It
follows that 4 S k - p and that S x-1 By Lemma we have that the set
{ mod 2T, (6 + 2 0) mod 2 (6 (6+ k- 0) mod 2
has at least a single point any continuous interval (in mod 2 length A. As such, any continuous interval mod 2 of length must contain at least
2x
2r.
k
F-I
points, where the last inequality true for any k 4. Since the mostly-negative regions are continuous intervals (mod 2T) of length
and
2x we have that the set 3
{(b + f) mod 2m, (b + 2 0) mod 2n, 2 (b + k. 0) mod 2
has least a sixth of its points in the mostly-positive and mostly-negative regions, and therefore balanced, as needed.
2. If is in +
2x
dn and
3
2 9, then 20 mod π is in the interval Therefore, by the previous section, there exists some E
2x
2x 3
which is
contained in the interval
2m
k < such that the following
(b + 20 mod 2....., k- 22 mod 2T)
and the set
{(b - 0) + mod .., (b 0) + k 20 mod 2
are both balanced. Overall, their union, the set
{(b 0) mod 2n, 0) mod 2 (b+ + 2k 0) mod 2x)
is also balanced, showing that the B(x) 2k S p needed.
Lemma 2. For any natrual numbers r, 0 the following holds:
3 (cr+s0) = (c(cr-00)
Proof. For any rational numbers 0 and b, and for any natural number p, will define the set bp the following way:
Su.t,p = {(b + 0) mod 2m, + 2 0) mod ....... p. 0) mod 2n)
We will also define the Sg,p
Sa.p = E C}.
Given this notation, we have that B (c--10) if and only if is the minimum natural number such that every set in So.p is balanced. For any rational numbers 9 and b and for any natural number p, we have
S b.0.bb.p b.p = - So
(Where minus taken element-wise mod 2m). This immediately gives:
S S_. Sa
Since the mostly-positive and have that all the sets in So,p are balanced if and only so are all the sets of S_ This directly implies that (ir) = 3 (e) as needed.
regions invariant taking minus mod 2m,
Corollary 4. If C has that arg(z) mod
1
2n
2n for some p 2 then B(x)
18

---

Proof. Denote 8 = azg( From Lemma if the angle # lies within the interval
2xx
2x
2x
4m
p 3
p 3
then 3(x) S p. Additionally, Lemma indicates that same holds the interval -I (where operations are element-wise mod 2xx
Hence, we have that if 0 is contained in interval I', where
r'
(-I)
2T
2T
2T
4m
4x
2x
2T
2T
+
U
2T
p
p
P
P
2m
2n
2m
2
U
2n
p
p
p
p
then ((x) S p. Overall, this means that if has that
2x
2
0 mod π E
11
p
then ((x) S p, which gives the Corollary.
D.2.2 The Proof
Let 6 > 0 be any positive number. For any sequence X Xx1,X2.- Xe), let X|2 denote the subsequence consisting of elements at odd indices, i.e., X|1 (X1, X3....).
First, we notice that from the assumption that [sin(arg(Ae)) 2 0.2 we have that arg(Ac) E x 16: x 16 and so
2x
2T
arg(A mod π 2 arg(Ac) mod 2
mod
π
16'
9
This implies, by Corollary 4 that the balancing number of A is less than 9. Now, if &n (A, (+) c-approximates One (Ac. Be)Co) (e., (+) up to time i, then, by definition,
(A (I)., Pnc,(Ac,Be.Co (I), 111 sc.
This implies
| (1) (ne.(Ac. (1), lilli Sc.
Now, we have that
(dI,(AC,BC.O)) (1). l1) (DI,AA,Be,CC) (T)x) 24-1
R (Be 42k-22
and because the balancing of A3 is most 9, this implies that there exists a subsequence of 1, 2.2...., Lt/2] with increasing indices ky of length least [i]] 1 such that j is even then k1
BeCe (4 is in the mostly-positive region, which implies
(A3) k
R BBcC (A
BcCcl
2
where the first inequality is due to the definition of the mostly-positive region and the second is implied from the assumption that [B: Ocl 2 and |Acl 2 0.5 Conversely, if is odd it is in the mostly-negative region, which implies
(A3) k 2
R Cc (A2) (A3)*=-1) -|BBCCl
1
4
Next, we will show that the impulse response of any real system, when restricted to even indices, can change its sign most ng 1 times. This will prove the theorem since
1
1
t
ag -1) < II (1) - One.(Ac,Be.Ca (1) lalla sc.
4
19

---

The first inequality results from the fact that there would be least 1 nu
indices where
S (Ai. aI), (1) and (An. (T) la and Be, (1), | disagree on sign, which yields the theorem.
Indeed, let upper bound the number of sign changes of the real impulse response when restricted to odd indices. We have that
(Ora.(An. Cp. (1) = (An. B2. (1))) 2k-1
R (CRAR 12k-2 BB))
C2AB BBR
(Cn) 22-2
By the mean value theorem, the number times (Aa.(Az. Cx) (T) changes signs bounded by the number of zeros of the following continuous function:
[ = (BR),(CR), (()
This function linear combination of ng exponential functions with a positive base, and so by Lemma it has at most nig 1 zeros, as needed.
D.3 Proof of Theorem 2
Let d, m be natural numbers such that d m I [1/2], and let be in {odd, even]. We will show that
ne I Balloo 2 2 2242min(d.n) (2 (o (1) (1))) (a) -e)
thus proving the theorem.
Let (As, Oz. (.) be real system that e-approximates @ (-) up to time t. For convenience, we will denote (A. (I),, by Y and a (I)., by T. Then, by definition, we have that
IT Yll1 Se
which implies that
[ Y|olo Sc.
where Ag is non-negative and (Ax, BR. Cx)
Lemma guarantees that there exist some parameters the following two things hold:
CI c BRll 2 1| T 3 BRll
Y mA. (I)..
Because Ag is neg-negative, Y/, can be viewed as a linear combination of decaying exponentials with positive coefficients. Since the forward difference is linear, Lemma 6 ensuress that the absolute value the dth forward difference of Y|a at index m upper bounded by
m
T o Br Bolo T&R T
d + m
d + m
Using Lemma 12
we get
nz CR T
o BBlloc
(Yb (
2 min(m,d)
20

---

Lemma 8 immlles that
T(a (d)
Y 1/41)
T 1/
2d
(T)) (/o)
(Y)))m)
2d
(T
)m
nR ( 2 BRllo
2d
26+2 (m.
Plugging in [T) Yooloo and Tl we get
ne || BRll
2 (ob (1) ())
2d42
Reordering this equation yields the desired result.
D.4 Proof of Corollary
For simplicity notation, we will denote [= by ls and assume without loss of generality that is odd. Theorem indicates indiicttes that
nhp C2 @ Bx 2 maxd,meN, d+ms t/2] or (odd, even)) { 2 minfd,m) (2 (6(I) - })}
Substituting d k+1 m = 1+1 J. = even, and c I SV? yields:
(Ó(I) even
1
n/ C* + Bllo 2k-1
(8)
2 +
Svt
In the subsequent analysis, we will demonstrate that
2 2
(T(I)
evenn)
4VL
Once established, the remainder the proof will naturally follow since plugging this forthcoming result into Equation 8 will ensure that:
2
2
21(-1)//21
2(1/2)-1
2(1/2)
C @
B
8vi
16v2
16vt
16v1
32
satisfying the requirements for our conclusion. Indeed, we have that for any
k+
(o(I) leven), = (o(I)) = 5x (1)25 = = = =
Lemma 7 implies that
جيةة
(o) even
(o
A+l ر (-1)
{j
1=0
2+1
Σ
k +
k ++1
(-1)
k41 -j
k+1
2
1+1
(-1) الج
1+1
k+1
2
k+
(-1)
k++1
21

---

By Lemma
we can assert:
_
2 _
(o(I) loven
leven)
1
Av 2
4
which completes the proof.
D.5 Proof of Corollary 2
Theorem@liniccale that
ng C O Ball 2 maxdmme d+ms a even) {2d-2 (2-d (Retl) -
For any E {odd, even]. plugging in m [ d [ and S ave
yields:
Vi
(Reto)) (LE!)
avo
Tl Blo 2
2
Vt
In the subsequent analysis, we will demonstrate that for any o E fodd, even], the following holds with probability smaller than vo:
(Rarlo) (L+J) [i
2 20v8 Vi
Once established, the remainder of the proof will naturally follow, as plugging this forthcoming result into Equation will ensure that for any a E {oddd even], with probability 1 vō we have that:
2 33-3a/ 3a58
24av8
n Te| T B
Vi
8Vi
satisfying the requirements for our conclusion. Since R., even and Re are independent random variables, we have that the previous statement holds with probability higher than 6 as required.
Now 1et us proceed with proving the aforementioned result. Assume without loss of generality that even. Lemma 7 Jimplies that
1
Σ R leven) (1))(-) -s [ )
R
Σ (R) 2-14) [
For each. E [[4]]. define the random variable X; follows:
X, (R) (R) (-)
4 j
and denote its PDF by px, We have that
[
a) =((-a -
[ [ )
X,
u u(-
j
which means that
if < <a a
Px, (2) = 2a 2a( [
otherwise
22

---

| Let X be the sum of these random variables X = 2==0 X, and denote its PDF by px. We note that
P
R even
co Pl
cal 20o maxpx(x).
2ER
As sum of i..d. random variables, the maximum of px is upper bounded by the maximum of PDF of each of the random variables it is sum of. Which means that
Vt
max Px (x)
maxpx ZER
(x)
FER
20
[1/4]
22
2x2
(1/8)
(where the second inequality results from Lemma
10P
Overall have that
(1))
coVE
p
R
60
S
202
we have that Plugging in - 2L 2
oven (
(i))
< 211
2a 2
S v88
[
V
which concludes the proof.
D.6 Proof of Corollary
Theorem demnostteed that
ngl C @ Balbo 2 max d+msll/2, oefodd, 22d+2mmnddss (d.m) (2 (2-((()))))) -
-5)
Plugging in a odd, we have that for any E [14/2]] the following holds:
(p(I)))m = (-1)m=1.
Using simple induction, it is easy to show that for any d, m E N such that d + m S [4/2],
(o(I)) (dg (-1)(m+d-11)) 1)2gd
Plugging this into Theorem with odd, d [1/4J, m L1/4J, and 0.5 yields:
ng ||l C Balloc 2 211/4 0.5) 23/ > 231/4-4,
as required.
D.7 Proof of Proposition
It is sufficient to prove the proposition for ne = t since the dimension of a diagonal SSM can always be effectively reduced by zeroing out elements of Be.
According to Section 2.3 it enough to show that there exist assignments for (Ac, Be, Ge. such that the following conditions hold:
(A. = (IIae. ||Bll2 = 2ll ||0 1
For convenience, we will denote Ac, Be, Cc by A,B.
We begin by utilizing the theory of discrete Fourier transform (DFT) to allow us to write the truncated impulse response of ó of length t linear combination of t decaying sine and cosine waves. Specifically, defining (8(1):))
(60a.) I where E (0, 1) is some constant, and denoting
the DFT d(I):e by a + bi E Of we get that
vk E [t]
(o(T) #
Σ
aj+1 (2T 1)2)
>
bj+1 sin 2 -1)²)
j=0
23

---

Now, we will derive assignments for the SSM's parameters so that its impulse response will equate this sum. Indeed, we fix the diagonal entries of Á to be a scaled version of the roots of unity, and C to be the inverse of the square root of / as follows:
A = ac 2
C2
V
We know (see Section 2.3 that the impulse response of a complex system at index &s is given by:
(ALA)B,)))).) =
Σ
BBCB BBC.))
JJ
j=1
Which implies that
R
Σ A
B,C
= Σ
1=1
j=1
2 11/) RR(B))
[-1 Σ
27 112) 3(B))
a
k-1
Σ
cos
sin
j=0
By the Plancherel theorem the following holds:
||a + bill2 = Vt 1(0 S Vell
a²-1
Therefore, if we define B
a-ih vt
we get
Σ A 3
B
k-1
Σ
as+1 cos 2 - -1)((((1)))))
+ Σ
b sin 2 11²
t
j=1
1=0
1=
(o())
and
a bi
| x
1 ||0|2= Vo. t.
(
|B]|2
a
and by choosing a (2) r we get the required assignment.
D.8 Proof of Proposition
For simplicity of notation, let A BB ((0)
be denoted by A B(0, C(i), respectively, and
E(A(), (() by g(o, We begin by writing the loss explicitly (see Appendix C
((A, (A, = Σ
Σ
A
BBCr - -6(1)
J=1
k=1
Fixing any le E [ng]. we have
de(A, B.C)
2 3=1
2
A A C₁
Σ
A B 1m0mmmmm1p (1))
d.Bg
m==
which, combined with the fact that
[Am|
< 1, leads to
de( de(A,B,C) B,C)
ngg
2 CR Σ
A Bm Cm ② (1),
dBB
1=1 m=1
= 2 Ck ((
(I), - の (I)..ll
< 22VT|CH|||onnABB (T), 6 (1a
< 2Vt max
V((A,
24

---

This implies
|BO &c
[B(i-)) Iloo t
((--1) max (|B(-1))
Next, will demonstrate that
n max
B(-))))
- - Voi
which concludes the proof since this aforementioned result will establish that for E N, the following holds:
|B 1o00 (((11) 1c +22/2ttiee (V166-11e
(((-)) 1c0 + 2 VVvtoo t/tc t00000c
(1)
BB 1lx + 2i / tez
(2)
Where (1) holds because we assume ((--1) I czl and (2) by recursion.
Repeating the same argument for C(+) completes the proof.
Finally, let us show that (9( max (||B(i-)) | a S Va.. Indeed, Lemma combined with the assumptions that
2 max Amar 22 1) 1)00}
W <
and Vi N: ( < ci gives that
(1 min
2 2 maxx B(i-1) bo
- ||C(i-))|| } j.
Considering the cases where max immediately get the required result.
is bigger and smaller than 1/ /i we {I) || 11 (|/C//-))) -
Lemma 3. In the setting of Proposition we have for any Ags BR. On the following holds:
Amar (V2((AR, BR, C2)) 2 max 1|0
Proof. For simplicity of notation, let Ag, Bg. Cg be denoted by A, B, B,C. respectively. We will assume, without loss of generality, that ||C|| 2 ||] and denote i arg max; C2 and by e; the one-hot vector with at index and zero elsewhere. We will also denote the following function
(x) = (A (T),
by I((),, and the following loss function:
= (())==(()))
by E, Next, We notice that by definition of Hessian, we have that
(((((A,,)[[B) (0)
Therefore, Amax (V²() at A, B, C is lower-bounded by (0). It is therefore sufficient to show that K (0) 2||CI|2 Indeed, by Appendix C the following holds
25

---

de(A, B.C)
(0)
(dB:)²
d
E/=1
(2m= 1 Bm Cm $ (T);))
(dB.)²
2 d
Σ
A BmCm -11) 24 244--0
dB,
j=1
m=1
Σ
- 'C A
2
which concludes the proof.
D,9 Proof of Proposition
For simplicity of notation, we will denote Ag, BR, CR, ny by A, B, C,n. The robustness to q- quantization is by definition the probability:
P [|onttAAq...q...c3000) (1), o(I) <
S P [n..A00...BBpp..000 (I) ((I) sc
Let us denote the random variable BBA.LAQQA.BQQ.CCC (1) by X, and its PDF by Px- The
probability P[ - Y| S c| is equal to the integral fy y + Px (x) < 2e max Px (2). We get
that
P [IlenttaQA..B0...c000]
(()I < < 2e max px (1) ZER
and so, to prove the theorem, suffices to show that
max (x(x) S 9 o zER
Let us investigate the random variable X:
x Σ (BOQ)) Σ BCC
B,C, + qB, + 40; gB.(o))
1=1
where 9C; ud-q/2,(140 9/2). As a sum of independent random variables, the maximum of px upper bounded by the maximum of the PDF each of the random variables sum of. Specifically, for any i in], it is bounded by the maximum of the PDF of U(-, (/C,q which is equal to 1/,Cg., Overall, this means that
max (x) & min B,C,q ZER
needed.
26

---

E Auxiliary Lemmas
Lemma 4. For any n non-negative numbers .1..... Ons and real numbers b1, ...... bn, the function f defined below
n
f(x)
b;a
can have at most n zeros.
Proof. We will show this by induction. The claim obvious for n let us assume the induction claim is true for n = k and we will show that it is true for n = k + 1. Indeed, let f be the function defined by
k+1
f(x) - Σ b,a,"
b1 = or a1 = we can immediately use the induction step on f. Otherwise, we can write f in the following way:
f(x) b1oî
b
Since b, af is always non-zero, the amount of roots of is equal the number of roots of the function y defined by
b
ai
s(x) =
b1
a1
By Rolle's theorem, the number of roots of function is bounded by the number of roots of its derivative plus one. We have that g'(x) is given by:
by bi
g(x²)
In
a1
a1
Which, by the induction step, can have at most k roots, needed.
Lemma 5. Let O be real number in the open interval (0, 2x), let b be real number in [0, 2z). and let p be a natural number such that 0 2 2x. Then the set
{bb + 0) mod 2m, (b + 20) mod 2m. (b+ p. 0) mod 2T
contains least one point any closed and continuous-mod--2 2n interval of length within [0, 2m).
Proof. Let F2 = (b + k0) for 1,2,....7 Define the intervals
4. (x))). mod 2n for k 1, ...
Each interval / has length of 0. Since p0 2x have that
p
U 4. 2m. k=1
Now, consider any closed and continuous soo-uuuuuu----22-- mod-2 interval J C [0. 2xx) of length f. Since Uh Is [0, 2T), the interval J must intersect at least one of the intervals Ig. That is,
J n 12- + 0 for some k (1,2.....)
Since J has length 0 and overlaps with Ts- (which also has length 0), and since both are continuous- mod-2 their intersection must include least of the endpoints of Tg- which is in the
{bb + 0) mod 2m, (b 28) mod 2n. ....... (b + p mod 2T).
This completes the proof.
27

---

Let a be real number within the interval [0, 11, and let n. m be natural numbers with t being natural number such that t 2 n + m. The absolute value of the mih forward difference of } at index n, defined in Definition / is bounded above by the sequence X = {1, (1,a00 a [11
Lemma 6.
77
n + m
T2 + m7
Proof. By induction, the mth forward difference of X index n (when we start at index 0), for m. is a" 1)" For [0, 1], this absolute value simplifies to:
la" 1)th = an aa)
To find the maximum value of this expression within [0, 1], we differentiate with respect to and set the derivative to zero:
da (a" = nann-an a)m ma"(1 (1-a) m-!
Solving for a, find that the critical points are {0, or:
n(1 a:)
m
A second derivative test confirms that = æ is a maximum within [0, 1]. Substituting into our original expression, we obtain: 7+3
(
((x()))
n
71 + m
m
72
n2 + m
+ m
12 +
thereby completing the proof.
Lemma 7. Given a sequence A ta, a1..... .n- } and two natural numbers m the mith forward difference of A (Definition at index n, denoted (A(m))), n is given by
(A(m)
m Σ 5=0
anty (-+) m
Proof. We will show this by induction over For 0 This is obvious. Let's assume that the Lemma is true for m and prove that it is also true for m k n. Indeed
(A(m+t))
(A(m))
(A(m)
a+1
m
m Σ
Σ j=0
(-1 1) m-
antitl
(-1
m- Un
m (
5
j=0
(-1) 1 Onti-1 (mT + (; ))
#n+mm11
(-1)
an
m
m + 1) j+1
= 0a4m41 - (-1)aM On +
(-1) m Ont
1=0
m + 1 antj
= 0atm+1 - m- On +
(-1) m- m
j=1
m+l1 Σ
(-1) -1) ants
m 1)
j
1=
needed.
28

---

Lemma 8. Given two sequences A = {ao. a1...., 01....,Ox-11 and B = fbo. .n of length and for any natural number m < n,, holds that
||(m)
B(m) 100
- B
2
where A(m) and (mm) are the mih forward difference (Deftnition 1 of A and B respectively
Proof. We aim to demonstrate that
2 | - oo0 2 [|A(T)) 1l
which directly supports the statement of the lemma.
suffices to verify this for the general case can then be established by induction, showing that:
||A(m) - 1lo 21|A(m-1)) B(m-1))loo S... ....5270 5... B pm
Indeed, for m 1, we have that for any i <
((10)) BB last1 0z b bil I aa,-1 bi41+ + la: dul 211A Blloc
Lemma 9. Let One, Be. (I),, be a truncated impulse response of a real SSM denoted by Y. Each of the following two sequences
Y Yood (Y,, Y.....)
and
even (Y Ya,...)
are impluse responses of some other real SSM of dimension ny with parameters (Ax, BR, C2) where Ag is non-negative, and
1 o BRllxo 1 Ballo
Proof. We observe that (see Section
2.3
Y (ooda): = AB 2(1-1) BR
setting (R, = (Ah. Bg, Cx) yields that Yoodd the impulse response of the real SSM ne. Ba,
For the even case:
Y Veven): = CRAB" 21-1 Bg
setting (Az, Br, Oz)= (A2, BR, AR yields that leven the impulse response the real SSM Pn.. (As, (r.)).) In both cases, Ag is non-negative, and
cC @ BRllx 2 110x
BRllx
since in the even case (Ba, Oz) = (BR, CR) and in the odd case |Cazl S |CRyl because |ARa < for all j.
Lemma 10. For any positive integer the following inequality holds:
2n
2
2
2/n
29

---

Proof. Using the Stirling's formula for factorials, we know that n!! is bounded by:
2tn
n2
< n! < V
n
which can be simplified to:
2mn n!
2
We plug the bound in the factorial form of the binomial coefficients:
2n
(2m)!
2n 2n
2n
22n
22n
n! n!!
(V2mn) 2 (2)
c
Tne on
2//
Where the last inequality is due VTTe < for all To complete the proof for all positive integers notice we get equality forn
Lemma 11.
For any positive integer n, the following inequalitie hold:
2
4 2m
2
Proof. Utilizing Lemma 10
have
2m
2
m
2 m
To validate the lemma, we consider cases based on the parity of n. For even n,
2n
2
11 2
4
2n
2
and for odd n,
n
n
2
2
2
2
|
n-1
2
4v
2
2
thereby proving the lemma as required.
Lemma 12. For any positive integers and m, it holds that
m
12
+
m7
22 m2mimmm.n)
Proof. We establish this inequality through direct analysis:
m
min(m.n)
min(m.n)
m
7
+ m
12 + m
1
+ m7
min(m.n)
mn
(n + m)2
mn
min(m,n)
4nvmn
1
22 min((,,
This last inequality leverages the fact that (n m)²
4nm (n -m)²> 0.
Lemma 13. For any complex number x = a + bi with a < 0, it holds that
1
Proof. It suffices show that [1 -x1l 2 Indeed, we have
|| œ = / - a)² 62 2 -1 1
required.
30

---

2h
Input:
X
X
X
X
hh-
Output:
X
X
X
Figure Illustration the induction-head task. See Appendix for details.
Implementation Details
Appendices H1
below present implementation details omitted from Sections 4.
4.3
respectively. Source code for reproducing the results of Sections 4.1 and 4.3 can be found at https://github com/edenluu edenlum/ee/e wewtrompppeppaaaeeeeeeeeee obtained using the official S4 repository, available at https: atttps///gite //tgt/gtttttt////////////t com/ htt//stafee sww.tttpaaceeeeeeeeeeeeeea (Apache-2.0 license). All experiments conducted on single NVIDIA A6000 GPU.
The results of Section 4.2 were
F1 Theoretically Analyzed Setting
In all experiments, we parameterized state transition matrices in a manner that ensures stability, similarly to the LRU architecture [4T]. For real SSMs, we performed a grid search for each optimizer, varying learning rates and initialization schemes. Namely, we evaluated learning rates of 10
10-5 and 1 x 10-6 6 and randomly initialized the diagonal elements of Ag uniformly in [-1. 1] in [.99 [0.99, 1]. For complex SSMs, we used a learning rate diagonal elements of Ag similarly to [41], by sampling uniformly from the complex ring with radii 0.99 to 1. For all SSMs, we employed cosine learning rate scheduler (35] and trained for half million steps.
10-5 and initialized the
F.2 Real-World Setting
Our implementation is based on the official S4 repository, available at hhttps://githut com/ State-spaces// (Apache-2.0 license). Unless stated otherwise, repository hyperparameters (pertaining the neural network architecture and its training) were kept at their default values. The SSM powering the architecture was adapted to a diagonal structure for the state transition matrix A. For real SSMs, began with the same default configuration for complex SSMs, and extended the configuration by performing a grid search over different optimizers (Adam [29], Adam [36), SGD (45) and initialization schemes (diagonal-real, diagonal-lineat and legs, defined in the official S4 repository). We ran three random seeds with the default configuration, and a single random seed with all others.
F33 Selectivity
Copy task. Our version of copy task has delay of / 64. entails input sequences of length 2t, where tokens are sampled independently and uniformly as one-hot vectors of dimension 16. The corresponding output sequences are generated by shifting the input sequences positions to the right, while introducing zero padding. That is, given an input sequence [a1, a.,....... a2.]. the
corresponding output sequence [0, O...., 0, 01 a2,..., ar]. Training and evaluation (measurement of test accuracy) in this task are based on randomly generated examples, where the input is sampled from a uniform distribution. In training, fresh batch of examples generated for each iteration, and the loss corresponding an example is the cross-entropy loss averaged over the last tokens of the output. In evaluation, the zero-one loss is averaged over the last & tokens of the output across one thousand freshly generated examples.
Induction-head task. In the induction- head task [18, the goal is to teach model to identify and copy specific subsequence of the input. Figure T illustrates this task, which our case has an induction head size of h = 128. The task entails input sequences of length 3h, i.e., input sequences with 3h tokens. The first (less than h) tokens in an input sequence are sampled independently and uniformly ont vectors of dimension 16. These tokens followed by special copy token,
31

---

= 0. After the copy token comes a sequence of h tokens, sampled as before and denoted X. The 2hth token another copy token c, after which the first to penultimate tokens of the sequence X repeat. The tokens between the first appearance of X and the second appearance of are irrelevant for the task. The output sequence corresponding to the above-descrihed input sequence is equal the input sequence shifted one position to the left (with the last token of X placed on the right). Training and evaluation (measurement test accuracy) in this task are based on randomly generated examples, where the following aspects of the input are sampled from uniform distributions: the location of the first copy token c, the sequence X, and the irrelevant tokens. In training, a fresh batch of examples is generated for each iteration, and the loss corresponding averaged over the last tokens the output. In evaluation, the zero-one loss is averaged over the last h tokens of the output across one thousand freshly generated examples.
example is the cross-entropy loss
Hyperparameters. Our implementation is based on widely adopted Mamba repository. available at /tttttps://githut com/ LixxddrLL/mamba, py (MIT license). Unless stated otherwise, repository hyperparameters (pertaining to the neural network architecture and its training) were kept at their default values. The Mamba neural network was configured to have two layers with hidden dimension of 64. We trained the network with a batch size of and a learning rate of 1 x 10-3 Training comprised 1,000,000 steps on the copy task, and 250,000 steps on the induction-head task (the latter task warranted a shorter run-time since it was experimented with much more). For complex parameterization, we changed the state transition matrix A, the input matrix and the output matrix C' to be complex, while keeping the discretization parameter A real. To maintain parameter count, the dimension of SSMs with complex parameterization was half the dimension with real parameterization, namely, opposed to 16.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction clearly differentiate between formal contributions and informal discussions.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper includes dedicated limitations section (Section 6
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Every theoretical result is formally stated (as a lemma, proposition, theorem or corollary) and proven.
4. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The paper provides (in Section and Appendix F) references to code for reproducing experiments.
5. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper provides (in Section and Appendix a detailed account of implementation details.
6. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: The paper reports (in Section 4and Appendix F minimum and maximum values across multiple random seeds, while specifying the number seeds.
7. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Answer: [Yes]
The paper specifies (in Appendix F) the type of hardware used for compute, as well details determining the computational load of each experiment (number of training steps, neural network architecture etc.).
Justification:
8. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics http://pp//.eappp..coo///////aaa
33

---

Answer:
[Yes]
Justification: The paper is theoretical in nature, with experiments on synthetic or standard datasets designed to corroborate the theory. As such, it inherently conforms with the NeurIPS Code of Ethics.
9. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The paper theoretical in nature, with experiments on synthetic or standard
datasets designed to corroborate the theory. As such, its societal impacts are self explanatory.
10. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper does not offer data or models that have high risk for misuse.
11. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The paper specifies (in Section and Appendix F) all assets used, along with applicable license details.
12. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The paper is accompanied by code for reproducing experiments (https: / github. wwt.c/oo////ce/e eeeenddelllll um -SS.CompeePaaammeeeeeFee.
and this code well documented.
13. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and sereenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not include crowdsourcing experiments or research with human subjects.
14. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not include research with human subjects.
34


Reviews:
[{"review_id": "ZxvuRypStS", "reviewer": "Reviewer_9K2D", "summary": "The paper deals with an important question: is it possible to show a concrete advantage of complex diagonal RNNs compared to real diagonal RNNs? The motivation is clear, especially for people who studied the SSM literature. While modern SSM variants used in language modeling (e.g. S6-Mamba) do not make use of complex numbers, for some reasoning tasks in the long-range arena, these are necessary. This motivates the question \"which tasks necessitate complex numbers and why?\". The authors start with a useful recap, and correctly point out universality of both real and complex linear RNNs in the approximation of filters. Then show one example of a filter which is represented easily with complex numbers, but requires a huge hidden state if the recurrence is real. Further, the authors discuss a bigger class of filters that comprises random convolutions and shifts: here, real RNN parameters have to explode to reach the correct values. The authors corroborate their findings with experimental validations.", "questions": "See above, + I have another question - something which I might have missed but is my biggest curiosity:\n\n- How do you explain the fact that Mamba on language modeling works better with real recurrences? I am perfectly aware the question is not easy - but given your efforts, I believe your paper should try to answer this question. What you claim in the paper is \"selectivity allows the real parameterization to achieve comparable performance\": this is a bit too quick, on an extremely crucial issue. I expected the discussion to be much more precise on this point.\n\nI will be active in the rebuttal, and will engage in the discussion so to update my borderline score. I thank the authors in advance for their efforts. I know the topic in this paper is not an easy one, but for this exact reason I care the findings are robust and discussion complete.", "limitations": "See above", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I believe in the value of complex numbers in recurrent networks.  I liked reading the paper, and I think many people can find it interesting. However, the theoretical results might not be super surprising for readers who already worked on theory of RNNs (see next part) but experiments are interesting. I think it's good to draw attention to the question the authors study.\nPros: Math is at a good level of formality, notation is precise, and the appendix is well structured. Clarity is good, though a specific thing can be improved (see later). I think with some tweaks, this can be a very good paper. I especially liked some parts of Sec. 3.3.", "weaknesses": "I like the theme of this paper and appreciate the formality and correctness of the results. However, I think some improvements are possible and some things need to be clarified.\n\n- Theorem 1: this is a crucial piece of Section 3. In short, both real and complex diagonal RNNs are universal, but complex diagonal linear RNNs require exponentially fewer parameters to approximate some specific functions. I agree with the proof, which is very simple: you cannot approximate well sin(x) using exponential modes (i.e. real RNNs). It is good to remind this fact, though the result is not novel it helps the discussion. However, while your statement is correct, it might be misleading: it looks like for a big part of the functions of interest in the hypothesis class, complex numbers are crucial. What the theorem actually shows is that for a subset of measure zero in the class of smooth functions, complex valued recurrences are more effective. I agree oscillations are important, but this is not formal and should be toned down. I would phrase this as an example rather than a theorem. It is indeed just a counterexample.\n  \n- The second part of Section 3, Sec 3.3, is completely disconnected: here, you are talking about parameter magnitudes. This is fine, but I was a bit confused by the wall of text at the beginning of page 5. You should be much more schematic. You are now talking about something bit different, and the bridge should be clear but concise.\n  \n- Sec 3.3 is interesting, but I'm not at all convinced that the results you found are orthogonal to those of Orvieto et al. (discussed at the end of page 8). I think your results are stronger, but comparing further makes your paper much more robust: Orvieto et al. shows that to retrieve information from real RNNs hidden states, the readout maps must explode in magnitude. Here, you found something similar, but on the B & C matrices when approximating some filters. I suspect the mechanism is similar, do you agree? I think drawing a better connection is needed, no way those effects have a disjoint cause.\n  \n- Sec 3.3: All bounds you have here should be validated in the simplest toy setting possible. Would it be possible to verify empirically all your bounds in the setting of the propositions? This makes the reader believe much more in the results and makes the bounds clearer and visual.\n\n- Experiments: I like them, but as the authors themselves admit, more efforts are needed. Well my question here is: what would you do next, and why do you think the paper should be accepted without further experiments?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review, for highlighting that “with some tweaks, this can be a very good paper”, and for the willingness to “engage in the discussion so [as] to update [your] borderline score”. Below we address your comments and questions.\n\n## Specificity of Theorem 1:\nTheorem 1 readily extends to any function realized by the complex SSM whose impulse response oscillates. More precisely, the proof of Theorem 1 can easily be extended to establish a lower bound on $n_{\\mathbb{R}}$ that is linear in $t$ whenever the restriction to odd elements of the impulse response of the complex SSM admits a number of sign changes linear in $t$. With this extension, Theorem 1 applies to a positive measure subset of the complex SSM’s function class. Moreover, among the subset of the complex SSM’s function class which is characterized by $A_{\\mathbb{C}}$ having entries close to the unit circle, the above-described extension of Theorem 1 can be shown to apply to “most” functions. We will elaborate on this in the camera-ready version. Thank you for bringing it up!\n\nNotwithstanding the above, we note that proving separation in expressiveness through particular counterexamples is very common. Indeed, various important results in deep learning theory fall under this category (see references in “On the Expressive Power of Deep Learning: A Tensor Analysis” by Cohen et al.).\n\n## Opening of Section 3.3:\nFollowing your comment, this text was completely refactored. In particular, we broke down Section 3.3 to three subsubsections, titled: “Real Parameterizations Suffer from Exponentiality”, “Exponentiality Impedes Practical Learning”, and “Complex Parameterizations Do Not Suffer from Exponentiality”. We believe Section 3.3 is much clearer now. Thank you for the feedback!\n\n## Relation to Orvieto et al.:\nThank you for raising this point! Upon closer inspection, we indeed believe that the result of Orvieto et al. ([25], Section 4.1) can be viewed as a special case of ours. In particular, the task considered in Orvieto et al. — namely, reconstructing past inputs to a real SSM from its current state using a linear mapping — can be viewed as taking an output matrix $C_{\\mathbb{R}}$ with which the input-to-output mapping of a real SSM is a canonical copy (delay) mapping. Our Corollary 1 implies that this necessitates exponential parameter magnitudes, therefore essentially recovers the result of Orvieto et al. We stress that our Theorem 2 is far more general than our Corollary 1 (and accordingly, than the result of Orvieto et al.). Indeed, our Theorem 2 applies (i.e., ensures exponential parameter magnitudes for the real SSM) not only with a copy input-to-output mapping, but with any input-to-output mapping whose impulse response has forward differences that are not especially small (this includes, e.g., random input-to-output mappings — see Corollary 2).\n\nWe will detail the relation between the result of Orvieto et al. and ours in the camera-ready version. Thanks again!\n\n## Empirical demonstration of bounds in Section 3.3:\nFollowing your request, we conducted experiments demonstrating the bounds in Section 3.3. ***The results of these experiments can be found in the PDF attached to our global response***. In a nutshell, the results show that while the complex SSM is able to learn all impulse responses (up to times no greater than its dimension), when the impulse response is such that the real SSM is provably required to have exponential parameter magnitudes, training the real SSM does not converge.\n\n## Further experiments:\nFollowing your feedback, we conducted further experiments, including:\n* Demonstration that complex parameterizations for (non-selective) SSMs improve performance of prominent neural network architectures (S4) on real-world data (sequential CIFAR-10, included in the standard long range arena benchmark).\n* Ablation study showing that among the architectural differences between S6 and S4, the one primarily responsible for closing the gap between real and complex parameterizations for SSMs, is the selectivity of the input and output matrices $B$ and $C$.\n\n***The results of these experiments can be found in the PDF attached to our global response***.\n\n## Success of real parameterizations in selective SSMs:\nWe agree with you that theoretical support for the success of real parameterizations in selective SSMs is an extremely crucial pursuit. As stated in the paper, we believe our results may serve as an important stepping stone in this pursuit. Below we qualitatively discuss the reasoning behind our belief. A more detailed version of this discussion will be added to the paper. Thank you for raising the matter!  \n\nRoughly speaking, the separations we established between real and complex SSMs result from a gap in their ability to express oscillations, i.e., to express frequency components in their impulse response: while the complex SSM can easily express any frequency, the real SSM is required to have exponential dimension or parameter magnitudes. Adding selectivity to the real SSM means that its parameters become input-dependent, leading to what can be viewed as an input-dependent impulse response. It can be shown that this dependence allows “importing” frequency components from the input to the impulse response. Therefore, if the input data is sufficiently rich in terms of its frequency content, selectivity may endow real parameterizations with all the benefits we proved for complex parameterizations.\n\nRecall that, as stated in our introduction, [10] conjectured that complex parameterizations are preferable for continuous data modalities (e.g., audio, video), whereas for discrete data modalities (e.g., text, DNA) real parameterizations suffice. The explanation above aligns with this conjecture: continuous data modalities typically consist of low frequencies only, whereas discrete data modalities have a “whiter spectrum,” i.e. a more uniform mix of frequencies.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9ZMphy0Gzc", "reviewer": "Reviewer_SDv4", "summary": "This work establishes a formal gap between real and complex parameterizations of stable, diagonal SSMs. While complex parameters can trivially express any real SSM, the converse is not true and real SSMs need an arbitrarily large number of parameters to approximate complex SSMs in at least two important cases.", "questions": "See above.", "limitations": "The paper has a thorough discussion of the limitations of the analysis.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. Clear writing and presentation\n2. Theoretical results support a clear practical suggestion: use complex parametrizations for your SSM if you don't have input selectivity.", "weaknesses": "1. Experimental results on non-synthetic datasets would be great. Especially considering the theorems regarding practical learnability and the exponentiality of real parametrizations for random impulse responses with high probability.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support!\n\nWe conducted several additional experiments, including: \n* Demonstration of the gap in practical learnability between real and complex SSMs in the theoretically analyzed setting (i.e., in the setting for which we established such a gap).\n* Demonstration that complex parameterizations for (non-selective) SSMs improve performance of prominent neural network architectures (S4) on real-world data (sequential CIFAR-10, included in the standard long range arena benchmark).\n* Ablation study showing that among the architectural differences between S6 and S4, the one primarily responsible for closing the gap between real and complex parameterizations for SSMs, is the selectivity of the input and output matrices $B$ and $C$.\n\n***The results of these experiments can be found in the PDF attached to our global response***.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "x1K2dWM5AT", "reviewer": "Reviewer_sPCd", "summary": "This paper considers learning LTI systems with bounded response. It shows that if we restrict to SSMs with diagonal dynamics, both real-valued and complex valued state sizes suffice. However, it shows that if we use only real-valued SSMs, to learn a sequence of length t we will need parameters that scale as $\\exp(t)$, while if we use complex-valued SSMs, we need only parameters that scale as $t$.", "questions": "* I think the first sentence of the paper should name check S5 between S4 and Mamba (which is sometimes referred to in the body of its text as S6). S5 helped to pioneer the use of diagonal complex dynamics in an LTI setting, about which this entire paper is based. I think not namechecking it, and instead lopping in onto the end as \"and more\" does a disservice to a reader trying to learn more about the literature.\n* How do the results in this paper serve as an important stepping stone towards understanding real vs complex parameterization in LTV or selective settings?\n* What happens if we use a feedthrough matrix D in (1), which is common in nearly all SSM parameterizations?\n* What is $\\Omega(t)$ on line 187? Is it defined somewhere in the paper?\n* Is it possible to do better than $n_{\\mathbb{C}} = t$? why or why not?", "limitations": "yes", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper did a great job of distinguishing between model expressivity (showing that with large enough state size both real- and complex-valued SSMS are equally expressive) and practical learnability (showing that real- valued SSMs need an impractically large state size). \n\nI also liked how their proof of practical learnability was basically based on the point that for stable real-valued diagonal SSMs, the dynamics pretty have to be decaying exponentials, so we will need exponentially many of them to form a basis for a function. On the other hand, for complex-valued diagonal SSMs, we effectively have a Fourier basis, which is more expressive.\n\nI also like the robust limitations section of the paper, which emphasized that although the paper has demonstrated the need for complex parameterization in the LTI setting, they haven't addressed the selectivity setting, leaving open theoretical contributions to explain why Mamba can get away with using only real parameterization for language tasks. \n\nI also liked the proof technique based on impulse series and impulse response, that was a very nice framing.\n\nThis paper provides an effort grounded in both experiments and theory that attempts to resolve an important question practitioners genuinely care about.", "weaknesses": "The paper would have been more interesting if it had addressed what is going on in the setting of selectivity. On lines 66-7, the authors write \"We believe our results may serve as an important stepping stone in this pursuit.\" It would be nice if more evidence was given. I can't see how the proof techniques carry over. It would be great if some indication could be given of how this paper could be helpful in addressing selectivity.\n\nFootnote 1 is extremely confusing. It basically contradictions lines 101-2, which state that the SSMs considered in the paper are going to be diagonal. So, the eigenvalues of a real-valued diagonal A are definitely always real. I would just remove footnote 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your support, and for highlighting the importance of the question we study and the merit of our theory and experiments! We address your comments and questions below.\n\n## Addressing selectivity:\nWe agree with you that addressing selectivity — i.e., theoretically supporting the success of real parameterizations in selective SSMs — is an interesting pursuit. Below we qualitatively discuss the reasoning behind our belief that “our results may serve as an important stepping stone in this pursuit”. A more detailed version of this discussion will be added to the paper. Thank you for raising the matter!  \n\nRoughly speaking, the separations we established between real and complex SSMs result from a gap in their ability to express oscillations, i.e., to express frequency components in their impulse response: while the complex SSM can easily express any frequency, the real SSM is required to have exponential dimension or parameter magnitudes. Adding selectivity to the real SSM means that its parameters become input-dependent, leading to what can be viewed as an input-dependent impulse response. It can be shown that this dependence allows “importing” frequency components from the input to the impulse response. Therefore, if the input data is sufficiently rich in terms of its frequency content, selectivity may endow real parameterizations with all the benefits we proved for complex parameterizations.\n\nRecall that, as stated in our introduction, [10] conjectured that complex parameterizations are preferable for continuous data modalities (e.g., audio, video), whereas for discrete data modalities (e.g., text, DNA) real parameterizations suffice. The explanation above aligns with this conjecture: continuous data modalities typically consist of low frequencies only, whereas discrete data modalities have a “whiter spectrum,” i.e. a more uniform mix of frequencies. \n\nAs stated, a detailed version of the above discussion will be added to the paper.\n\n## Footnote 1:\nPer your suggestion, we will remove Footnote 1.\n\n## Questions (addressed by order of appearance):\n* We will explicitly mention S5 when listing prominent SSM-based neural network architectures.\n* See “addressing selectivity” section above.\n* Our theory essentially applies as is (more precisely, it applies given very slight modifications in the established bounds) to the case where SSMs include a feedthrough $D$. The reason why incorporation of $D$ does not make a material difference is that it can easily be emulated by: (i) increasing the dimension of the SSM by one; (ii) assigning one to the last diagonal entry of $A$ and the last entry of $B$; and (iii) assigning $D$ to the last entry of $C$. We will mention this in the camera-ready version. Thank you for raising the matter!\n* $\\Omega (\\cdot )$ in line 187 stands for Big-Omega notation, i.e. it signifies a function that is at least linear in its argument. Note that it is used to qualitatively characterize a dependence whose precise form is provided by Theorem 2.\n* In Proposition 3 (and Proposition 1), it is indeed possible to improve (relax) the requirement $n_{\\mathbb{C}} \\geq t$. Namely, by leveraging the fact that the discrete Fourier transform of a real sequence is symmetric, one can update the proof of Proposition 3 to show that $n_{\\mathbb{C}} \\geq \\lceil t / 2 \\rceil$ suffices. Parameter counting arguments imply that the latter requirement is tight. We will mention all of this in the camera-ready version. Thank you for asking about it!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "A3eet4IOWT", "reviewer": "Reviewer_UNm3", "summary": "This paper provides a theoretical analysis of why SSM needs to be parameterized by complex numbers instead of real numbers. It shows that there exist complex LTI systems that could not be well-approximated by real systems of comparable size. Moreover, it proves that certain dynamics cannot be approximated by real LTI systems unless it has an exponentially large state-space dimension or large system matrices; yet, using complex LTI systems resolves this issue.", "questions": "1. You formulate the problem using the discrete LTI system. Of course, in SSMs, the parameters are from the continuous-time LTI systems. While this does not change the basic question you are exploring because the real axis in the left half-plane gets mapped to the real axis in the unit disk under virtually all discretization schemes, would Theorem 2 be changed if you take the discretization into account?\n2. The paper studies two cases: $\\mathbf{A}$, $\\mathbf{B}$, and $\\mathbf{C}$ are either all restricted to real or all allowed to be complex. Intuitively, however, the important thing is that $\\mathbf{A}$ has to be complex. Have you looked into the case where $\\mathbf{A}$ is complex and $\\mathbf{B}$ and $\\mathbf{C}$ are real? In that case, which world would it fall into?\n3. In section 3.3, instead of giving two examples of dynamics that are poorly approximated by real systems, maybe there could be a discussion of what you called forward difference. It would be helpful to relate Theorem 2 to some general (and easily interpretable) properties of the dynamics.", "limitations": "None.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The theoretical statements are precisely made. The sketch of the proofs are helpful for understanding the paper.\n2. The comparison between real and complex is fairly thorough, encompassing different perspectives.", "weaknesses": "1. My main concern is about the contribution of this work. While it is true that many ML models use real parameterizations, the diagonal matrix $\\mathbf{A}$ comes from diagonalizing a general state matrix. Therefore, unless one puts restrictions on the matrix to be diagonalized (e.g. Hermitian), it is natural to assume that $\\mathbf{A}$ should be complex-valued. Showing why a real parameterization does not work well sounds like a slightly artificial problem and adds relatively little to the SSM community.\n2. The experiments could not strongly corroborate the theory. In addition to showing the performance, maybe some synthetic experiments would be helpful to show the exponential gap in Theorem 2 and Proposition 3.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review, and for highlighting the thoroughness and preciseness of our theory. We address your comments and questions below. If you find our responses satisfactory, we would greatly appreciate it if you would consider raising your score.\n\n## Significance of real diagonal SSMs:\nReal diagonal SSMs (with and without selectivity) underlie some of the most prominent neural network architectures for long sequence processing. This includes the recent Mamba architecture and its variants, as well as other architectures [A, B, C, D, E]. Advantages of real diagonal SSMs include simplicity and speed. The extent to which they compare to complex diagonal SSMs in terms of accuracy has been the subject of much debate (see our introduction). This debate is what motivated our work.\n\nWe hope the above addresses your concern regarding the significance of our contribution. If not, please let us know and we will gladly elaborate.\n\n--\n\n**[A]** “Mamba: Linear-time sequence modeling with selective state spaces”, Gu and Dao, 2023\n\n**[B]** “Mega: Moving Average Equipped Gated Attention”, Ma et al., 2023\n\n**[C]** “Transformers are SSMs: Generalized Models and Efficient Algorithms Through Structured State Space Duality”, Dao and Gu, 2024\n\n**[D]** “Megalodon: Efficient LLM Pretraining and Inference with Unlimited Context Length”, Ma et al., 2024\n\n**[E]** “Jamba: A Hybrid Transformer-mamba language model”, Lieber et al., 2024\n\n## Experimentation:\nFollowing your comment, we conducted several experiments, including: \n* Demonstration of the gap in practical learnability between real and complex SSMs in the theoretically analyzed setting (i.e., in the setting for which we established such a gap).\n* Demonstration that complex parameterizations for (non-selective) SSMs improve performance of prominent neural network architectures (S4) on real-world data (sequential CIFAR-10, included in the standard long range arena benchmark).\n* Ablation study showing that among the architectural differences between S6 and S4, the one primarily responsible for closing the gap between real and complex parameterizations for SSMs, is the selectivity of the input and output matrices $B$ and $C$.\n\n***The results of these experiments can be found in the PDF attached to our global response***.\n\n## Impact of discretization:\nOur theory essentially applies as is (more precisely, it applies given slight modifications in the established bounds) to cases where the SSMs include conventional discretizations. For example, with the discretization laid out in the original Mamba paper [10]: the state transition matrix $A$ is represented as the exponent of a parameter matrix $A’$ times a scalar $\\Delta$; and the input matrix $B$ is represented as a parameter matrix $B’$ times $\\Delta$ times some matrix with spectral norm no greater than one. All of our proofs readily adapt to this case (in particular, the proofs of Theorem 2, Corollary 1 and Corollary 2 readily adapt to establishing an exponential lower bound on the magnitudes of $( B’ , C )$ for the real SSM).\n\nWe will add a discussion of discretization to the camera-ready version. Thank you very much for raising the matter!\n\n## Complex $A$ with real $B$ and $C$:\nYour intuition is correct. Namely, all benefits we have proven for the complex SSM apply (given a slight modification in one of the established bounds) when the input matrix $B$ and the output matrix $C$ are constrained to be real. To see this, note that our proofs of Propositions 1, Proposition 2 and Theorem 1 do not make use of complex assignments for $B$ and $C$. Our proof of Proposition 3 does make use of such assignments, but can readily avoid them by replacing the discrete Fourier transform with the discrete cosine transform (in this case a factor of $\\sqrt{2}$ is introduced in the second bound). We will mention this in the camera-ready version. Thank you for the question!\n\n## Mappings poorly approximated by the real SSM:\nWhile Corollary 1 indeed provides an example (albeit a canonical one) of a mapping poorly approximated by the real SSM, Corollary 2 goes far beyond an example, in the sense that it applies to a random (generic) mapping. Nonetheless, we agree with you that it would be interesting to relate the condition brought forth by Theorem 2 — namely, forward differences not being especially small — to easily interpretable properties of the mappings. We invested considerable efforts trying to establish such a relation (primarily using tools from complex analysis, e.g. Rice’s method), but to no avail. We will mention this pursuit as a direction for future work in the camera-ready version. Thank you for raising the matter!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their time and feedback, addressed per reviewer in our individual responses.

***Attached to this comment is a PDF presenting results of new experiments*** which will be added to the paper. These experiments include:
* Demonstration of the gap in practical learnability between real and complex SSMs in the theoretically analyzed setting (i.e., in the setting for which we established such a gap).
* Demonstration that complex parameterizations for (non-selective) SSMs improve performance of prominent neural network architectures (S4) on real-world data (sequential CIFAR-10, included in the standard long range arena benchmark).
* Ablation study showing that among the architectural differences between S6 and S4, the one primarily responsible for closing the gap between real and complex parameterizations for SSMs, is the selectivity of the input and output matrices $B$ and $C$.

Meta-review: This paper investigates whether complex diagonal State Space Models (SSMs) have an advantage over real diagonal SSMs. It demonstrates that complex parameterization in SSMs is important because certain dynamics cannot be well-approximated by real-valued models without requiring a large state space or large system matrices. Furthermore, the paper shows that complex SSMs need significantly fewer parameters to learn specific systems compared to real SSMs, particularly for long sequences. 

As reviewer UNm3 noted, the question being addressed may seem somewhat unnatural at first, since diagonalization of a general state matrix already results in a diagonal matrix with complex entries. It seems intuitive that restricting the system to real values would hurt performance --- not only due to reduced parameter count but also because the dynamics that can be modeled by a real-valued diagonal matrix are quite limited. Complex values are essential for capturing oscillatory behavior, and reducing these values toward zero implies heavy damping of the system. Thus, the paper's findings are rather intuitive and may not surprise those familiar with dynamical systems theory. Similarly, reviewer 9K2D points out that "the theoretical results might not be super surprising for readers who already worked on the theory of RNNs." Indeed, similar questions have been widely studied in the past.

Nevertheless, the authors make a valid point that there is an ongoing debate, likely driven by engineering perspectives, on the practical advantages of complex versus real parameterizations in SSMs. In this regard, the paper contributes insights that could help steer this discussion.

Overall, the reviewers are positive, acknowledging both the strengths and weaknesses of the work. While I agree that the paper provides interesting insights, I find the findings and experiments somewhat limited, and I do not believe the paper will have a significant impact in its current form. However, it could be much stronger if the authors address the reviewers' comments in the camera-ready version. Nevertheless, I suggest accepting this paper.
Decision: Accept (poster)