Provable Benefits of Complex Parameterizations for Structured State Space Models

Authors: yuval  ran-milo
eden  lumbroso
edo  cohen-karlik
raja  giryes
amir  globerson
i  ii
nadav  cohen
yuval  milo
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 16:26:52

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.

Main paper: 
 introduction: 
 Structured state space models (SSMs) are the core engine behind prominent neural network architectures such as S4 [21] , Mamba [20] , LRU [41] , Mega [37] , S5 [50] and more [23, 31, 38, 34] . In their typical form, SSMs can be thought of as single-input single-output linear dynamical systems, wherein the state transition matrix has a specified structure, most notably diagonal [22, 23, 41, 50, 37, 20] . A salient characteristic of SSMs is that their parameterizations are often complex (take values in C), in contrast to typical neural network modules whose parameterizations are conventionally real (take values in R).There has been mixed evidence regarding benefits of complex parameterizations over real parameterizations for SSMs. Some prior works have demonstrated that complex parameterizations are 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 [37, 20] . It was conjectured [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 an open question.In this paper, we take a step towards theoretically addressing the foregoing question. Specifically, we provide two theoretical contributions establishing provable benefits of complex parameterizations constrained to be diagonal); B ∈ K n,1 , an input matrix; and C ∈ K 1,n , an output matrix. 23 Given the values of A, B and C, the SSM realizes a mapping ϕ n,(A,B,C) : R N → R N which receives as input a real scalar series (u(t)) t∈N , and produces as output a real scalar series (y(t)) t∈N defined through the following recursive formula:x(t) = Ax(t -1) + Bu(t) , y(t) = ℜ Cx(t) , t ∈ N , (1) where (x(t) ∈ K n ) t∈N is a vector series of states, and x(0) = 0 ∈ K n . If K = R we say that the SSM is real, and if K = C we say that it is complex. 4 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 C ⊤ as vectors.Perhaps the most prominent form of structure imposed on SSMs is stable diagonality, i.e. stability combined with diagonality [22, 23, 41, 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. 
linear time-invariant mappings: 
 Let ϕ : R N → R N be a mapping from the space of (infinite) real scalar series to itself. We say that ϕ(•) is linear if for all α ∈ R and S, S ∈ R N it holds that ϕ(αS + S) = αϕ(S) + ϕ( S). For every k ∈ N, define the k step delay δ k : R N → R N to be the operator that adds k preceding zeros to the series it receives as input. 5 We say that the mapping ϕ(•) is linear time-invariant (LTI) if it is linear, and it commutes with δ k (•) (meaning ϕ(δ k (•)) = δ k (ϕ(•))) for every k ∈ N. It is well known [40] that if ϕ(•) is LTI then it is given by ϕ(S) = S * ϕ(I), where I := (1, 0, 0, . . .) ∈ R N is the impulse series, and ϕ(I) is referred to as the impulse response of ϕ(•). Conversely, for any R ∈ R N , the mapping defined by S → S * R is LTI, and its impulse response is R.We will identify LTI mappings with their impulse responses. More specifically, for any k ∈ 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 ϕ(•), φ(•) and any ϵ ∈ R ≥0 , we say that φ(•) ϵ-approximates ϕ(•) up to time k if ∥ϕ(I) :k -φ(I) :k ∥ 1 ≤ ϵ. If the latter inequality holds with ϵ = 0, we also say that φ(•) matches ϕ(•) up to time k.Let (A, B, C) be an SSM of dimension n ∈ N, realizing the mapping ϕ n,(A,B,C) : R N → R N (see Section 2.2). It is straightforward to see that ϕ n,(A,B,C) (•) is LTI, and that its impulse response is given by: ϕ n,(A,B,C) (I) = ℜ(CB), ℜ(CAB), ℜ(CA 2 B), . . . .For real and complex settings (i.e. for K = R and K = C), we will study the extent to which varying (A, B, C) as well as n, can lead ϕ n,(A,B,C) (•) to ϵ-approximate different LTI mappings up to different times. 
theoretical analysis: 
 Throughout this section, we consider a real SSM (A R , B R , C R ) of dimension n R realizing the mapping ϕ n R ,(A R ,B R ,C R ) (•), and a complex SSM (A C , B C , C C ) of dimension n C realizing the mappingϕ n C ,(A C ,B C ,C C ) (•) (see Section 2.2). 2 Various SSMs include discretization [20, 21, 23, 16] , which amounts to replacing parameter matrices by certain transformations that depend on an additional parameter ∆ ∈ R>0 (e.g., replacing A by (I -∆/2 • A) -1 (I + ∆/2 • A) [23, 22] ). With slight modifications, our main theoretical results apply to SSMs with common discretizations-see Appendix A.1 for details. 3 Some SSMs include an additional feedthrough parameter D ∈ K 1,1 [41] . With feedthrough, the expression for y(t) in Equation (1) becomes ℜ(Cx(t) + Du(t)). Our theory essentially applies as is to SSMs with feedthrough-see Appendix A.2 for details. 4 It is possible to consider a hybrid setting where A is allowed to be complex while B and C are restricted to be real. This setting enjoys all provable benefits of the complex setting (K = C)-see Appendix A.3 for details. 5 That is, for any S = (s(t)) t∈N ∈ R N , δ k (S) ∈ R N is the series whose mth element, for m ∈ N, equals s(m -k) if m > k and 0 otherwise.It is known (see, e.g., [14] ) that the real SSM is universal, in the sense that it can precisely express any LTI mapping up to any time t when its dimension is equal to or greater than t. Trivially, this implies the same for the complex SSM. Proposition 1 below formalizes these facts for completeness. Proposition 1. Let ϕ : R N → R N be an arbitrary LTI mapping, and let t ∈ N. Then, the following holds for both K = R and K = C. If n K ≥ t, there exist assignments for (A K , B K , C K ) with which ϕ n K ,(A K ,B K ,C K ) (•) matches ϕ(•) up to time t. 6Proof sketch (proof in Appendix D.1). Beginning with the real SSM (K = R), the proof shows thatϕ n R ,(A R ,B R ,C R ) (•) matches ϕ(•) up to time t if V (A R )(C ⊤ R ⊙ B R ) = ϕ(I) :t , where V (A R) is a Vandermonde matrix that has full rank when the diagonal entries of A R are distinct. Assigning A R this way, there must exist v ∈ R n R with which V (A R )v = ϕ(I) :t . Assigning B R = v and C ⊤ R = 1 concludes the proof for the real SSM. The complex SSM (K = C) can be treated analogously.Proposition 2 and Theorem 1 below together establish that although both the real and complex SSMs are universal (see Section 3.1), there is a strong separation between the two in terms of expressiveness. Proposition 2 formalizes an obvious fact: all mappings expressible by the real SSM can be precisely expressed (up to any time) by the complex SSM whenever n C ≥ n R (i.e., whenever the dimension of the complex SSM is equal to or greater than the dimension of the real SSM). Theorem 1 proves a much less obvious result: for any n C , 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 t by the real SSM unless n R is on the order of t, which may be arbitrarily larger than n C . Proposition 2. Consider an arbitrary assignment for (A R , B R , C R ), and assume that n C ≥ n R . Then, there exist assignments for(A C , B C , C C ) with which ϕ n C ,(A C ,B C ,C C ) (•) = ϕ n R ,(A R ,B R ,C R ) (•).Proof. It suffices to prove the sought after result for n C = n R , since one can effectively reduce the dimension of the complex SSM by zeroing out entries of B C (or C C ). Assuming that n C = n R , we may assign to(A C , B C , C C ) the values of (A R , B R , C R ). Under this assignment ϕ n C ,(A C ,B C ,C C ) (•) = ϕ n R ,(A R ,B R ,C R ) (•), as required.Theorem 1. Let t ∈ N and ϵ ∈ R ≥0 . Assume without loss of generality that n C = 1,7 in which case A C , B C and C C can be regarded as scalars. Suppose |sin(arg(A C ))| ≥ 0.2, |A C | ≥ 0.5 1/t and |B C • C C | ≥ 1. Then, if ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ n C ,(A C ,B C ,C C ) (•) up to time t, it must be that n R ≥ ⌊t/9⌋ -1 -4ϵ.Proof sketch (proof in Appendix D.2). The idea behind the proof is as follows. The complex SSM realizes an oscillatory mapping, in the sense that elements 1, 3, . . . , 2⌈t/2⌉-1 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⌉ -1 of the impulse response it gives rise to are a linear combination of decaying exponentials, and therefore can change sign at most O(n R ) times. Combining these two observations leads to the desired result.Let ϕ : R N → R N be an LTI mapping with bounded impulse response, which we would like to ϵ-approximate up to time t for some ϵ ∈ R ≥0 and t ∈ N. Assume that the dimensions of the real and complex SSMs are greater than or equal to t. By Proposition 1, both the real and complex 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. Section 3.3.1 proves that under a mild condition on ϕ(•), in order for the real SSM to achieve the desired approximation, either its dimension or the magnitude of its parameters must be 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.Definition 1 below formalizes the notion of forward difference for a real scalar series-a discrete analogue of derivative for a differentiable real function. Our main theoretical result, Theorem 2, then establishes that if forward differences associated with ϕ(I)-the impulse response of ϕ(•)-satisfy a certain condition, then in order for the real SSM to express a mapping that ϵ-approximates ϕ(•) up to time t, either the dimension of the real SSM n R or the magnitude of its parameters (B R , C R ) must be exponential in t. Roughly speaking, the aforementioned condition on forward differences associated with ϕ(I) is that there exists some d ∈ Θ(t) such that the dth forward difference of the restriction of ϕ(I) to either odd or even elements has magnitude greater than 2 d ϵ. 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 a real scalar series of length k ∈ N ∪ {∞}. The forward difference of S, denoted S (1) , is the scalar series of length k -1 whose mth element, for m ∈ [k -1], is given by S m+1 -S m . For d ∈ {2, 3, . . . , k -1}, the dth forward difference of S, denoted S (d) , is recursively defined to be the forward difference of S (d-1) . Proof sketch (proof in Appendix D.3). The idea behind the proof is as follows. The restrictions of the impulse response ofEQUATIONϕ n R ,(A R ,B R ,C R ) (•) to odd and even elements-i.e., ϕ n R ,(A R ,B R ,C R ) (I)| odd and ϕ n R ,(A R ,B R ,C R ) (I)| even ,respectively-are each a linear combination of n R decaying exponentials, where the coefficients of the linear combination have absolute value no greater than ∥C R ⊤ ⊙ B R ∥ ∞ . Forward differences of decaying exponentials are exponentially small. Therefore, by linearity of forward differences, requiringϕ n R ,(A R ,B R ,C R ) (I)| odd or ϕ n R ,(A R ,B R ,C R ) (I)| even to have a forward difference that is not exponentially small implies an exponentially large lower bound onn R ∥C R ⊤ ⊙ B R ∥ ∞ . When ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ(•) up to time t, forward differences of ϕ n R ,(A R ,B R ,C R ) (I)| odd and ϕ n R ,(A R ,B R ,C R ) (I)| evenare close to those of ϕ(I)| odd and ϕ(I)| even , respectively. We thus conclude that if ϕ(I)| odd or ϕ(I)| even has a forward difference that is not especially small, then n R ∥C R ⊤ ⊙ B R ∥ ∞ must be exponentially large. This conclusion is formalized via Equation (3), the sought after result. Special cases. Theorem 2 implies that the real SSM suffers from exponentiality (namely, its dimension n R or the magnitude of its parameters (B R , C R ) must be exponential in t in order for it to express a mapping that ϵ-approximates ϕ(•) up to time t) in various important cases. Indeed, Corollaries 1 and 2 below respectively show that the real SSM suffers from exponentiality when ϕ(•) is a canonical copy (delay) mapping, and with high probability when ϕ(•) is a random (generic) mapping. In light of Theorem 1 (namely, of the inability of the real SSM to compactly approximate various oscillatory mappings expressible by the complex SSM), it is natural to ask if the real SSM suffers from exponentiality in cases where ϕ(•) is oscillatory, i.e. where its impulse response oscillates. Corollary 3 below shows that exponentiality indeed transpires in a case where ϕ(•) is a basic oscillatory mapping. On the other hand, there are simple cases where ϕ(•) is oscillatory yet exponentiality does not take place, e.g. the case where the impulse response of ϕ(•) is (+1, -1, +1, -1, . . .). 8 Precise delineation of the type of oscillations that lead to exponentiality is deferred to future work (see Section 6).Corollary 1. Suppose t ≥ 9 and ϕ(•) = δ ⌊(t-1)/2⌋ (•), where as defined in Section 2.3, δ ⌊(t-1)/2⌋ (•) is the ⌊(t -1)/2⌋ step delay mapping. Assume also that ϵEQUATIONProof sketch (proof in Appendix D.4). The proof computes forward differences associated with δ ⌊(t-1)/2⌋ (I) (impulse response of δ ⌊(t-1)/2⌋ (•)), and plugs them into Theorem 2 (Equation (3)).Corollary 2. Let α ∈ R >0 , and let R ∈ R N be generated by a random process where each element of R is independently drawn from a uniform distribution over the interval [-α, α]. Suppose that t ≥ 8 and that ϕ(•) is the mapping whose impulse response is R (i.e., ϕ(•) is defined by ϕ(S) = S * R). Let p ∈ (0, 1), and assume that ϵ ≤ α p/t. Then, with probability at leastEQUATION)Proof sketch (proof in Appendix D.5). The proof derives lower bounds (holding with probability at least 1-p) on forward differences associated with R, and plugs them into Theorem 2 (Equation ( 3)).Corollary 3. Suppose that ϕ(I) = (+1 , 0 , -1 , 0 , +1 , 0 , -1 , 0 , . . .) and ϵ ≤ 0.5. Then, ifEQUATIONProof sketch (proof in Appendix D.6). The proof computes forward differences associated with the series (+1 , 0 , -1 , 0 , +1 , 0 , -1 , 0 , . . .), and plugs them into Theorem 2 (Equation (3)).For any value of t that is not especially small, exponentiality in t for the real SSM as put forth in Section 3.3.1-i.e., exponentiality in t of the dimension of the real SSM n R or the magnitude of its parameters (B R , C R )-impedes practical learning. This impediment is obvious in the case where n R is exponential in t (in this case, it is impractical to even store the parameters of the real SSM, let alone learn them). Appendix B treats the complementary case, i.e. it shows that learning is impractical when the required values for the parameters (B R , C R ) are exponential in t (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 ϵ-approximates ϕ(•) up to time t under important choices of ϕ(•).  
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 1). 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 at https://github.com/edenlum/ SSMComplexParamBenefits.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 ϕ(•): the canonical copy (delay) mapping from Corollary 1; the random (generic) mapping from Corollary 2; and the basic oscillatory mapping from Corollary 3. Throughout, the dimension of the real or complex SSM (n R or n C , respectively) was set to at least t, which, by universality (Section 3.1), implies that the SSM can express a mapping that precisely matches ϕ(•) up to time t. Our theory (Section 3.3) establishes that despite this parity between the real and complex SSMs in terms of expressiveness, there is 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 ϕ(•) up to time t. Tables 1 and 2 present results obtained with the real and complex SSMs, respectively. They confirm the predictions of our theory.Table 1 : In accordance with our theory, the analyzed real SSM (see Section 2.2) cannot practically learn to closely approximate ϕ(•) up to time t under important choices of ϕ(•), even when t is moderate. This table reports the approximation error attained by the real SSM, i.e. the minimum ϵ with which a mapping learned by the real SSM ϵ-approximates ϕ(•) up to time t (see Section 2.3), when t = 32 and ϕ(•) varies over the following possibilities: the canonical copy (delay) mapping from Corollary 1; the random (generic) mapping from Corollary 2; and the basic oscillatory mapping from Corollary 3. Learning was implemented by applying one of three possible gradient-based optimizers-Adam [29] , AdamW [36] or RAdam [33] -to a loss as in our theory (see Appendix C). For each choice of ϕ(•), 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 (n R ) was set to 1024; other choices of dimension led to qualitatively identical results. For further implementation details see Appendix F. 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 CIFAR-10 dataset from the widely recognized Long Range Arena benchmark [52] . Our implementation is based on the official S4 repository, 10 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 F.2 for details. The overarching conclusion from our theory-namely, that SSMs benefit from complex parameterizations-thus extends to this real-world setting.A new architectural feature for SSMs that yields state of the art performance is selectivity [20, 31, 4, 57] . In its original form-proposed as part of the Mamba neural network architecture [20] selectivity amounts to replacing the parameters B and C (see Section 2.2), as well as an additional discretization parameter ∆ ∈ R >0 , 2 by certain functions of the input (u(t)) t∈N . We empirically study the impact of complex parameterizations on SSMs with selectivity by evaluating a 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 4.1) 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. 11Unless 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 F.3.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 [22, 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 an ablation experiment with partial versions of selectivity (i.e., where not all of the parameters B, C and ∆ were replaced by functions of the input). The results of this experiment, reported in Table 3 , reveal that when selectivity is fully or partially removed (more precisely, when [20] on a synthetic induction-head task regarded as canonical in the SSM literature [27, 20] . Evaluation included multiple configurations for the SSMs underlying the neural network. Each configuration corresponds to either real or complex parameterization, and to a specific partial version of selectivity-i.e., to a specific combination of parameters that are selective (replaced by functions of the input), where the parameters that may be selective are: the input matrix B; the output matrix C; and a discretization parameter ∆. For each 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) to the complex parameterization, whereas otherwise, the complex parameterization is superior. For further implementation details see Appendix F. B, C or both are 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 as well as complex parameterizations for SSMs on 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 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. 
related work: 
 SSMs are closely related to linear dynamical systems-a classic object of study in areas such as systems theory [3] and control theory [51] . Although there exists extensive literature concerning properties of real and complex linear dynamical systems [10, 5, 6, 9] , this literature does not readily establish benefits of complex parameterizations for SSMs, primarily due to the following reasons: (i) the output of 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 on linear dynamical systems.SSMs can be viewed as a special case of recurrent neural networks [48] , which received significant theoretical attention [46, 39, 25, 11, 53] . In this context, several works focused specifically on SSMs [42, 30, 24, 2, 28, 58, 12, 32, 55] . However, to our knowledge, the only prior work to formally and explicitly treat benefits of complex parameterizations for SSMs is [42] . The treatment of [42] (see Section 4.1 therein) can be viewed as a special case of ours. Indeed, [42] considered a task that, using our notation (see Section 2.2), amounts to linearly reconstructing an input element u(t) from the state x(t ′ ) of an SSM, where t, t ′ ∈ N, t ′ ≥ 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 a 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 1 and Proposition 3. We stress that our theory goes far beyond this result, for example in that it covers various mappings beyond copy, including a random (generic) mapping-see Section 3.3 for details.With regards to related empirical work, the literature includes several experimental comparisons between real and complex parameterizations for SSMs [20, 22, 42] . Nonetheless, to our knowledge, the controlled experiments we conducted (see Section 4) are reported herein for the first time. 
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.1 and 3.3.2), and that complex parameterizations do not suffer from exponentiality (Section 3.3.3), we do not formally establish practical learnability with complex parameterizationsour evidence for this is purely empirical (Section 4). 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 4) 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 1 to 3), these cases are likely far from being exhaustive. Indeed, Theorem 2 provides a mild sufficient condition for separation in terms of practical learnability-namely, that certain forward differences are not especially small-and we believe it is possible to apply analytical tools (e.g., the Nørlund-Rice integral [17] ) 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. 
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 parameterizations 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 a 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, we 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 is exponentially large. Experiments corroborated our theory, and suggested that selectivity-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 a potential extension of our theory that accounts for selectivity. Roughly speaking, the separations we established between real and complex SSMs arise from a gap in their ability to express oscillations, i.e., to express frequency components in their impulse response: while a 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 as an input-dependent impulse response. We hypothesize that this dependence allows importing frequency components from the input to 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, thereby fully delineating the benefits of complex parameterizations for SSMs.A.1 DiscretizationVarious SSMs incorporate discretization [20, 21, 23, 16] , which involves replacing parameter matrices with specific transformations that depend on an additional parameter ∆ ∈ R >0 . With slight modifications, our main theoretical results, Theorem 1 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.One of the most common discretizations is the bilinear discretization [21, 22] , in which an SSM( Ď A K , Ď B K , Ď C K )is parameterized in the following way:Ď A K = (I -∆/2 • A K ) -1 (I + ∆/2 • A K ) , Ď B K = (I -∆/2 • A K ) -1 ∆B K , Ď C K = C K ,where ∆ ∈ R >0 , the matrices A K , B K and C K share the same dimensions and are defined over the same fields as Ď A K , Ď B K and Ď C K , respectively, and the real parts of the diagonal entries of A K are negative. Since the set of functions expressible by a real or complex SSM remains unchanged under this discretization, Theorem 1 holds without modification. Furthermore, Theorem 2 applies to this discretization if the left-hand side of Equation ( 3) is replaced by n R ∆∥C R ⊤ ⊙ B R ∥ ∞ . This follows directly from Lemma 13, which shows that for any i ∈[n R ], we have |∆ (B R ) i | ≥ | Ď B R i |.The latter inequality justifies replacing Ď B R with ∆B R on the left-hand side of Equation ( 3), leading to the desired result.Some SSMs include an additional feedthrough parameter D ∈ K 1,1 [41] . With feedthrough, the expression for y(t) in Equation (1) becomes ℜ(Cx(t) + Du(t)). Our theory essentially applies as is to SSMs with feedthrough, as explained below.Obviously, an SSM of dimension n without a feedthrough parameter can be emulated by an SSM of dimension n with a feedthrough parameter D by setting D = 0. Conversely, an SSM (A, B, C) of dimension n with a 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 C followed by D. For any result where an SSM without feedthrough is assumed, a corresponding result for an SSM with feedthrough holds. Such a result can be attained by either emulating an SSM with feedthrough by an SSM without (while increasing dimension from n to n + 1) or by emulating an SSM without feedthrough by an SSM with feedthrough, (while maintaining the dimension) depending on the context.It is possible to consider hybrid SSMs where A is allowed to be complex while B 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 1, Proposition 2, Theorem 1 and Proposition 3. The first three results can be trivially extended to the setting where only A 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 3 utilizes the fact that for a complex SSM (A C , B C , C C ) of dimension n C , the impulse response can be any linear combination of n C arbitrary decaying sine and cosine waves, which, by Fourier theory, can approximate any sequence of length n C . If only A C is allowed to be complex, the impulse response can consist of any linear combination of n C arbitrary decaying cosine waves, which can still represent any sequence of length n C via the discrete cosine transform. Thus, the setting remains fundamentally similar, allowing for the extension of Proposition 3 to hybrid SSMs.In this appendix, we show that learning the parameters of the real SSM, i.e. (A R , B R , C R ), is impractical when the required values for (B R , C R ) are exponential in t. We account for two aspects of this impracticality: the number of iterations required by gradient descent; and the precision (number 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 B R and C R ). 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 a mapping ϕ n R ,(A R ,B R ,C R ) (•) that ϵ-approximates ϕ(•) up to time t, is implemented via gradient descent over a loss function ℓ(•) that measures the squared error of the output at time t, where input elements are drawn independently from the standard normal distribution:EQUATION)By a simple derivation (see Appendix C)ℓ(A R , B R , C R ) = ∥ϕ n R ,(A R ,B R ,C R ) (I) :t -ϕ(I) :t ∥ 2 2, therefore sufficient minimization of the loss ℓ(•) (namely, minimization of ℓ(•) to or below the value ϵ 2 /t) indeed guarantees that ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ(•) up to time t. Assume the following regularity conditions on gradient descent: (i) the step sizes (learning rates) for all iterations are upper bounded by a constant (independent of t); (ii) the step size for each iteration is stable, in the sense that it is upper bounded by 2/λ max , where λ max represents the maximum eigenvalue of the Hessian of ℓ(•) at the respective iteration [13, 7, 15] ; and (iii) the values of ℓ(•) throughout all iterations are upper bounded by a constant (independent of t) times the value of ℓ(•) at initialization. Proposition 4 below establishes that under said regularity conditions, during gradient descent, the magnitude of the parameters (B R , C R ) grows at most linearly in the number of iterations. Accordingly, if the required values for (B R , C R ) are exponential in t and the initialization of (B R , C R ) is not, attaining the required values necessitates an exponential (in t) number of iterations. Proposition 4. Consider an application of gradient descent to the loss ℓ(•) in Equation (7):EQUATIONR is a chosen initialization, and η (i) ∈ R >0 represents the step size selected for iteration i ∈ N. Assume ∃c 1 ∈ R >0 such that ∀i ∈ N : η (i) ≤ c 1 . Assume also:∀i ∈ N : η (i) ≤ 2 max λ max ∇ 2 ℓ A (i-1) R , B (i-1) R , C (i-1) R , 0 ,where λ max (M ), for a symmetric matrix M , is the maximum eigenvalue of M . Finally, assume:EQUATIONR , C (0) R 0.5 .Proof sketch (proof in Appendix D.8). Taking into account the form of ℓ(•) (see Appendix C) and the assumptions made, the proof shows that at each iteration of gradient descent, each entry in B R or C R changes by at most (4cEQUATIONEQUATIONR )) 0.5 . This readily leads to the desired result. , where ξ ∈ R >0 is the quantization step size [56] . With the floating-point representation of ρ, the best (lowest) achievable quantization step size is on the order of |ρ| • 2 -b k , thus we may model quantization error as a multiplicative random variable uniformly distributed over [1 -q/2, 1 + q/2], where q = Θ(2 -b k ). Definition 2 below employs this model to formalize the notion of robustness to quantization for values of(A R , B R , C R ) with which ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ(•)up to time t. Specifically, Definition 2 defines robustness to q-quantization for such values to be the probability thatϕ n R ,(A R ,B R ,C R ) (•) continuesto ϵ-approximate ϕ(•) up to time t, when the values are multiplied by random variables uniformly distributed over [1 -q/2, 1 + q/2]. Proposition 5 below then proves that robustness to q-quantization is (at most) inversely proportional to q times the magnitude of (B R , C R ). Recalling that q = Θ(2 -b k ), we conclude that if the values of (B R , C R ) are exponential in t, a non-negligible robustness to quantization necessitates having b k = Ω(t), meaning a 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 [1, 43] ), all much smaller than what the time t can be (tens of thousands or more [20, 47, 19, 8] )Definition 2. Let q ∈ [0, 1], and let Q A R , Q B R and Q C Rbe random matrices of the same sizes as A R , B R and C R , respectively, wherein each entry is independently drawn from the uniform distribution over [1 -q/2,1 + q/2]. Let (A * R , B * R , C * R ) be values for (A R , B R , C R ) with which ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ(•) up to time t. The robustness to q-quantization of (A * R , B * R , C * R ) is the probability that ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ(•) up to time t when (A R , B R , C R ) take the values (A * R ⊙ Q A R , B * R ⊙ Q B R , C * R ⊙ Q C R ). Proposition 5. Suppose that ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ(•) up to time t.Then, for any q ∈ [0, 1], the robustness to q-quantization of the values held by(A R , B R , C R ) is at most: 2ϵ q∥C ⊤ R ⊙ B R ∥ ∞ .Proof sketch (proof in Appendix D.9). Denote by(A * R , B * R , C * R ) the values held by (A R , B R , C R ), and let Q A R , Q B R and Q C R be random matrices as in Definition 2. When (A R , B R , C R ) take the values (A * R ⊙Q A R , B * R ⊙Q B R , C * R ⊙Q C R ), the first entry of the impulse response of ϕ n R ,(A R ,B R ,C R ) (•) equals (C * R ⊙ Q C R )(B * R ⊙ Q B R ).It suffices to restrict attention to this first entry, and show that|(C * R ⊙ Q C R )(B * R ⊙ Q B R ) -ϕ(I) 1 | ≤ ϵ with probability at most 2ϵ/(q∥C ⊤ R ⊙ B R ∥ ∞ ).The proof establishes the latter anti-concentration result.Consider a loss function as in our theory (see Equation ( 7)), applied to both real and complex SSMs:ℓ(A K , B K , C K ) = E U∈R N , U1,U2,... i.i.d.∼ N (0,1)ϕ n K ,(A K ,B K ,C K ) (U) t -ϕ(U) t 2 ,where K = R or K = C. Below we prove that:ℓ(A K , B K , C K ) = ϕ n K ,(A K ,B K ,C K ) (I) :t -ϕ(I) :t 2 2 .Indeed, as discussed in Section 2.3, for any U ∈ R N :ϕ n K ,(A K ,B K ,C K ) (U) t = U * ϕ n K ,(A K ,B K ,C K ) (I) t , ϕ(U) t = (U * ϕ(I)) t .Thus:ϕ n K ,(A K ,B K ,C K ) (U) t -ϕ(U) t = t j=1 U j ϕ n K ,(A K ,B K ,C K ) (I) t-j+1 -ϕ(I) t-j+1 .It holds that:EQUATION2 , as required.Beginning with the real SSM (K = R), assume that n R ≥ t. We would like to show that there exist assignments for (A R , B R , C R ) with which:ϕ(I) :t = (C R B R , C R A R B R , C R A 2 R B R , . . . , C R A t-1 R B R ), where ϕ(I) :t stands for the first t elements of the impulse response of ϕ(•). Regarding ϕ(I) :t , B R and C ⊤ R as (column) vectors, we may write the sought after equality asV (A R )(C ⊤ R ⊙ B R ) = ϕ(I) :t , where V (A R ) ∈ R t,n Ris a matrix whose (i, j)th entry holds the jth diagonal entry of A R exponentiated by i -1. Notice that V (A R ) is a Vandermonde matrix comprising powers of the diagonal entries of A R . Any assignment for A R with distinct diagonal entries leads the Vandermonde matrix to have full rank, which in turn means that there exists a vectorv ∈ R n R satisfying V (A R )v = ϕ(I) :t . Assigning B R = v and C ⊤ R = 1concludes the proof for the real SSM. The complex SSM (K = C) can be treated analogously, while assigning real values to A C , B C and C C in order to allow disregarding the fact that only real parts of outputs are taken (i.e., disregarding the operator ℜ(•) in Equation ( 2)).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.Definition 3. For an angle θ in R we will say that θ is in the mostly-positive region ifEQUATIONand we say that θ is in the mostly-negative region ifθ mod 2π ∈ 2π 3 , 4π 3 Remark 1.Under this definition, a non-zero complex number x has that its argument is in the mostly-positive region if and only if R(x) ≥ |x| 2 . Conversely, x has that its argument is in the mostly-negative region if and only if R(x) ≤ -|x| 2 . Definition 4. We say that a set is balanced if at least a sixth of its elements are in the mostly-positive region and at least a sixth of its elements are in the mostly-negative region. Definition 5. The balancing number of a complex number x with argument θ is defined as the minimum p ∈ N such that for any non-zero real number b the set {b + θ, b + 2θ, . . . , b + pθ} is balanced. If no such p exists, we say that the balancing number of x is infinity. We denote the balancing number of x by β(x).We will begin by establishing an upper bound on β(x) for x in a specific region in the complex plane. Subsequently, we generalize this result to give an upper bound of the balancing number for almost all complex numbers. Lemma 1. For any natural number p ≥ 4, if a non-zero complex number x has an argument θ such that θ is in [ 2π p , 2π 3 ], then β(x) ≤ p. Moreover, for any natural number p ≥ 9, if x has an argument θ such that θ is in[π + 2π p-1 , 4π 3 ] then β(x) ≤ p.Proof. Since the mostly-positive and mostly-negative regions are defined by looking at the angle of a complex number mod 2π, to prove that β(x) ≤ p, it is enough to show there exists some number k ≤ p such that for any real b the following set{(b + θ) mod 2π, (b + 2 • θ) mod 2π, . . . , (b + k • θ) mod 2π} is balanced.Indeed, let there be some real b.EQUATION] and p ≥ 4 , Let k be the natural number such that 2π < θk ≤ 2π + θ. It follows that 4 ≤ k ≤ p and that θ ≤ 2π k-1 . By Lemma 5 we have that the set{(b + θ) mod 2π, (b + 2 • θ) mod 2π, . . . , (b + k • θ) mod 2π}has at least a single point in any continuous interval (in mod 2π) of length θ. As such, any continuous interval mod 2π of length 2π 3 must contain at leastEQUATIONpoints, where the last inequality is true for any k ≥ 4. Since the mostly-positive and mostly-negative regions are continuous intervals (mod 2π) of length 2π 3 , we have that the set{(b + θ) mod 2π, (b + 2 • θ) mod 2π, . . . , (b + k • θ) mod 2π}has at least a sixth of its points in the mostly-positive and mostly-negative regions, and is therefore balanced, as needed.2. If θ is in [ π 2 + 2π p-1 , 4π 3 ] and p ≥ 9, then 2θ mod π is in the interval 2π p-1 2 , 2π 3 which is contained in the 2π ⌊ p 2 ⌋, 2π 3 . Therefore, by the previous section, there exists some k ≤ p 2 such that the following set:{b + 2θ mod 2π, . . . , b + k • 2θ mod 2π} and the set {(b -θ) + 2θ mod 2π, . . . , (b -θ) + k • 2θ mod 2π}are both balanced. Overall, their union, the set{(b + θ) mod 2π, (b + 2 • θ) mod 2π, . . . , (b + 2k • θ) mod 2π}is also balanced, showing that the β(x) ≤ 2k ≤ p as needed.Lemma 2. For any natrual numbers r, θ the following holds:β e r+iθ = β e r-iθProof. For any rational numbers θ and b, and for any natural number p, we will define the set S θ,b,p in the following way:S θ,b,p = {(b + θ) mod 2π, (b + 2 • θ) mod 2π, . . . , (b + p • θ) mod 2π}We will also define the set S θ,p asS θ,p = {S θ,b,p |b ∈ C} .Given this notation, we have that β e r-iθ = p if and only if p is the minimum natural number such that every set in S θ,p is balanced. For any rational numbers θ and b and for any natural number p, we have S -θ,-b,p = -S θ,b,p (Where minus is taken element-wise mod 2π). This immediately gives:S -θ,p = -S θ,p .Since the mostly-positive and mostly-negative regions are invariant to taking a minus mod 2π, we have that all the sets in S θ,p are balanced if and only if so are all the sets of S -θ,p . This directly implies that β e r+iθ = β e r-iθ as needed.Corollary 4. If x ∈ C has that arg(x) mod π ∈ [ 2π p-1 , π -2π p-1 ] for some p ≥ 9 then β(x) ≤ pProof. Denote θ ≡ arg(x). From Lemma 1 if the angle θ lies within the intervalEQUATIONthen β(x) ≤ p. Additionally, Lemma 2 indicates that the same holds if θ is in the interval -I (where operations are element-wise mod 2π). Hence, we have that if θ is contained in interval I ′ , whereI ′ = I ∪ (-I) = 2π p , 2π 3 ∪ π + 2π p -1 , 4π 3 ∪ 4π 3 , 2π - 2π p ∪ 2π 3 , π - 2π p -1 = 2π p , π - 2π p -1 ∪ π + 2π p -1 , 2π - 2π p then β(x) ≤ p. Overall, this means that if θ has that θ mod π ∈ 2π p -1 , π - 2π p -1then β(x) ≤ p, which gives the Corollary.Let ϵ > 0 be any positive number. For any sequence X = {X 1 , X 2 , . . . , X t }, let X| 1 denote the subsequence consisting of elements at odd indices, i.e., X| 1 = {X 1 , X 3 , . . .}.C ))| ≥ 0.2 we have that arg(A C ) ∈ π 16 , π -π16 , and soarg(A 2 C ) mod π = 2 arg(A C ) mod π ∈ 2 • π 16 , π - π 16 mod π = 2π 9 -1 , π - 2π 9 -1 .This implies, by Corollary 4, that the balancing number ofA 2 C is less than 9. Now, if ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ n C ,(A C ,B C ,C C ) (•) up to time t, then, by definition, ∥ϕ n R ,(A R ,B R ,C R ) (I) :t -ϕ n C ,(A C ,B C ,C C ) (I) :t ∥ 1 ≤ ϵ . This implies ∥ϕ n R ,(A R ,B R ,C R ) (I) :t | 1 -ϕ n C ,(A C ,B C ,C C ) (I) :t | 1 ∥ 1 ≤ ϵ .Now, we have thatϕ 1,(A C ,B C ,C C ) (I) :t | 1 k = ϕ 1,(A C ,B C ,C C ) (I) :t 2k-1 = ℜ B C C C A 2k-2 Cand because the balancing of A 2 C is at most 9, this implies that there exists a subsequence of 1, 2, . . . , ⌊t/2⌋ with increasing indices k j of length at least t 9 -1 such that if j is even thenB C C C A 2 C kj -1 is in the mostly-positive region, which implies ℜ B C C C A 2 C kj -1 ≥ |B C C C | A 2 C kj -1 2 ≥ 1 4 ,where the first inequality is due to the definition of the mostly-positive region and the second is implied from the assumption that|B C • C C | ≥ 1 and |A C | ≥ 0.5 1/t .Conversely, if j is odd it is in the mostly-negative region, which impliesEQUATIONNext, we will show that the impulse response of any real system, when restricted to even indices, can change its sign at most n R -1 times. This will prove the theorem since1 4 t 9 -n R -1 ≤ ∥ϕ n R ,(A R ,B R ,C R ) (I) :t | 1 -ϕ n C ,(A C ,B C ,C C ) (I) :t | 1 ∥ 1 ≤ ϵ .The first inequality results from the fact that there would be at least t p -n R -1 indices where1 4 ≤ ϕ 1,(A C ,B C ,C C ) (I) :t | 1 k and ϕ n R ,(A R ,B R ,C R ) (I) :t | 1 and ϕ 1,(A C ,B C ,C C ) (I) :t | 1 disagreeon sign, which yields the theorem.Indeed, let us upper bound the number of sign changes of the real impulse response when restricted to odd indices. We have thatϕ n R ,(A R ,B R ,C R ) (I) :t | 1 k = ϕ n R ,(A R ,B R ,C R ) (I) :t 2k-1 = ℜ C R A 2k-2 R B R = C R A 2k-2 R B R = n R j=1 (B R ) j (C R ) j (A R ) 2k-2 j,j.By the mean value theorem, the number of times ϕ n R ,(A R ,B R ,C R ) (I) :t | 1 changes signs is bounded by the number of zeros of the following continuous function:f (x) = n R j=1 (B R ) j (C R ) j (A R ) 2 j,j x .This function is a linear combination of n R exponential functions with a positive base, and so by Lemma 4 , it has at most n R -1 zeros, as needed.Let d, m be natural numbers such that d + m ≤ ⌊t/2⌋, and let σ be in {odd, even}. We will showthat n R ∥C ⊤ R ⊙ B R ∥ ∞ ≥ 2 d+2 min{d,m} 2 -d (ϕ (I) | σ ) (d)m -ϵ , thus proving the theorem.Let ϕ n R ,(A R ,B R ,C R ) (•) be a real system that ϵ-approximates ϕ (•) up to time t. For convenience, we will denote ϕ n R ,(A R ,B R ,C R ) (I) :t by Y and ϕ (I) :t by T. Then, by definition, we have that∥T -Y∥ 1 ≤ ϵ, which implies that |T| σ -Y| σ | ∞ ≤ ϵ.Lemma 9 guarantees that there exist some parameters ÃR , BR , CR where ÃR is non-negative and the following two things hold:∥C T R ⊙ B R ∥ ∞ ≥ ∥ CR T ⊙ BR ∥ ∞ Y| σ = ϕ n R ,( ÃR , BR , CR) (I) :t .Because ÃR is non-negative, Y| σ can be viewed as a linear combination of decaying exponentials with positive coefficients. Since the forward difference is linear, Lemma 6 ensures that the absolute value of the dth forward difference of Y| σ at index m is upper bounded bym d + m m d d + m d • n R ∥ CR T ⊙ BR ∥ ∞ .Using Lemma 12, we get d) .(Y| σ ) (d) m ≤ n R ∥ CR T ⊙ BR ∥ ∞ 2 2 min(m,Lemma 8 implies that d) .∥T| σ -σ ∥ ∞ ≥ T| (d) σ -Y| (d) σ ∞ 2 d ≥ (T| σ ) (d) m -(Y| σ ) (d) m 2 d ≥ (T| σ ) (d) m 2 d - n R ∥ CR T ⊙ BR ∥ ∞ 2 d+2 min(m,Plugging in |T| σ -Y| σ | ∞ ≤ ϵ and T| σ , we get d) . Reordering this equation yields the desired result.ϵ ≥ 2 -d (ϕ (I) | σ ) (d) m - n R ∥ CR T ⊙ BR ∥ ∞ 2 d+2 min(m,For simplicity of notation, we will denote t-1 2 by k and assume without loss of generality that k is odd.EQUATION, σ = even, and ϵ ≤ 1 8 √ t yields:EQUATIONEQUATIONIn the subsequent analysis, we will demonstrate that(ϕ(I)| even ) ( k+1 2 ) ⌊ k+1 4 ⌋ ≥ 2 k+1 2 4 √ t .Once established, the remainder of the proof will naturally follow since plugging this forthcoming result into Equation (8) will ensure that:n∥C T ⊙ B∥ ∞ ≥ 2 k-1 8 √ t = 2 k 16 √ t = 2 ⌊(t-1)/2⌋ 16 √ t ≥ 2 (t/2)-1 16 √ t = 2 (t/2) 32 √ tsatisfying the requirements for our conclusion. Indeed, we have that for any j ≤ k(ϕ(I)| even ) j = (ϕ(I)) 2j = δ k (I) 2j = 1(2j = k + 1) = 1 j = k + 1 2 .Lemma 7 implies thatEQUATION2 )⌊ k+1 4 ⌋ = k+1 2 j=0 (ϕ(I)| even ) ⌊ k+1 4 ⌋+j (-1) k+1 2 -j k+1 2 j = k+1 2 j=0 1 j + k + 1 4 = k + 1 2 (-1) k+1 2 -j k+1 2 j = (-1) ⌊ k+1 4 ⌋ k+1 2 k+1 2 -k+1 4 = (-1) ⌊ k+1 4 ⌋ k+1 2 k+1 4.Let X be the sum of these random variables X = ⌊ t 4 ⌋ j=0 X j and denote its PDF by p X . We note thatP (R| even ) t 4 ⌋) ⌊ t 8 ⌋ ≤ ϵ 0 = P [-ϵ 0 < X < ϵ 0 ] ≤ 2ϵ 0 max x∈R p X (x) .As a sum of i.i.d. random variables, the maximum of p X is upper bounded by the maximum of the PDF of each of the random variables it is a sum of. Which means thatmax x∈R p X (x) ≤ max x∈R p X ⌊ t 8 ⌋ (x) = 1 2α ⌊t/4⌋ ⌊t/8⌋ ≤ ⌊ t 8 ⌋ α2 ⌊ t 4 ⌋ ≤ √ t 2α2 ⌊ t 4 ⌋(where the second inequality results from Lemma 10). Overall we have thatP (R| even ) (⌊ t 4 ⌋) ⌊ t 8 ⌋ ≤ ϵ 0 ≤ ϵ 0 √ t 2α2 ⌊ t 4 ⌋ . Plugging in ϵ 0 = 2 ⌊ t 4 ⌋ • 2α √ δ √ t we have that P (R| even ) (⌊ t 4 ⌋) ⌊ t 8 ⌋ ≤ 2 ⌊ t 4 ⌋ • 2α √ δ √ t ≤ √ δwhich concludes the proof.Theorem 2 demonstrated thatn R ∥C ⊤ R ⊙B R ∥ ∞ ≥ max d,m∈N , d+m≤⌊t/2⌋ , σ∈{odd , even} 2 d+2 min{d,m} 2 -d (ϕ(I)| σ ) (d) m -ϵ .Plugging in σ = odd, we have that for any m ∈ [⌊t/2⌋] the following holds: n R ∥C ⊤ R ⊙ B R ∥ ∞ ≥ 2 ⌊t/4⌋+2⌊t/4⌋(1 -0.5) = 2 3⌊t/4⌋-1 ≥ 2 3t/4-4 , as required.It is sufficient to prove the proposition for n C = t since the dimension of a diagonal SSM can always be effectively reduced by zeroing out elements of B C .According to Section 2.3, it is enough to show that there exist assignments for (A C , B C , C C ) such that the following conditions hold:ϕ t,(A C ,B C ,C C ) (I) :t = ϕ(I) :t , ∥B C ∥ 2 = 2∥ϕ(I) :t ∥ 2 , ∥C T C ∥ 2 = 1 . For convenience, we will denote A C , B C , C C by A, B, C.We begin by utilizing the theory of discrete Fourier transform (DFT) to allow us to write the truncated impulse response of ϕ of length t as a linear combination of t decaying sine and cosine waves. Specifically, defining φ(I) :t k = (ϕ(I):t) k α k-1 , where α ∈ (0, 1) is some constant, and denoting the DFT of φ(I) :t by a + bi ∈ C t we get that ∀k ∈ [t],(ϕ(I) :t ) k α k-1 = 1 t t-1 j=0 a j+1 cos 2π(k -1) j t + t-1 j=0 b j+1 sin 2π(k -1) j t .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 A to be a scaled version of the t roots of unity, and C to be the inverse of square root of t as follows:A j,j = αe 2πi j-1 t , C j = 1 √ t We know (see Section 2.3) that the impulse response of a complex system at index k is given by:ϕ t,(A,B,C) (I) :t k = ℜ   t j=1 A k-1 j,j B j C j   . Which implies that ℜ   t j=1 A k-1 j,j B j C j   = t j=1 ℜ(C j A k-1 j,j )ℜ(B j ) -ℑ(C j A k-1 j,j )ℑ(B j ) = α k-1 1 √ t   t-1 j=0 cos 2π(k -1) j t ℜ(B j ) - t-1 j=0 sin 2π(k -1) j t ℑ(B j )   .By the Plancherel theorem the following holds:∥a + bi∥ 2 = √ t φ(I) :t 2 ≤ √ t∥ϕ(I) :t ∥ 2 α t-1 .Therefore, if we define B = a-ib √ t , we getℜ   t j=1 A k-1 j,j B j C j   = α k-1 t   t-1 j=0 a j+1 cos 2π(k -1) j t + t-1 j=0 b j+1 sin 2π(k -1) j t   = (ϕ(I) :t ) k and ∥B∥ 2 = a -bi √ t 2 ≤ ∥ϕ(I) :t ∥ 2 α t-1 , ∥C∥ 2 = t • 1 √ t 2 = 1 ,and by choosing α = 1 2 1 t-1 we get the required assignment.For simplicity of notation, letEQUATIONR be denoted by A (i) , B (i) , C (i) , respectively, and ℓ(A (i) , B (i) , C (i) ) by ℓ (i) . We begin by writing the loss explicitly (see Appendix C):ℓ(A, B, C) = t j=1 n R k=1 A j-1 k B k C k -ϕ (I) j 2 . Fixing any k ∈ [n R ], we have dℓ(A, B, C) dB k = 2 t j=1 A j-1 k C k n R m=1 A j-1 m B m C m -ϕ (I) j , which, combined with the fact that |A m | ≤ 1, leads to dℓ(A, B, C) dB k ≤ 2 |C k | t j=1 n R m=1 A j-1 m B m C m -ϕ (I) j = 2 |C k | ϕ n,(A,B,C) (I) :t -ϕ (I) :t 1 ≤ 2 √ t |C k | ϕ n,(A,B,C) (I) :t -ϕ (I) :t 2 ≤ 2 √ t • max (∥B∥ ∞ , ∥C∥ ∞ ) ℓ(A, B, C) . | l′′ i (0)| = dℓ(A, B, C) (dB i ) 2 = d t j=1 n R m=1 A j-1 m B m C m -ϕ (I) j 2 (dB i ) 2 = t j=1 d dB i n R m=1 A j-1 m B m C m -ϕ (I) j • 2A j-1 i C i = t j=1 2A j-1 i C i • A j-1 i C i ≥ 2∥C∥ 2 ∞ ,which concludes the proof.For simplicity of notation, we will denote A R , B R , C R , n R by A, B, C, n. The robustness to qquantization is by definition the probability:P ∥ϕ n,(A⊙Q A ,B⊙Q B ,C⊙Q C ) (I) :t -ϕ(I) :t ∥ 1 ≤ ϵ ≤ P ϕ n,(A⊙Q A ,B⊙Q B ,C⊙Q C ) (I) 1 -ϕ(I) 1 ≤ ϵ .Let us denote the random variable ϕ n,(A⊙Q A ,B⊙Q B ,C⊙Q C ) (I) 1 by X, and its PDF by p X . The probability P[|X -Y | ≤ ϵ] is equal to the integral Y +ϵ Y -ϵ p X (x)dx ≤ 2ϵ max x∈R p X (x). We get that P ∥ϕ n,(A⊙Q A ,B⊙Q B ,C⊙Q C ) (I) -ϕ(I)∥ 1 ≤ ϵ ≤ 2ϵ max x∈R p X (x) .and so, to prove the theorem, it suffices to show thatmax x∈R p X (x) ≤ 1 q∥B ⊙ C∥ ∞ .Let us investigate the random variable X:X = n i=1 (B ⊙ Q B ) i (C ⊙ Q C ) i = n i=1 B i C i (1 + q B i )(1 + q C i ) = n i=1 B i C i (1 + q B i + q C i + q B i q C i ) ,where q B i , q C i ∼ U(-q/2, q/2). As a sum of independent random variables, the maximum of p X is upper bounded by the maximum of the PDF of each of the random variables it is a sum of. Specifically, for any i ∈ [n], it is bounded by the maximum of the PDF of U(-B i C i q/2, B i C i q/2) which is equal to 1/(B i C i q). Overall, this means thatmax x∈R p X (x) ≤ min i 1 B i C i q = 1 q∥B ⊙ C∥ ∞ ,as needed. Proof. We will show this by induction. The claim is obvious for n = 1, 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 byf (x) = k+1 i=1 b i a i x .If b 1 = 0 or a 1 = 0 we can immediately use the induction step on f . Otherwise, we can write f in the following way:f (x) = b 1 a x 1 1 + k+1 i=2 b i b 1 a i a 1 x .Since b 1 a x 1 is always non-zero, the amount of roots of f is equal to the number of roots of the function g defined byg(x) = 1 + n+1 i=2 b i b 1 a i a 1 x .By Rolle's theorem, the number of roots of a function is bounded by the number of roots of its derivative plus one. We have that g ′ (x) is given by:g ′ (x) = k+1 i=2 b i b 1 a i a 1 x ln a i a 1 .Which, by the induction step, can have at most k roots, as needed. This completes the proof. Lemma 6. Let α be a real number within the interval [0, 1], and let n, m be natural numbers with t being a natural number such that t ≥ n + m. The absolute value of the mth forward difference of the sequence X = {1, α, α 2 , . . . , α t-1 } at index n, as defined in Definition 1, is bounded above bym n + m m n n + m n .Proof. By induction, the mth forward difference of X at index n (when we start at index 0), for n ≤ t -m, is α n (α -1)m . For α ∈ [0, 1], this absolute value simplifies to:|α n (α -1) m | = α n (1 -α) m .To find the maximum value of this expression within [0, 1], we differentiate with respect to α and set the derivative to zero:d dα (α n (1 -α) m ) = nα n-1 (1 -α) m -mα n (1 -α) m-1 .Solving for α, we find that the critical points are at α ∈ {0, 1} or:n(1 -α) -mα = 0 =⇒ α = n n + m .A second derivative test confirms that α = n n+m is a maximum within [0, 1]. Substituting α max = n n+m into our original expression, we obtain:|(X (m) ) n | ≤ n n + m n 1 - n n + m m = m n + m m n n + m n ,thereby completing the proof. Lemma 7. Given a sequence A = {a 0 , a 1 , . . . , a n-1 } and two natural numbers m < n, the mth forward difference of A (Definition 1) at index n, denoted A (m) n , is given byA (m) n = m j=0a n+j (-1) m-j m jProof. We will show this by induction over m. For m = 0 This is obvious. Let's assume that the Lemma is true for m = k and prove that it is also true for m = k + 1 < n. are impluse responses of some other real SSM of dimension n R with parameters ( ÃR , BR , CR ) where ÃR is non-negative, and∥C T R ⊙ B R ∥ ∞ ≥ ∥ CR T ⊙ BR ∥ ∞Proof. We observe that (see Section 2.3)(Y| odd ) i = C R A R 2(i-1) B Rsetting ( ÃR , BR , CR ) = (A 2 R , B R , C R ) yields that Y| odd is the impulse response of the real SSM ϕ n R ,( ÃR , BR , CR) .For the even case:(Y| even ) i = C R A R 2i-1 B R setting ( ÃR , BR , CR ) = (A 2 R , B R , C R A R )yields that Y| even is the impulse response of the real SSM ϕ n R ,( ÃR , BR , CR) . In both cases, ÃR is non-negative, and To validate the lemma, we consider cases based on the parity of n. For even n, n∥C T R ⊙ B R ∥ ∞ ≥ ∥ CR T ⊙ BR ∥ ∞⌊ n 2 ⌋ = n n 2 ≥ 2 n 2 n 2 > 2 n 4 √ 2n ,and for odd n, n⌊ n 2 ⌋ = n n-1 2 ≥ n -1 n-1 2 ≥ 2 n-2 2 n-1 2 ≥ 2 n 4 √ 2n ,thereby proving the lemma as required. c = 0. After the copy token comes a sequence of h tokens, sampled as before and denoted X. The 2hth token is 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 c are irrelevant for the task. The output sequence corresponding to the above-described input sequence is equal to the input sequence shifted one position to the left (with the last token of X placed on the right). Training and evaluation (measurement of 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 to an example is the cross-entropy loss averaged over the last h tokens of the output. In evaluation, the zero-one loss is averaged over the last h tokens of the output across one thousand freshly generated examples.Hyperparameters. Our implementation is based on a widely adopted Mamba repository, available at https://github.com/alxndrTL/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 a hidden dimension of 64. We trained the network with a batch size of 8 and a learning rate of 1 × 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 B and the output matrix C to be complex, while keeping the discretization parameter ∆ real. To maintain parameter count, the dimension of SSMs with complex parameterization was half the dimension with real parameterization, namely, 8 as opposed to 16.It is possible to strengthen this result, e.g., by showing that the requirement n K ≥ t can be replaced by n K ≥ ⌈(t + 1)/2⌉ 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 B C (or C C ).To see that exponentiality does not take place when ϕ(I) = (+1, -1, +1, -1, . . .), note that in this case, with any n R , ϕ n R ,(A R ,B R ,C R ) (•) ϵ-approximates ϕ(•) up to time t whenever: C R ⊤ ⊙ B R holds one in its first entry and zeros elsewhere; and A R holds min{0, (-1 + ϵ/t 2 )} in its first diagonal entry.It is possible to develop a variant of this result that only requires n C ≥ ⌈(t + 1)/2⌉. We omit details, as the current form of the result suffices for our purposes.https://github.com/state-spaces/s4 (Apache-2.0 license).https://github.com/alxndrTL/mamba.py (MIT license). 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

- 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.
  
- 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.
  
- 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.
  
- 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.

- 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?
questions: questions: See above, + I have another question - something which I might have missed but is my biggest curiosity:

- 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.

I 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: limitations: See above
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: questions: See above.
limitations: limitations: The paper has a thorough discussion of the limitations of the analysis.
paper_summary: paper_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$.
strength_weakness: strength_weakness: 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.

Footnote 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.
questions: 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.
* How do the results in this paper serve as an important stepping stone towards understanding real vs complex parameterization in LTV or selective settings?
* What happens if we use a feedthrough matrix D in (1), which is common in nearly all SSM parameterizations?
* What is $\Omega(t)$ on line 187? Is it defined somewhere in the paper?
* Is it possible to do better than $n_{\mathbb{C}} = t$? why or why not?
limitations: limitations: yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
questions: 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?
2. 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?
3. 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: limitations: None.

Comments: title: Thanks!
Increasing score to 8
comment: Thank you for engaging in the discussion and for highlighting the quality of our work! With regards to the motivation behind it: we will include in the camera-ready version a detailed account covering all of our arguments from the discussion (and more).
Dear Author(s),

I understand your point regarding real LTI systems with arbitrarily large state dimensions $N$ being universal approximators. I realize that my previous comment about universal approximation should have been more precise, as I was specifically referring to the approximation of matrices with a fixed dimension.

However, this does not alter my primary concern about the relevance of the problem addressed in this paper. From a backpropagation perspective, it's logical to use real parameterization for simplicity, and in that context, this paper serves as a validation that complex numbers are indeed necessary. From a linear algebra standpoint, constraining a matrix to have real eigenvalues is not typically a natural approach, making this paper a (well-executed) exploration of an unusually framed problem. Whether or not real parameterizations are universal approximators does not fundamentally change the nature of the issue at hand.

This is not a critique of the depth of your research. I believe the work presented is of high quality. My comments are more focused on the significance of the problem studied in the paper. I will maintain my current evaluation. Thank you.

Reviewer UNm3
Thank you.

We respectfully disagree with the following statement:

> “the underlying question studied in this work is relatively trivial from a linear algebra perspective, pinning that matrices with real eigenvalues are not universal approximators”. 

It is true that matrices with complex eigenvalues are more general than ones with real eigenvalues, but to our knowledge, this does not establish any benefit of complex parameterizations over real parameterizations for diagonal SSMs. Indeed (perhaps counter-intuitively), we show in Proposition 1 that if the dimension of a diagonal SSM is not bounded, real and complex parameterizations are equivalent, in the sense that they both lead to universal approximation (of LTI mappings). The question is then whether complex parameterizations allow approximating mappings with lower dimension or parameter magnitudes than are required with real parameterizations. To our knowledge, this question — which we affirm in Theorems 1 and 2, Corollaries 1 and 2, and Proposition 3 — cannot be answered via simple linear algebraic arguments as you mentioned.

We hope the above clarification addresses your remaining concern. Please let us know if this is not the case and we will further elaborate.
Thank you for your response! The additional experiments look convincing; therefore, I have raised my score. My primary concern is still that the underlying question studied in this work is relatively trivial from a linear algebra perspective, pinning that matrices with real eigenvalues are not universal approximators. This prevents me from further increasing my evaluation. However, I acknowledge that the problem studied in this work is important and the author(s) have done a good job of making a point.
Thank you very much!

As you suggest, we will reposition Theorem 1 and clarify its limitations. 

With regards to the stronger result you outline, there are two steps towards it which we intend to take:
* Extending the result in Theorem 1 as discussed in our rebuttal. Namely, extending it to apply to sufficiently oscillating impulse responses, which form a positive measure subset of the complex SSM’s function class.
* Analyzing forward differences of oscillatory impulse responses, thereby hopefully drawing another corollary of Theorem 2, which will establish that in order to approximate an oscillatory function, the real SSM must have dimension or parameter magnitudes exponential in $t$.

Thank you again for your thorough analysis and very useful suggestions!
Thank you.  Please let us know if a need for further information arises.
Thank you very much! The camera ready version will indeed expand on both selectivity and the new experiments.
Dear Authors,
Thanks so much for the efforts in this rebuttal. I raised my score to accept as I believe the additional experiments, along with your interpretation of selectivity, are convincing.

I still would tone down Thm 1 and place it as a counterexample. What you can do is argue that oscillations are important, but you cannot be 100% formal in this. A thing that would be super nice to show is that using only exponential decay (real numbers) leads to a basis that requires, in general, more elements compared to exp + exp*sine waves. This may be true, but it requires some spectral or functional analysis. It would make your point, though, SO MUCH stronger. Currently, Thm1 gives a hint, but is not giving us the generality expected from a theorem.
Thank you for a very clear and interesting rebuttal.

I think your discussion of selectivity is very interesting and should be included in as much details as possible in the camera ready version.

Your new experiments in the .pdf are great as well! They should also be included in camera ready.

I am raising my score to an 8.
Thank you for the response and additional results. I will stay with my assessment.