# Theoretical Foundations of Deep Selective State-Space Models

Nicola Muca Cirone  Antonio Orvieto  Benjamin Walker  Cristopher Salvi  Terry
Lyons

###### Abstract

Structured state-space models (SSMs) such as S4, stemming from the seminal
work of Gu et al., are gaining popularity as effective approaches for modeling
sequential data. Deep SSMs demonstrate outstanding performance across a
diverse set of domains, at a reduced training and inference cost compared to
attention-based transformers. Recent developments show that if the linear
recurrence powering SSMs allows for multiplicative interactions between inputs
and hidden states (e.g. GateLoop, Mamba, GLA), then the resulting architecture
can surpass in both in accuracy and efficiency attention-powered foundation
models trained on text, at scales of billion parameters. In this paper, we
give theoretical grounding to this recent finding using tools from Rough Path
Theory: we show that when random linear recurrences are equipped with simple
input-controlled transitions (selectivity mechanism), then the hidden state is
provably a low-dimensional projection of a powerful mathematical object called
the signature of the input – capturing non-linear interactions between tokens
at distinct timescales. Our theory not only motivates the success of modern
selective state-space models such as Mamba but also provides a solid framework
to understand the expressive power of future SSM variants.

Machine Learning, ICML

[name=Theorem,numberwithin=section]thm
[name=Lemma,numberwithin=section,numberlike=thm]lem
[name=Corollary,numberwithin=section,numberlike=thm]cor
[name=Proposition,numberwithin=section,numberlike=thm]prop
[name=Assumption,numberlike=thm]ass

##  1 Introduction

Sequence-to-sequence blocks are fundamental components of modern deep learning
models for language, images, video, audio, time series, and genomics. While
attention (Vaswani et al., 2017; Dosovitskiy et al., 2020) has been for the
last five years the dominant mechanism powering these architectures,
competitive results have been recently achieved by replacing attention with
state-space models (SSMs): GPU-efficient linear recurrent sequence-to-sequence
blocks stemming from S4 (Gu et al., 2021). SSMs achieve state-of-the-art
results on long-range-reasoning benchmarks (Tay et al., 2020) and show
outstanding performance in various domain including vision (Nguyen et al.,
2022), audio (Goel et al., 2022), biological signals (Gu et al., 2021),
reinforcement learning (Lu et al., 2023) and online learning (Zucchet et al.,
2023). SSMs recently have gained significant interest in the community since
their computational complexity scales linearly in sequence length, while
attention scales quadratically; moreover, unlike other recurrent mechanisms
such as LSTMs (Hochreiter & Schmidhuber, 1997) and GRUs (Cho et al., 2014),
they can be efficiently parallelized on GPUs during training using parallel
scans (Martin & Cundy, 2017; Smith et al., 2023).

While standard SSMs were shown to be particularly powerful on signal
processing tasks, their computation power is limited: the core sequential
mechanism of S4 is equivalent to a convolution (filtering) (Li et al., 2022a).
This represents a drawback in challenging domains such as text and genetics,
where the ability to select data efficiently in an input-dependent manner
(i.e., perform content-based reasoning) is crucial (see results in (Wang et
al., 2022; Fu et al., 2022)). Towards reaching this goal with recurrent
models, various adaptations of S4 have been proposed in the last few months.
Notably, Mamba (Gu & Dao, 2023) implements simple and efficient gating
mechanisms on the S4 recurrence, unlocking input selectivity in the memory
update. Mamba achieved state-of-the-art performance of various language
modeling tasks at a fraction of the compute needed to train a transformer
model with an equal number of parameters, with inference time still scaling
(like S4) with $O(\text{sequence length})$. Similar ideas can be found in
recent S4-inspired recurrent linear attention models, such as RWKV (Peng et
al., 2023), RetNet (Sun et al., 2023), Gateloop (Katsch, 2023) and Gated
Linear Attention (GLA) (Yang et al., 2023). Last, very recently, (De et al.,
2024) surpassed the performance of Mamba with a gated RNN architecture –
Griffin – based on an improved version of the LRU (Orvieto et al., 2023b),
perhaps the simplest SSM variant.

At the core of the models discussed above is a linear time-varying dynamical
system, where content-based reasoning is performed along the input sequence
through an efficient and parallelizable update on a hidden state. In this
paper, we generalize the structure of such models, drawing a direct link to
_controlled differential equations (CDEs)_ (Kidger et al., 2020; Morrill et
al., 2021; Arribas et al., 2020; Salvi et al., 2022; Hoglund et al., 2023) and
using tools from _rough path theory_ to study expressivity of deep selective
SSMs.

  1. 1.

We provide a framework for the analysis of (input-controlled) linear (in the
hidden state) recurrences such as S4, Mamba and GLA. This framework allows the
use of powerful tools and results in the Rough Path Theory literature to
reason about the expressivity of modern SSM layers and to obtain generalized
versions of the universality results of (Li et al., 2022b). This framework
captures both S4 and Mamba, as well as recently proposed linear-attention-
powered recurrences.

  2. 2.

We prove that wide enough randomly initialized dense input-controlled linear
recurrences are fully expressive: with no need for a multi-layer-perceptron
(MLP) block transforming pointwise the recurrence output (as instead is done
in the transformers architecture or at the S4 recurrence output), we show that
the hidden state contains sufficient input statistics to approximate any
continuous function from the input sequence to a target value. This is in
clear contrast to S4, where the hidden state is just a convolution of the
input sequence with a fixed kernel.

  3. 3.

We show that diagonal input-controlled linear recurrences (such as Mamba)
provably collect input statistics more efficiently than S4. We additionally
show that chaining such blocks, by simply placing linear pointwise maps in
between, allows computation of higher order global statistics – matching the
dense linear input-controlled setting discussed in point (2) above, in the
depth limit.

The main objective of our research is to outline the foundational mathematical
tools for comprehensive theoretical investigations of modern recurrent blocks.
In addition to our results and insights concerning recently proposed SSM
models, our work provides a framework that can be useful for analyzing and
comparing forthcoming architectural advances.

##  2 State-space Models

We describe here the structure of the main SSMs-based strategies for
processing length-$L$ input sequences of $d$ dimensional tokens:
$x\in\mathbb{R}^{d\times L}$. We denote by $x_{\ell}$ the $\ell$-th column of
$x$ (the $\ell$-th token) and by $x^{i}$ the $i$-th row of $x$ (time series
for the $i$-th channel).

###  2.1 Review of Modern SSMs

We start with a quick simplified recap of S4 (Gu et al., 2021) and then
describe recently proposed variants such as Mamba (in particular, the S6
block) (Gu & Dao, 2023) and Gated Linear Attention (GLA) (Yang et al., 2023).
We restrict our focus to the recurrent mechanism and invite the reader to
refer to the original papers for a description of the token-wise operations
following and preceding each block.

##### SSM basics (S4).

Most111The LRU (Orvieto et al., 2023b) and S5 (Smith et al., 2023) instead
build a single recurrence operating on multidimensional (# channels)
inputs.SSMs (Gu et al., 2021, 2022) operate independently on input channels.
The time-series for each channel $x^{i}\in\mathbb{R}^{L}$ is seen as the
result of sampling a latent continuous-time signal $X^{i}:[0,1]\to\mathbb{R}$
at multiples of a channel-dependent stepsize $\Delta_{i}>0$:

$X_{\Delta_{i}\ell}^{i}:=X^{i}(\Delta_{i}\ell)=x_{\ell}^{i}$

for all $\ell\in[L]$, $i\in[d]$.

Under S4, each input signal $X^{i}$ produces a complex-valued state signal
$Z^{i}:[0,1]\to\mathbb{C}^{N}$ according to a linear differential equation:

$\displaystyle\frac{d}{dt}Z_{t}^{i}=A_{i}Z_{t}^{i}+BX_{t}^{i},$ (1)

where $A_{i}=\text{diag}(a_{i,1},a_{i,2},\dots a_{i,N})$ is channel-specific
diagonal $N\times N$ complex valued matrix: $a_{i,n}\in\mathbb{C}$ for all
$(i,n)\in[d]\times[N]$. $B\in\mathbb{C}^{N}$ is an input projection shared
across input components $i\in[d]$. SSM models are based on stable
discretizations of the continuous time system above: each input sequence
channel $x^{i}$ produces a sequence of hidden states
$z^{i}=(z_{1}^{i},z_{2}^{i},\dots,z_{L}^{i})\in\mathbb{R}^{N\times L}$ as
follows:

$\displaystyle
z_{\ell}^{i}=\bar{A}_{i}z_{\ell-1}^{i}+\bar{B}_{i}x_{\ell}^{i},$ (2)

with $\bar{A}_{i},\bar{B}_{i}$ determined by the discretization technique and
the channel-dependent stepsize $\Delta_{i}$: under the commonly used Zero-
Order Hold discretization 222This corresponds to: (i). considering the
continuous underlying signal $X_{t}$ to be piecewise constant, (ii). solving
exactly the ODE 1 and finally (iii). sampling $Z_{t}$ at the sample times of
$X_{t}$. ,

$\bar{A}_{i}=\exp(\Delta_{i}A_{i}),\
\bar{B}_{i}=(\Delta_{i}A_{i})^{-1}(\exp(\Delta_{i}A_{i})-I)\Delta_{i}B.$

Note from eq. 2 that SSMs at inference time are equivalent to linear recurrent
neural networks (RNNs). Yet, learning with gradient descent is performed on
the continuous-time variables, unlocking stable signal propagation and
alleviating vanishing gradients (Orvieto et al., 2023b). Finally, at each
dimension $i$, the sequence of hidden states is mapped back to real numbers,
and a projection is performed to produce an output a sequence of tokens
$y\in\mathbb{R}^{d\times L}$ with the same dimensions as $x$. To conclude, we
point out that the transition matrix $A$ is often (yet not crucially, as shown
by Orvieto et al. (2023b)) structured, i.e. initialized deterministically
through HiPPO theory (Gu et al., 2020) in diagonal form. Common choices (Gu et
al., 2022) are $a_{\cdot,n}=-\frac{1}{2}+\mathrm{i}\mkern 1.0mu\pi n$
(S4D-Lin333Reall: $\mathrm{i}\mkern 1.0mu$ denotes the imaginary unit
$\sqrt{-1}$, not to be confused with the index $i$.) and
$a_{\cdot,n}=-\frac{1}{2}$ (S4D-Real).

##### Mamba.

The Selective SSM (S6) powering the Mamba architecture (Gu & Dao, 2023)
augments S4 with input-controlled transitions:

$\displaystyle
z_{\ell}^{i}={\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\bar{A}_{i}(x_{\ell}^{i})}z_{\ell-1}^{i}+{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\bar{B}(x_{\ell}^{i})}x_{\ell}^{i},$
(3)

where the most crucial component (see Table 7 in Gu & Dao (2023)) is the
dependency of $\bar{A}_{i}$ on the input – thus making the operation
$\bar{A}_{i}(x_{\ell}^{i})z_{\ell-1}^{i}$ effectively a gate. This dependency
of $\bar{A}_{i}$ on the input is achieved efficiently through the $\Delta_{i}$
parameter, which becomes iteration-dependent following the equation444To be
more precise, the scalar multiplier map $\alpha_{i}$ is the result of a low-
rank projection (timestamp independent) of the input (all channels).

$\Delta_{\ell}^{i}=\text{softplus}(\alpha_{i}x_{\ell}^{i}+\beta_{i})$ (4)

with $\alpha_{i},\beta_{i}\in\mathbb{R}$. The RG-LRU recurrence in (De et al.,
2024) works in a similar way, yet processing all input channels at once.

##### GLA and other linear attention variants.

Gated Linear attention555Discussed is only the single-head setting. (Yang et
al., 2023) is a recursion on a matrix hidden state $z\in\mathbb{R}^{N\times
N}$ with input-controlled transition:

$z_{\ell}={\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\bar{A}(x_{\ell})}\odot
z_{\ell-1}+{\color[rgb]{0,.5,.5}\definecolor[named]{pgfstrokecolor}{rgb}{0,.5,.5}\bar{B}(x_{\ell})}$
(5)

where $\odot$ denotes the Hadamard product and all channels in the input
sequence are fed into the transition through a linear attention mechanism, and
$A\in\mathbb{R}^{N\times N}$ is computed through the equation:

$\displaystyle\bar{B}(x_{\ell})=W_{\text{key}}^{\top}x_{\ell}x_{\ell}^{\top}W_{\text{val}}\in\mathbb{R}^{d\times
d},$
$\displaystyle\bar{A}(x_{\ell})=\tau^{-2}\sigma(x_{\ell}^{\top}W_{\alpha}+b_{\alpha})^{\top}\sigma(x_{\ell}^{\top}W_{\beta}+b_{\beta})\in\mathbb{R}^{d\times
d},$

with $W_{\text{key}},W_{\text{val}},W_{\alpha},W_{\beta}\in\mathbb{R}^{d\times
d}$, $b_{\alpha},b_{\beta}\in\mathbb{R}^{d}$, $\tau\geq 0$ and $\sigma$ is a
sigmoid. RetNet (Sun et al., 2023) is similar on $\bar{B}$ but does not have
input-controlled $\bar{A}$. GateLoop (Katsch, 2023) is similar to RetNet, with
$\bar{A}$ diagonal and complex-valued: phase and magnitude of each component
is controlled via a linear map on the input, similarly to Mamba.

###  2.2 Known properties of (non-linear) recurrences

Expressiveness of standard nonlinear RNNs of the form
$z_{\ell}=A\sigma(z_{\ell-1})+Bx_{\ell}$, where $\sigma$ is a nonlinearity,
has been extensively studied since the seminal work of Siegelmann & Sontag
(1992), with recent contributions such as (Korsky & Berwick, 2019; Hanson &
Raginsky, 2020). In particular, Hanson & Raginsky (2020) proved in the
continuous-time setting that wide enough non-linear RNNs can approximate up to
vanishing precision non-linear time-homogeneous systems of differential
equations, driven by input paths. The argument used here to show universality
is based on the celebrated Barron’s theorem (Barron, 1993) for approximation
of continuous functions with neural networks with one hidden layer. Indeed,
note that non-linear RNNs are recurrent perceptrons with one hidden layer,
acting both on the state and the input (Tallec & Ollivier, 2018). Instead,
(selective) SSMs such as S4 and Mamba have transition map which is linear in
the state – unlocking parallelization of the recurrent computation (Smith et
al., 2023; Gu & Dao, 2023).
In the context of linear RNNs and non-selective SSMs, many results (old and
new) exist that characterize expressivity. Li et al. (2022b) showed that
linear RNNs (i.e. S4-like recurrences) can approximate arbitrary convolution
filters in the width limit. Further, Hanson & Raginsky (2020) proved that
stacking exponentially (in the sequence length) many temporal convolution
filters, chained together with ReLU activations, leads to approximation of
arbitrary non-linear filters. Recent works (Orvieto et al., 2023a; Wang & Xue,
2023) prove universality of linear recurrences (one layer) when equipped with
a fixed (timestamp independent) point-wise MLP acting across the recurrence
output, with intriguing connections to Volterra series (Boyd & Chua, 1985).

Mamba (alongside with gated linear attention variants e.g. Yang et al. (2023))
does not fall in the linear RNN or the nonlinear RNN setting: its recurrence
is linear on the hidden state (hence it can be parallelized) but it is not
linear time-invariant as S4. In this paper, we study this setting.

##  3 SSMs as Linear CDEs

As shown by Gu & Dao (2023), the crucial component that unlocks in-context
learning and selectivity in modern SSMs is the input-dependent state-to-state
transition matrix $A$, gating the hidden state and thus allowing the system to
filter out irrelevant information and remember relevant information
indefinitely. As we will shortly see, one can study the structure and features
of such systems within a unified convenient continuous-time framework (Linear
Controlled Differential equations). We define such framework (Def. 6) in full
generality, and draw the connection to S4 and Mamba.

###  3.1 Linear CDEs

Let us consider the separable Banach space $C_{1,0}([0,1];\mathbb{R}^{d})$ of
absolutely continuous $\mathbb{R}^{d}$-valued paths on $[0,1]$ and starting at
the origin 666We remove the subscript $0$ if this constrain is removed.

$\left\\{\omega:t\mapsto\int_{0}^{t}\dot{\omega}_{s}~{}ds\mid\dot{\omega}\in
L^{1}([0,1];\mathbb{R}^{d})\right\\}$

endowed with the $1$-variation norm

$\left\lVert\omega\right\rVert_{1;[0,1]}:=\int_{0}^{1}|\dot{\omega}_{s}|~{}ds.$

Let $\mathbb{X}$ of be some topological vector space where the input data
lies. The prototypical example of $\mathbb{X}$ considered in the SSM
literature is the set of sequences of finite length. Modern selective (or
gated) SSMs such as Mamba do not work directly with raw input data. Instead,
they introduce continuous embeddings

$\displaystyle\omega:\mathbb{X}\to
C_{1,0}([0,1];\mathbb{R}^{d_{\omega}}),\quad\xi:\mathbb{X}\to
C_{1,0}([0,1];\mathbb{R}^{d_{\xi}})$

usually referred to as _gates_.

After the data $X\in\mathbb{X}$ is embedded into continuous paths
$\omega^{\text{X}},\xi^{\text{X}}$ by means of gates $\omega,\xi$
respectively, we define our model as a linear controlled differential equation
(CDE) driven by these embeddings: fix $N\in\mathbb{N}$, and matrices
$A_{1},...,A_{d_{\omega}}\in\mathbb{R}^{N\times N}$, and
$B\in\mathbb{R}^{N\times d_{\xi}}$. The model we consider in this paper is the
following Linear CDE777More generally, the initial condition $Z_{0}^{X}$ can
be chosen to be the image of another embedding of the input data, as we
discuss in the Appendix.

$\displaystyle Z:\mathbb{X}\to C_{1}([0,1];\mathbb{R}^{N})$ $\displaystyle
dZ^{\text{X}}_{t}=\sum_{i=1}^{d_{\omega}}A_{i}Z^{\text{X}}_{t}d\omega^{\text{X},i}_{t}+Bd\xi^{\text{X}}_{t},\quad
Z^{\text{X}}_{0}\in\mathbb{R}^{N}$ (6)

where $t\mapsto\omega^{\text{X},i}_{t}$ is the $i$-th channel of the path
$\omega^{\text{X}}$.

We show that both S4 and Mamba can be written in continuous-time as Linear
CDEs, for difference choices of $\omega$ and $\xi$. We describe this visually
in Fig. 1. This motivates us to study the expressivity of the model in Eq. 6
and how it is affected by the choice of $\omega$ and $\xi$.

##### S4 is a Linear CDE.

The S4 model (Gu et al., 2021) is a Linear CDE of the form (6) with “gate”
functions

$\displaystyle\omega^{\text{X}}_{t}=t,\quad\xi^{\text{X}}_{t}=\int_{0}^{t}X_{s}ds.$
(7)

###  3.2 Mamba is a Linear CDE

Let us revisit Eqn. (3), dropping the channel index $m$ for convenience. We
introduce a new parameter $\delta>0$ and consider the following
reparametrization: $\alpha\leftarrow\delta\tilde{\alpha},\
\beta\leftarrow\delta\tilde{\beta}$. Let us further approximate the softplus
function with a ReLU: $\sigma=\text{ReLU}(x)\simeq\log(1+e^{x})$. Eqn. (4)
becomes

$\Delta_{\ell}=\sigma(\delta\tilde{\alpha}x_{\ell}+\delta\tilde{\beta})=\sigma(\tilde{\alpha}x_{\ell}+\tilde{\beta})\delta.$

As shown Appendix F, Mamba in Eqn. (3) is equivalent to the following Linear
CDE

$dZ^{\text{X}}_{t}=AZ^{\text{X}}_{t}d\omega^{\text{X}}_{t}+Bd\xi^{\text{X}}_{t},$
(8)

where we defined $X_{t}$ piecewise constant, with values the $x_{l}$, on a
grid of stepsize $\delta$ and

$\displaystyle
d\omega^{\text{X}}_{t}=\sigma(\tilde{\alpha}X_{t}+\tilde{\beta})dt$
$\displaystyle
d\xi^{\text{X}}_{t}=\sigma(\tilde{\alpha}X_{t}+\tilde{\beta})X_{t}dt$

As a quick validation, note that Eqn. (3) becomes

$\displaystyle z_{\ell}$
$\displaystyle=\exp(\sigma(\tilde{\alpha}x_{\ell}+\tilde{\beta})\delta
A)z_{\ell-1}+\sigma(\tilde{\alpha}x_{\ell}+\tilde{\beta})\delta Bx_{\ell}.$

As $\delta\to 0$, the exponential becomes linear and one has

$\displaystyle z_{\ell}$ $\displaystyle\overset{\delta\to
0}{=}z_{\ell-1}+\sigma(\tilde{\alpha}x_{\ell}+\tilde{\beta})\delta
Az_{\ell-1}+\sigma(\tilde{\alpha}x_{\ell}+\tilde{\beta})\delta Bx_{\ell}.$

Which is the standard forward Euler discretization of the Mamba ODE in Eqn.
(8).

Figure 1: Example of the dynamics of the S4 and Mamba CDEs derived in Sec.
3.1. The continuous-time approximation of these algorithms can be written as a
Linear CDE. In S4, $\omega^{\text{X}}_{t}=t$, while
$\xi^{\text{X}}_{t}=\int_{0}^{t}X_{s}ds$. In Mamba,
$\omega^{\text{X}}_{t}=\int_{0}^{t}\sigma(\tilde{\alpha}X_{s}+\tilde{\beta})ds$,
while
$\xi^{\text{X}}_{t}=\int_{0}^{t}\sigma(\tilde{\alpha}X_{s}+\tilde{\beta})X_{s}ds$.
As we will see in Sec. 4, the input dependency of $\omega^{\text{X}}_{t}$
allows Mamba to provably go beyond input filtering (S4), achieving higher
reasoning power compared to S4: here, the hidden state of Mamba (one-
dimensional) is updated only if the input signal is bigger than one in value.
This is an example of input selectivity, see discussion in (Gu & Dao, 2023).

##  4 Expressivity of Linear CDEs

Having established the connection between SSMs and Linear CDEs, we now provide
an explicit characterisation of their uniform closure, i.e. a description of
all the functions from compact subsets of $\mathbb{X}$ to $\mathbb{R}$ that
can be uniformly approximated at an arbitrary precision by a Linear CDE of the
form given in Eqn. (6).

###  4.1 Characterization of the closure

For any path $\omega\in C_{1,0}([0,1],\mathbb{R}^{d_{\omega}})$ and any sub-
interval $[s,t]\subset[0,1]$, we denote by $\omega_{[s,t]}\in
C_{1,0}([0,1],\mathbb{R}^{d_{\omega}})$ the following path

$\omega_{[s,t]}(u)=\begin{cases}0&\text{if }u<s\\\
\omega_{u}-\omega_{s}&\text{if }u\in[s,t]\\\ \omega_{t}-\omega_{s}&\text{if
}u>t.\end{cases}$

######  Theorem 4.1.

Consider continuous gates $\omega,\xi$ such that $\omega^{\text{X},1}_{t}=t$
and $\omega^{\text{X},2}_{t}=t^{2}$ 888 These assumptions are of technical
nature and can be relaxed at the cost of talking about _tree-like_ equivalence
of paths _cf._ (Hambly & Lyons, 2010). $\omega^{\text{X},2}_{t}=t^{2}$ not
needed for path-to-point tasks.. Let $\mathbb{K}\subset\mathbb{X}$ be a
compact subset. Then, the uniform closure of the Linear CDE model in (6) over
$\mathbb{K}\times[0,1]$ is given by the following set of functionals

$\left\\{(X,t)\mapsto\Psi(\omega^{\text{X}}_{[0,t]})+\int_{0}^{t}\Phi(\omega^{\text{X}}_{[s,t]})\cdot
d\xi^{\text{X}}_{s}\right\\}$ (9)

where $\cdot$ is the scalar product on $\mathbb{R}^{d_{\xi}}$, and where

$\Psi:C_{1,0}([0,1],\mathbb{R}^{d_{\omega}})\to\mathbb{R},\quad\Phi:C_{1,0}([0,1],\mathbb{R}^{d_{\xi}})\to\mathbb{R}^{d_{\xi}}$

are generic continuous functions.

If the matrices $A_{1},...,A_{d_{\omega}}$ are constrained to be diagonal, as
it is often the case in practice, the requirements
$\omega^{\text{X},1}_{t}=t$, $\omega^{\text{X},2}_{t}=t^{2}$ can be dropped
and the closure reduces to

$\left\\{(X,t)\mapsto\psi(\omega^{\text{X}}_{t})+\int_{0}^{t}\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}\right\\}$ (10)

for continuous $\psi:\mathbb{R}^{d_{\omega}}\to\mathbb{R}$ and
$\phi:\mathbb{R}^{d_{\omega}}\to\mathbb{R}^{d_{\xi}}$.

All proofs can be found in the Appendix.

######  Remark 4.2.

This result can be seen as a generalization of the _Universal Approximation
for Linear RNNs_ presented by Li et al. (2022b)[Thm. 7] for generic gates
$\omega,\xi$. In fact in their setting $Z_{0}=0$ with gates set as in (7)
family (9) reduces to linear input filterings given by convolutions

$\left\\{(X,t)\mapsto\int_{0}^{t}\rho(t-s)\cdot X_{s}ds\right\\}$

######  Remark 4.3.

The specific restriction of $\omega$ to subsets of $[0,1]$ is a crucial part
of (9). The family of approximable maps _does not_ include _all_ path-to-path
causal999A _causal_ map is one which does not ”look in the future” _cf._
Appendix D. functions $t\mapsto Y_{t}^{\text{X}}$ but a subset of them, of
type $t\mapsto Y_{t}^{\text{X}}:=\Psi(\omega^{\text{X}}_{[0,t]})$, satisfying
the specific _time-homogeneity_ specified by the form of the restriction, akin
to that in (Li et al., 2022b).

###  4.2 Signature expansion

To study expressivity of these generalized SSMs (Linear CDEs), it will be
convenient to introduce the so-called _signature transform_ (Lyons et al.,
2007; Kidger et al., 2019; Fermanian et al., 2023), a classical path-transform
from stochastic analysis. The main reason for doing so is that, as a simple
consequence of the Stone-Weirestrass theorem, linear functionals on the
signature provide the essential building blocks (analogous to monomials on
Euclidean spaces) to approximate continuous functions on path space.

Consider a path $\omega\in C_{1,0}([0,1];\mathbb{R}^{d_{\omega}})$ and define
as $\mathbb{W}_{d_{\omega}}$ the set of _words_ (_i.e._ ordered sequences) in
the alphabet $\\{1,\dots,d_{\omega}\\}$ 101010So when we write
$I\in\mathbb{W}_{d_{\omega}}$ we mean $I=i_{1}i_{2}\cdots i_{M}$ for some
integer $M\geq 0$ and letters $i_{m}\in\\{1,\dots,d_{\omega}\\}$, then $Ii$
will be the word $i_{1}i_{2}\cdots i_{M}i$ for
$i\in\\{1,\dots,d_{\omega}\\}$.. The signature transform is the following
infinite collection of scalar iterated integrals

$\text{Sig}(\omega)_{s,t}:=\left(\text{Sig}(\omega)_{s,t}^{(I)}\right)_{I\in\mathbb{W}_{d_{\omega}}}\in
l^{2}(\mathbb{W}_{d_{\omega}})$

where

$\text{Sig}(\omega)_{s,t}^{(I)}:=\int_{s<u_{1}<...<u_{n}<t}\dot{\omega}_{u_{1}}^{(i_{1})}...\dot{\omega}_{u_{n}}^{(i_{n})}du_{1}...du_{n}.$

We refer the interested reader to Appendix A for additional details and
references on the signature. A classical result from rough path theory states
that a Linear CDE can be expanded explicitly as an (infinite) linear
combination of terms in the signature of the driving path. Next, we specialize
this result to the case of Linear CDEs given by Eqn. (6).

######  Proposition 4.4.

For any choice of matrices $A_{1},...,A_{d_{\omega}}$ and $B$, the unique
solution to

$dZ^{\text{X}}_{t}=\sum_{i=1}^{d_{\omega}}A_{i}Z^{\text{X}}_{t}d\omega^{\text{X},i}_{t}+Bd\xi^{\text{X}}_{t},\quad
Z^{\text{X}}_{0}=Z_{0}\in\mathbb{R}^{N}$

is given by

$\displaystyle Z^{\text{X}}_{t}=$
$\displaystyle\sum_{I\in\mathbb{W}_{d_{\omega}}}A_{I}Z_{0}\text{Sig}(\omega^{\text{X}})_{0,t}^{(I)}$
(11)
$\displaystyle+\sum_{i=1}^{d_{\xi}}\sum_{I\in\mathbb{W}_{d_{\omega}}}A_{I}B_{i}\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}^{(I)}d\xi^{\text{X},i}_{s}\in\mathbb{R}^{N}$

where we used the notation $A_{I}:=A_{i_{n}}...A_{i_{1}}$.

Notice that the previous result _does not_ rely on any assumptions on the
nature of $Z_{0}$, $A_{i}$, and $B$; for any such choice the result is a
_time-independent linear map_ on a _feature vector_

$T(X)_{0,t}:=\left(\text{Sig}(\omega^{\text{X}})_{0,t}^{(I)},\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}^{(I)}d\xi^{\text{X},i}_{s}\right)_{(I,i)}$

which is a subsequence of
$\text{Sig}((\omega^{\text{X}},\xi^{\text{X}}))_{0,t}\in
l^{2}(\mathbb{W}_{d_{\omega}+d_{\xi}})$, and where the index $(I,i)$ runs over
$\mathbb{W}_{d_{\omega}}\times\\{1,...,d_{\xi}\\}$.

###  4.3 Randomised Linear CDEs

It turns out that the same space of functionals in the closure (9) of a Linear
CDE can be induced, with high probability, by sampling the matrices
$A_{1},...,A_{d_{\omega}},B$ and $Z_{0}$ at random according to standard ML
practices (LeCun et al., 2012), as stated in the following result:

######  Theorem 4.5.

For any compact subset $\mathbb{K}\subset\mathbb{X}$ and for any functional
$F:\mathbb{K}\times[0,1]\to\mathbb{R}$ of the form given in Eqn. (9), the
following holds

$\displaystyle\lim\limits_{N\to\infty}\mathbb{P}\Big{[}\Big{\\{}$
$\displaystyle\exists v\in\mathbb{R}^{N}\quad\text{such that}$
$\displaystyle\sup\limits_{(X,t)\in\mathbb{K}\times[0,1]}|F(X,t)-\langle
v,Z^{\text{X}}_{t}\rangle|\leq\epsilon\Big{\\}}\Big{]}=1$

where the matrices $A_{1},...,A_{d_{\omega}}$ and $B$ defining $Z^{X}$ are
sampled at random as

$[A_{j}]_{n,n^{\prime}}\overset{\text{iid}}{\sim}\mathcal{N}(0,\frac{1}{N})\quad[Z]_{n},[B]_{n,j}\overset{\text{iid}}{\sim}\mathcal{N}(0,1).$

In particular, Thm. 4.5 implies that only the final readout $v$ needs to be
trained, while the randomly initialised matrices $A_{1},...,A_{d_{\omega}}$
and $B$ can be left untrained (_cf._ Sec. 6). This is a similar mechanism to
the paradigm advocated in reservoir computing (Cuchiero et al., 2021b;
Lukoveviius & Jaeger, 2009).

######  Remark 4.6.

It can be proved, using the results by Dubach & Peled (2021), that the
sampling measure does not have to be Gaussian if it satisfies certain moment
requirements.

The core argument behind the proof of Thm. 4.5 consists of exhibiting _almost-
orthogonal_ vectors trough random linear maps, and then using these as a
pseudo-basis of vectors on which to mimic the dynamics of the feature map
$T(X)_{0,t}$. It then suffices to bound the error made by this approximate
approach, which is proved to disappear as the dimension $N$ increases.

###  4.4 S4 as a special case

In case $\omega^{\text{X}}_{t}=t$ and
$\xi^{\text{X}}_{t}=\int_{0}^{t}X_{s}ds$, like in S4, one has $d_{\omega}=1$.
Thus, $\mathbb{W}_{d_{\omega}}=\mathbb{N}$ and the signature reduces to

$\text{Sig}(\omega^{\text{X}})_{s,t}:=\left(\text{Sig}(\omega^{\text{X}})_{s,t}^{(k)}\right)_{k\in\mathbb{N}}$

where

$\text{Sig}(\omega^{\text{X}})_{s,t}^{(k)}=\frac{(t-s)^{k}}{k!}.$

This in turns implies the following expression for $Z^{X}$

$Z_{t}^{\text{X}}=\sum_{i=1}^{d_{\xi}}\int_{0}^{t}e^{A(t-s)}B_{i}X^{i}_{s}ds,$

and the corresponding feature vector $T$ reads

$T(X)_{0,t}=\left(\int_{0}^{t}\frac{(t-s)^{k}}{k!}X^{i}_{s}ds\right)_{(k,i)}.$

where the index runs over $\mathbb{N}\times\\{1,...,d_{\xi}\\}$. As a result,
linear maps on $T$ are of the type

$\int_{0}^{t}p(t-s)\cdot X_{s}ds$

for polynomials $p^{1},\dots,p^{d}$, which reconciles our framework with the
results obtained by Li et al. (2022b).

It is evident from this discussion that the classical choice of input-
independent $\omega$ (i.e. $\omega^{\text{X}}_{t}=t$) _precludes_ the use of
higher order statistics of $X$.

##### Architectural choices

The matrices $A_{1},...,A_{d_{\omega}}\in\mathbb{R}^{N\times N}$ defining the
Linear CDE (6) are generally dense matrices. However, at the core of the
efficient GPU-efficient computation strategy of S4 and Mamba is the need for
diagonal recurrences (see speed comparisons in (Orvieto et al., 2023b)).
Indeed, dense matrix multiplication inevitably takes the computational cost of
the forward pass to $O(N^{2}L)$ complexity, where $L$ is the sequence length.
Instead, using diagonal recurrences results in a $\mathcal{O}(LN)$ complexity.

Motivated by the efficiency requirements in S4 and Mamba, in the next section,
we discuss the question of whether this choice of diagonal restricts the
family of functionals that one can learn.

###  4.5 The Diagonal Case

If $A_{i}:=\operatorname{diag}(v_{i})$, due to commutativity of diagonal
matrices, one has that for any permutation $\sigma(I)$ of a word $I$ the
equality $A_{I}=A_{\sigma(I)}$ holds. This means that a linear functional on
$Z_{t}^{\text{X}}$ such as (11) can fundamentally only see the symmetric part
of $\text{Sig}(\omega^{\text{X}})_{s,t}$, which is just the tensor exponential

$e^{\otimes\int_{s}^{t}d\omega^{\text{X}}_{r}}:=\left(\prod_{i=1}^{d_{\omega}}\frac{(\omega^{\text{X},i}_{t}-\omega^{\text{X},i}_{s})^{k_{i}}}{k_{i}!}\right)_{\boldsymbol{k}\in\mathbb{N}^{d_{\omega}}},$
(12)

and as such does not capture higher order channel combinations (_cf._ See
Sect. 6 for empirical validation). In fact the explicit solution a can be
written as

$Z_{t}^{\text{X}}=e^{\operatorname{diag}(V\omega^{\text{X}}_{t})}Z_{0}+\int_{0}^{t}e^{\operatorname{diag}(V(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s}))}Bd\xi^{\text{X}}_{s}$
(13)

where $V:=\left[v_{1}|\cdots|v_{d_{\omega}}\right]\in\mathbb{R}^{N\times
d_{\omega}}$. The closure of linear functionals on solutions of (13) is
characterized as the following set of functionals

$\left\\{(X,t)\mapsto\psi(\omega^{\text{X}}_{t})+\int_{0}^{t}\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}\right\\}$ (14)

for $\psi\in C^{0}(\mathbb{R}^{d_{\omega}};\mathbb{R})$ and $\phi\in
C^{0}(\mathbb{R}^{d_{\omega}};\mathbb{R}^{d_{\xi}})$.

##### Efficiency and Stability.

On top of efficiency, an important feature of selective SSMs, crucial for
long-range reasoning (see discussion in (Orvieto et al., 2023b)) is their
stability in a dynamical system sense: eigenvalues of $\bar{A}$ for those
discrete recurrences always have absolute value bounded by $1$. Both S4 and
Mamba achieve this by restricting the sign of the diagonal components of their
recurrent matrix $A$ with positive nonlinearities such as ReLUs (see Sec. 2).
Under ZOH numerical integration (see again Sec. 2), the resulting discrete-
time $\bar{A}=\exp(\Delta A)$ is guaranteed to be stable. We can apply the
same idea in the general linear diagonal CDE setting (_cf._ Appendix C.1).
Instead, if one works with dense matrices, ensuring stability in numerical
integration during training requires heavy adaptations of the optimizer on top
of higher overall complexity.

##### Expressivity.

Note that the main difference between (9) and (14) is the path-dependence: the
latter take as input just a value or increment of $\omega^{\text{X}}$ while
the maps in $(\ref{eqn:main_F})$ are functions on whole sections of it.
Diagonal selective SSMs (i.e. Mamba111111Instead, expressivity of S4 is
unaffected by diagonality in the recurrence, see results above and in (Li et
al., 2022b).) are thus fundamentally weaker than their non-diagonal
counterparts, as they can at most capture the symmetric part of
$\omega^{\text{X}}$’s signature and its integrals against $d\xi^{\text{X}}$
(see Appendix for details).

###  4.6 Chaining Diagonal CDEs

Fortunately it is possible to re-gain expressivity without sacrificing the
computational advantages of diagonal schemes through _chaining_. This means
driving a new linear CDE by the solution of a previous linear CDE, and
repeating this procedure $K$ times. With this procedure, one can recover
signature entries up to depth $K$ with complexity $\mathcal{O}(KLN)$.

######  Proposition 4.7.

Assume a compact input set $\mathbb{X}\subset C_{1,0}([0,1];\mathbb{R}^{d})$.
For any $I\in\mathbb{W}_{d}$ with $|I|\geq 2$ and $\epsilon>0$ there is a
sequence of linear maps $W_{k}\in\mathbb{R}^{N_{k}\times 1}$ and weights for
the following family of _chained_ linear CDEs

$\displaystyle
dZ_{t}^{1,\text{X}}=\sum_{i=1}^{d}A^{(1)}_{i}Z^{1,\text{X}}_{t}dX^{i}_{t}+B^{(1)}d{{X}}_{t},$
$\displaystyle
dZ_{t}^{k+1,\text{X}}=\sum_{i=1}^{d+1}A^{(k+1)}_{i}Z^{k+1,\text{X}}_{t}d\begin{bmatrix}W_{k}Z^{k,\text{X}}\\\
{X}\end{bmatrix}^{i}_{t}$ $\displaystyle+B^{(k+1)}dX_{t},$

with $Z^{k}\in\mathbb{R}^{N_{k}}$, such that for some
$v\in\mathbb{R}^{N_{|I|-1}}$ one has

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|Sig(X)^{(I)}_{0,t}-\langle
v,Z_{t}^{|I|-1,\text{X}}\rangle|\leq\epsilon$ (15)

The intuition behind this result is the following: with a single diagonal
layer it’s possible 121212This is not straightforward since the time in the
integral part of (14) is going ”backwards”! to recover the terms

$\int_{0}^{t}(\omega^{\text{X},i}_{s}-\omega^{\text{X},i}_{0})d\xi^{\text{X},j}_{s}$

which are just length $2$ terms from
$\text{Sig}((\omega^{\text{X}},\xi^{\text{X}}))_{0,t}$. If we pass these terms
as $\omega$ in another layer then we can obtain a length $3$ term from
$\text{Sig}((\omega^{\text{X}},\xi^{\text{X}}))_{0,t}$, and so on.

######  Remark 4.8.

The structure of the chaining in Prop. 4.7 seems quite restrictive, in
particular it’s not clear to which extent gates which are non-linear in the
input $X$ allow for such a construction. In the Appendix we address this issue
in the simple but important case
$d\omega^{\text{X}}_{t}=\text{ReLU}(WX_{t}+B)dt$, where we show that no
information is lost and numerical stability can be enforced.

##  5 Path-to-Path Learning

Up to now we have been dealing with a limited class of path-to-path maps
essentially built by functionals of type
$(X,t)\mapsto\langle\alpha,T(X)_{s,t}\rangle$ for a fixed linear map $\alpha$.
Crucial for modern machine learning are general continuous path-to-path models
of type $C_{0,1}([0,1];\mathbb{R}^{d})\to C_{0,1}([0,1];\mathbb{R})$. As shown
in (Orvieto et al., 2023a), classical SSMs followed by a non-linearity and a
feed-forward network are universal path-to-path when the inputs are piecewise
linear paths on fixed discretizations (_i.e._ universal on sequences).

Orvieto et al. (2023a) discuss an important feature of S4, which we already
presented in previous sections: its action on the input is a simple
convolution with fixed (independent of the input) parameters. For this exact
reason, the construction of (Orvieto et al., 2023a) defers all non-linear
computation (reasoning) to the multi-layer perceptron (MLP) acting on the
linear recurrence output, which is simply providing in their setting a loss-
less compression of the inputs – with no added reasoning.

$C_{1,0}([0,1];\mathbb{R}^{d})$$C_{1,0}([0,1];\mathbb{R}^{d^{\prime}})$$\mathbb{R}^{L+1}$$\mathbb{R}^{L^{\prime}}$$\mathbb{R}^{L^{\prime}+1}$MLPMLPOperatorInterpolationLinear$\left(S4_{t}^{X}\right)$Linear$\left(CDE_{t}^{X}\right)$
Figure 2: Square: (Orvieto et al., 2023a)’s approach for path-to-path
universality. Triangle: our approach.

In our setting, we instead characterized the processing power of input-
controlled (dense or diagonal) SSMs precisely, showing that it greatly
surpasses linear filtering. For this reason, the computational burden for an
MLP action on a general linear CDE, unlocking path-to-path learning, would be
greatly diminished and its actual function reduced to a time-consistent
interpolation of already good path-to-point approximations. This method is
robust to different input discretization schemes and does not offload all the
complexity to the network which follows the SSM (_cf._ Figure 2).

######  Proposition 5.1.

Fix a compact set $\mathbb{K}\subseteq\mathbb{X}$ and continuous $\omega,\xi$
with $\omega^{\text{X},1}_{t}\equiv t$. Then for all $\epsilon>0$ and all
_causal_ continuous mapping
$G:C_{1,0}([0,1],\mathbb{R}^{d_{\omega}})\times[0,1]\to\mathbb{R}$ there exist
an integer $N\geq 0$, some Feed Forward neural network
$F:\mathbb{R}^{N}\to\mathbb{R}$, and parameters
$Z_{0}\in\mathbb{R}^{N},A_{i}\in\mathbb{R}^{N\times N},B\in\mathbb{R}^{N\times
d_{\xi}}$ such that

$\sup\limits_{(X,t)\in\mathbb{K}\times[0,1]}|F(Z^{\text{X}}_{t})-G(\omega^{\text{X}},t)|<\epsilon$
(16)

Actually, $F$ in the above result does not have to be a neural network, it
suffices for it to be able to interpolate linear maps in a time-consistent
manner _cf._ Appendix D.

##  6 Empirical Validation

A variation on the toy dataset introduced in (Walker et al., 2024) is used to
empirically validate our theoretical results. We use two datasets of $100,000$
sample paths each, with dimensions $2$ and $3$ respectively. In both datasets,
paths are defined on $100$ regularly spaced time-steps between $t=0$ and
$t=1$. The change in each channel at each time point is an independent sample
from a standard Normal distribution rounded to the nearest integer. The
datasets are then normalised to range between $-1$ and $1$. The aim on both
datasets is to predict specific terms in the anti-symmetric part of the
signature. For the $2$ dimensional dataset the prediction is an area integral
and for the $3$ dimensional a volume integral given, respectively, by

$\int_{0}^{1}\int_{0}^{v}dX^{1}_{u}dX^{2}_{v},\quad\int_{0}^{1}\int_{0}^{w}\int_{0}^{v}dX^{1}_{u}dX^{2}_{v}dX^{3}_{w}.$

We consider five models:

  1. 1.

A S5 or Mamba recurrence with linear readout.

  2. 2.

Two stacked S5 or Mamba recurrences with a linear mixing layer in-between, and
the final state of the second layer fed into a linear readout.

  3. 3.

A linear NCDE with gates $\omega^{\text{X}}_{t}=\xi^{\text{X}}_{t}=(t,X_{t})$
followed by a linear readout.

All state space models have trainable matrices in their recurrences, whereas
the linear NCDE is using fixed matrices. All of the models use a hidden
dimension of $256$, with the state space models using a state dimension of
$256$. The state space models are trained using batch gradient descent with a
batch size of $32$ and Adam with a learning rate of $3\times 10^{-5}$. Results
are plotted in Fig. 3.

Figure 3: Comparison of Linear CDE, Mamba and S5 on anti-symmetric signature
prediction tasks. As suggested by the theory Mamba struggles to immediately
capture these high order statistics, but performance improves with _chaining_.
On the other hand S5 does not learn such non-linear features even after
training and chaining.

The output from the linear NCDE’s recurrence is obtained using an adaptive ODE
solver, Tsit5, with an absolute and relative tolerance of $1\times 10^{-2}$.
The linear NCDEs linear layer is obtained by ordinary least squares.

##  7 Conclusions

In this paper we have considered a family of models, defined by gating
functions as solutions to linear CDEs, which extends both classical and modern
SSM architectures.

Using analytical tools from _Rough Paths_ theory we have characterized the
uniform closure of these models generalizing the results of (Li et al.,
2022b), shedding light on the expressive advantages of input-controlled
transition dynamics, which allow to capture high order statistics of the input
as opposed to just the linear ones extracted by convolutions.

We point out how the full expressive range is already captured by generic
models, and how more efficient computational structures, such as imposing
diagonality, weaken these expressive capabilities. A remedy to this loss is
presented in the _chaining_ of these models.

Finally we show how the substitution of the linear readout with an MLP allows
to approximate general path-to-path functions without, in contrast to the S4
case, offloading all the complexity to the neural network.

##  8 Acknowledgements

Nicola Muca Cirone is supported by the EPSRC Centre for Doctoral Training in
Mathematics of Random Systems: Analysis, Modelling and Simulation
(EP/S023925/1). Antonio Orvieto acknowledges the financial support of the
Hector Foundation. Benjamin Walker was funded by the Hong Kong Innovation and
Technology Commission (InnoHK Project CIMDA). Terry Lyons was funded in part
by the EPSRC [grant number EP/S026347/1], in part by The Alan Turing Institute
under the EPSRC grant EP/N510129/1, the Data Centric Engineering Programme
(under the Lloyd’s Register Foundation grant G0095), the Defence and Security
Programme (funded by the UK Government) and the Office for National Statistics
& The Alan Turing Institute (strategic partnership) and in part by the Hong
Kong Innovation and Technology Commission (InnoHK Project CIMDA).

## References

  * Arribas et al. (2020) Arribas, I. P., Salvi, C., and Szpruch, L.  Sig-sdes model for quantitative finance.  In _Proceedings of the First ACM International Conference on AI in Finance_ , pp. 1–8, 2020.
  * Barron (1993) Barron, A. R.  Universal approximation bounds for superpositions of a sigmoidal function.  _IEEE Transactions on Information theory_ , 39(3):930–945, 1993.
  * Berlinet & Thomas-Agnan (2011) Berlinet, A. and Thomas-Agnan, C.  _Reproducing Kernel Hilbert Spaces in Probability and Statistics_.  Springer US, 2011.  ISBN 9781441990969.  URL https://books.google.co.uk/books?id=bX3TBwAAQBAJ.
  * Boyd & Chua (1985) Boyd, S. and Chua, L.  Fading memory and the problem of approximating nonlinear operators with volterra series.  _IEEE Transactions on circuits and systems_ , 32(11):1150–1161, 1985.
  * Chen (1958) Chen, K.-T.  Integration of paths–a faithful representation of paths by noncommutative formal power series.  _Transactions of the American Mathematical Society_ , 89(2):395–407, 1958.  ISSN 00029947.  URL http://www.jstor.org/stable/1993193.
  * Chevyrev & Kormilitzin (2016) Chevyrev, I. and Kormilitzin, A.  A primer on the signature method in machine learning.  _arXiv preprint arXiv:1603.03788_ , 2016.
  * Cho et al. (2014) Cho, K., Van Merriënboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., and Bengio, Y.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  _arXiv preprint arXiv:1406.1078_ , 2014.
  * Cirone et al. (2023) Cirone, N. M., Lemercier, M., and Salvi, C.  Neural signature kernels as infinite-width-depth-limits of controlled resnets, 2023.
  * Cochrane et al. (2021) Cochrane, T., Foster, P., Chhabra, V., Lemercier, M., Lyons, T., and Salvi, C.  Sk-tree: a systematic malware detection algorithm on streaming trees via the signature kernel.  In _2021 IEEE international conference on cyber security and resilience (CSR)_ , pp. 35–40. IEEE, 2021.
  * Cuchiero et al. (2021a) Cuchiero, C., Gonon, L., Grigoryeva, L., Ortega, J.-P., and Teichmann, J.  Expressive power of randomized signature.  In _The Symbiosis of Deep Learning and Differential Equations_ , 2021a.
  * Cuchiero et al. (2021b) Cuchiero, C., Gonon, L., Grigoryeva, L., Ortega, J.-P., and Teichmann, J.  Discrete-time signatures and randomness in reservoir computing.  _IEEE Transactions on Neural Networks and Learning Systems_ , Forthcoming, 04 2021b.  doi: 10.1109/TNNLS.2021.3076777.
  * Dasgupta & Gupta (2003) Dasgupta, S. and Gupta, A.  An elementary proof of a theorem of johnson and lindenstrauss.  _Random Structures & Algorithms_, 22, 2003.  URL https://api.semanticscholar.org/CorpusID:10327785.
  * De et al. (2024) De, S., Smith, S. L., Fernando, A., Botev, A., Cristian-Muraru, G., Gu, A., Haroun, R., Berrada, L., Chen, Y., Srinivasan, S., Desjardins, G., Doucet, A., Budden, D., Teh, Y. W., Pascanu, R., Freitas, N. D., and Gulcehre, C.  Griffin: Mixing gated linear recurrences with local attention for efficient language models, 2024.
  * Dosovitskiy et al. (2020) Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Houlsby, N., Gelly, S., Zhang, X., and Uszkoreit, J.  An image is worth 16x16 words: Transformers for image recognition at scale.  _arXiv preprint arXiv:2010.11929_ , 2020.
  * Dubach & Peled (2021) Dubach, G. and Peled, Y.  On words of non-Hermitian random matrices.  _The Annals of Probability_ , 49(4):1886 – 1916, 2021.  doi: 10.1214/20-AOP1496.  URL https://doi.org/10.1214/20-AOP1496.
  * Fermanian (2020) Fermanian, A.  Embedding and learning with signatures, 2020.
  * Fermanian et al. (2023) Fermanian, A., Lyons, T., Morrill, J., and Salvi, C.  New directions in the applications of rough path theory.  _IEEE BITS the Information Theory Magazine_ , 2023.
  * Friz & Victoir (2010) Friz, P. K. and Victoir, N. B.  _Multidimensional Stochastic Processes as Rough Paths: Theory and Applications_.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2010.  doi: 10.1017/CBO9780511845079.
  * Fu et al. (2022) Fu, D. Y., Dao, T., Saab, K. K., Thomas, A. W., Rudra, A., and Re, C.  Hungry hungry hippos: Towards language modeling with state space models.  In _The Eleventh International Conference on Learning Representations_ , 2022.
  * Goel et al. (2022) Goel, K., Gu, A., Donahue, C., and Ré, C.  It’s raw! audio generation with state-space models.  _International Conference on Machine Learning_ , 2022.
  * Gu & Dao (2023) Gu, A. and Dao, T.  Mamba: Linear-time sequence modeling with selective state spaces, 2023.
  * Gu et al. (2020) Gu, A., Dao, T., Ermon, S., Rudra, A., and Ré, C.  Hippo: Recurrent memory with optimal polynomial projections.  _Advances in neural information processing systems_ , 33:1474–1487, 2020.
  * Gu et al. (2021) Gu, A., Goel, K., and Re, C.  Efficiently modeling long sequences with structured state spaces.  In _International Conference on Learning Representations_ , 2021.
  * Gu et al. (2022) Gu, A., Gupta, A., Goel, K., and Ré, C.  On the parameterization and initialization of diagonal state space models.  _arXiv preprint arXiv:2206.11893_ , 2022.
  * Hambly & Lyons (2010) Hambly, B. and Lyons, T.  Uniqueness for the signature of a path of bounded variation and the reduced path group.  _Annals of Mathematics_ , pp. 109–167, 2010.
  * Hanson & Raginsky (2020) Hanson, J. and Raginsky, M.  Universal simulation of stable dynamical systems by recurrent neural nets.  In _Learning for Dynamics and Control_ , pp. 384–392. PMLR, 2020.
  * Hochreiter & Schmidhuber (1997) Hochreiter, S. and Schmidhuber, J.  Long short-term memory.  _Neural computation_ , 1997.
  * Hoglund et al. (2023) Hoglund, M., Ferrucci, E., Hernandez, C., Gonzalez, A. M., Salvi, C., Sanchez-Betancourt, L., and Zhang, Y.  A neural rde approach for continuous-time non-markovian stochastic control problems.  _arXiv preprint arXiv:2306.14258_ , 2023.
  * Issa et al. (2023) Issa, Z., Horvath, B., Lemercier, M., and Salvi, C.  Non-adversarial training of neural sdes with signature kernel scores.  _Advances in Neural Information Processing Systems_ , 2023.
  * Katsch (2023) Katsch, T.  Gateloop: Fully data-controlled linear recurrence for sequence modeling, 2023.
  * Kidger (2022) Kidger, P.  On neural differential equations, 2022.
  * Kidger et al. (2019) Kidger, P., Bonnier, P., Perez Arribas, I., Salvi, C., and Lyons, T.  Deep signature transforms.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Kidger et al. (2020) Kidger, P., Morrill, J., Foster, J., and Lyons, T.  Neural controlled differential equations for irregular time series.  _Advances in Neural Information Processing Systems_ , 33:6696–6707, 2020.
  * Korsky & Berwick (2019) Korsky, S. A. and Berwick, R. C.  On the computational power of rnns.  _arXiv preprint arXiv:1906.06349_ , 2019.
  * LeCun et al. (2012) LeCun, Y. A., Bottou, L., Orr, G. B., and Müller, K.-R.  _Efficient BackProp_ , pp. 9–48.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.  ISBN 978-3-642-35289-8.  doi: 10.1007/978-3-642-35289-8˙3.  URL https://doi.org/10.1007/978-3-642-35289-8_3.
  * Lemercier et al. (2021) Lemercier, M., Salvi, C., Damoulas, T., Bonilla, E. V., and Lyons, T.  Distribution regression for sequential data, 2021.
  * Li et al. (2022a) Li, Y., Cai, T., Zhang, Y., Chen, D., and Dey, D.  What makes convolutional models great on long sequence modeling?  _arXiv preprint arXiv:2210.09298_ , 2022a.
  * Li et al. (2022b) Li, Z., Han, J., Weinan, E., and Li, Q.  Approximation and optimization theory for linear continuous-time recurrent neural networks.  _J. Mach. Learn. Res._ , 23:42–1, 2022b.
  * Lu et al. (2023) Lu, C., Schroecker, Y., Gu, A., Parisotto, E., Foerster, J., Singh, S., and Behbahani, F.  Structured state space models for in-context reinforcement learning.  _Advances in Neural Information Processing Systems_ , 2023.
  * Lukoveviius & Jaeger (2009) Lukoveviius, M. and Jaeger, H.  Reservoir computing approaches to recurrent neural network training.  _Comput. Sci. Rev._ , 3:127–149, 2009.  URL https://api.semanticscholar.org/CorpusID:554006.
  * Lyons & McLeod (2024) Lyons, T. and McLeod, A. D.  Signature methods in machine learning, 2024.
  * Lyons et al. (2007) Lyons, T. J., Caruana, M., and Lévy, T.  _Differential equations driven by rough paths_.  Springer, 2007.
  * Martin & Cundy (2017) Martin, E. and Cundy, C.  Parallelizing linear recurrent neural nets over sequence length.  _arXiv preprint arXiv:1709.04057_ , 2017.
  * Morrill et al. (2021) Morrill, J., Salvi, C., Kidger, P., and Foster, J.  Neural rough differential equations for long time series.  In _International Conference on Machine Learning_ , pp. 7829–7838. PMLR, 2021.
  * Nguyen et al. (2022) Nguyen, E., Goel, K., Gu, A., Downs, G. W., Shah, P., Dao, T., Baccus, S. A., and Ré, C.  S4nd: Modeling images and videos as multidimensional signals using state spaces.  _Advances in Neural Information Processing Systems_ , 2022.
  * Orvieto et al. (2023a) Orvieto, A., De, S., Gulcehre, C., Pascanu, R., and Smith, S. L.  On the universality of linear recurrences followed by nonlinear projections.  _arXiv preprint arXiv:2307.11888_ , 2023a.
  * Orvieto et al. (2023b) Orvieto, A., Smith, S. L., Gu, A., Fernando, A., Gulcehre, C., Pascanu, R., and De, S.  Resurrecting recurrent neural networks for long sequences.  _arXiv preprint arXiv:2303.06349_ , 2023b.
  * Peng et al. (2023) Peng, B., Alcaide, E., Anthony, Q., Albalak, A., Arcadinho, S., Cao, H., Cheng, X., Chung, M., Grella, M., GV, K. K., et al.  Rwkv: Reinventing rnns for the transformer era.  _arXiv preprint arXiv:2305.13048_ , 2023.
  * Salvi et al. (2021a) Salvi, C., Cass, T., Foster, J., Lyons, T., and Yang, W.  The signature kernel is the solution of a goursat pde.  _SIAM Journal on Mathematics of Data Science_ , 3(3):873–899, 2021a.  doi: 10.1137/20M1366794.  URL https://doi.org/10.1137/20M1366794.
  * Salvi et al. (2021b) Salvi, C., Lemercier, M., Cass, T., Bonilla, E. V., Damoulas, T., and Lyons, T. J.  Siggpde: Scaling sparse gaussian processes on sequential data.  In _International Conference on Machine Learning_ , pp. 6233–6242. PMLR, 2021b.
  * Salvi et al. (2021c) Salvi, C., Lemercier, M., Liu, C., Horvath, B., Damoulas, T., and Lyons, T.  Higher order kernel mean embeddings to capture filtrations of stochastic processes.  _Advances in Neural Information Processing Systems_ , 34:16635–16647, 2021c.
  * Salvi et al. (2022) Salvi, C., Lemercier, M., and Gerasimovics, A.  Neural stochastic pdes: Resolution-invariant learning of continuous spatiotemporal dynamics.  _Advances in Neural Information Processing Systems_ , 35:1333–1344, 2022.
  * Siegelmann & Sontag (1992) Siegelmann, H. T. and Sontag, E. D.  On the computational power of neural nets.  In _Proceedings of the fifth annual workshop on Computational learning theory_ , pp. 440–449, 1992.
  * Smith et al. (2023) Smith, J. T. H., Warrington, A., and Linderman, S. W.  Simplified state space layers for sequence modeling, 2023.
  * Sun et al. (2023) Sun, Y., Dong, L., Huang, S., Ma, S., Xia, Y., Xue, J., Wang, J., and Wei, F.  Retentive network: A successor to transformer for large language models, 2023.
  * Tallec & Ollivier (2018) Tallec, C. and Ollivier, Y.  Can recurrent neural networks warp time?, 2018.
  * Tay et al. (2020) Tay, Y., Dehghani, M., Abnar, S., Shen, Y., Bahri, D., Pham, P., Rao, J., Yang, L., Ruder, S., and Metzler, D.  Long range arena: A benchmark for efficient transformers.  In _International Conference on Learning Representations_ , 2020.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  _Advances in Neural Information Processing Systems_ , 2017.
  * Walker et al. (2024) Walker, B., McLeod, A. D., Qin, T., Cheng, Y., Li, H., and Lyons, T.  Log neural controlled differential equations: The lie brackets make a difference, 2024.
  * Wang et al. (2022) Wang, J., Yan, J. N., Gu, A., and Rush, A. M.  Pretraining without attention.  _arXiv preprint arXiv:2212.10544_ , 2022.
  * Wang & Xue (2023) Wang, S. and Xue, B.  State-space models with layer-wise nonlinearity are universal approximators with exponential decaying memory.  _arXiv preprint arXiv:2309.13414_ , 2023.
  * Yang et al. (2023) Yang, S., Wang, B., Shen, Y., Panda, R., and Kim, Y.  Gated linear attention transformers with hardware-efficient training.  _arXiv preprint arXiv:2312.06635_ , 2023.
  * Zucchet et al. (2023) Zucchet, N., Meier, R., Schug, S., Mujika, A., and Sacramento, J.  Online learning of long-range dependencies, 2023.

##  Appendix A Introduction to Signatures

This initial section of the Appendix is devoted to a brief introduction to the
topic of Signature Transform. For more in-depth surveys we suggest the reader
to refer to (Fermanian, 2020; Chevyrev & Kormilitzin, 2016; Lyons & McLeod,
2024).

###  A.1 Intuition - Controlled Differential Equations

In the simplest setting of smooth paths a CDE is a differential equation of
form

$\frac{dZ_{t}}{dt}=F\Big{(}\frac{dX_{t}}{dt},Z_{t}\Big{)},\hskip
10.0ptZ_{0}\in\mathbb{R}^{n}$

where $X:[0,1]\to\mathbb{R}^{d}$ is a known smooth path to which we refer as
_control_ , $Z_{0}$ the known initial condition and $Z:[0,1]\to\mathbb{R}^{n}$
the unknown solution.

The natural generalization is the following: assume to have two spaces
$\mathbb{R}^{d_{x}}$ and $\mathbb{R}^{d_{z}}$, $X\in
C_{1}([0,1];\mathbb{R}^{d_{x}})$, $Z\in C_{1}([0,1];\mathbb{R}^{d_{z}})$,
$F:\mathbb{R}^{d_{z}}\to\mathcal{L}(\mathbb{R}^{d_{x}},\mathbb{R}^{d_{z}})$
and $Z_{0}\in\mathbb{R}^{d_{z}}$. We say that $(Z,X,F,Z_{0})$ satisfy the CDE

$dZ_{t}=F(Z_{t})dX_{t},\quad Z_{0}\in\mathbb{R}^{d_{z}}$

whenever

$Z_{t}=Z_{0}+\int_{0}^{t}F(Z_{s})dX_{s}$

The theory of _Rough Paths_ has its origins in the study of such types of
differential equations and provides a theoretical framework to define and work
in rough settings i.e. when $X$ is not kust BV but even $\alpha$-Hölder for
$\alpha\in(0,1)$ _cf._ (Friz & Victoir, 2010).

Assume thus to have the CDE

$dZ_{t}=\sum_{i=1}^{d_{x}}V_{i}(Z_{t})dX^{i}_{t},\quad
Z_{0}\in\mathbb{R}^{d_{z}}$

for sufficiently regular vector fields $V_{i}$ and $X\in
C_{1}([0,1];\mathbb{R}^{d_{x}})$. Given a smooth
$f:\mathbb{R}^{n}\to\mathbb{R}$, by the change of variable formula (_i.e._
fundamental theorem of calculus) we have

$f(Z_{t})=f(Z_{0})+\sum_{i=1}^{d_{x}}\int_{0}^{t}V_{i}f(Z_{s})dX^{i}_{s}$

where $V_{i}f(z):=df_{y}[V_{i}(z)]$. Iterating this procedure on the
$V_{i}f$s, _i.e._ substituting in the previous equation the analogously
obtained equality

$V_{i}f(Z_{s})=V_{i}f(Z_{0})+\sum_{j=1}^{d_{x}}\int_{0}^{s}V_{j}(V_{i}f)(Z_{u})dX^{j}_{u},$

we get

$f(Z_{t})=f(Z_{0})+\sum_{i=1}^{d}V_{i}f(Z_{0})\int_{0}^{t}dX^{i}_{s}+\sum_{i,j=1}^{d}\int_{0}^{t}\int_{0}^{s}V_{j}V_{i}f(Z_{u})dX_{u}^{j}dX_{s}^{i}$

Keeping with this procedure for $N$ steps we get

$f(Z_{t})=f(Z_{0})+\sum_{k=1}^{N}\sum_{|I|=k}V_{I}f(Z_{0})\idotsint\limits_{s<u_{1}<\cdots<u_{k}<t}dX^{i_{1}}_{u_{1}}\cdots
dX^{i_{k}}_{u_{k}}+R_{N}(t)$

where $I=(i_{1},\dots,i_{k})$ runs trough the multi-indices,
$V_{I}f:=V_{i_{1}}V_{i_{2}}\dots V_{i_{k}}f$ and

$R_{N}(t):=\sum_{|J|=k+1}\hskip
5.0pt\idotsint\limits_{s<u_{1}<\cdots<u_{k+1}<t}V_{J}f(Z_{u_{1}})dX^{j_{1}}_{u_{1}}\cdots
dX^{j_{k+1}}_{u_{k+1}}$

As one can imagine, under reasonable regularity assumptions, the remainder
goes to $0$ as $N\to\infty$ and at the limit

$f(Z_{t})=f(Z_{0})+\sum_{k=1}^{\infty}\sum_{|I|=k}V_{I}f(Z_{0})\idotsint\limits_{s<u_{1}<\cdots<u_{k}<t}dX^{i_{1}}_{u_{1}}\cdots
dX^{i_{k}}_{u_{k}}$

This is a remarkable result: to know the solution $Z_{t}$ to the original CDE
it suffices to know the quantities $V_{I}f$ for all multi-indices and $f$ in
the coordinate maps, together with the iterated integrals

$\text{Sig}(X)^{I}_{s,t}:=\idotsint\limits_{s<u_{1}<\cdots<u_{k}<t}dX^{i_{1}}_{u_{1}}\cdots
dX^{i_{k}}_{u_{k}}.$

This observation is at the core of _Rough Path Analysis_ , the theory can in a
sense be considered an extreme development of it. The collection of iterated
integrals, the _Signature_ , will be the main for our analysis.

In Appendix E we expand and make rigorous the arguments of this section in the
case of affine vector fields.

###  A.2 Basic Definitions

Denote by $(\mathbb{R}^{d})^{\otimes
n}:=\mathbb{R}^{d}\otimes\cdots\otimes\mathbb{R}^{d}$ the tensor product of
$n$ copies $\mathbb{R}^{d}$, set $(\mathbb{R}^{d})^{\otimes 0}:=\mathbb{R}$.
Let $T(\mathbb{R}^{d}):=\bigoplus_{k=0}^{\infty}(\mathbb{R}^{d})^{\otimes k}$
be the tensor algebra equipped with sum and tensor product.

######  Definition A.1.

Let $\\{e_{1},\dots,e_{d}\\}$ be the canonical basis of $\mathbb{R}^{d}$, then

$\\{e_{i_{1}}\otimes\cdots\otimes e_{i_{k}}:(i_{1},\dots,i_{k})\in[d]^{k}\\}$

is a basis of $(\mathbb{R}^{d})^{\otimes k}$. We equip
$(\mathbb{R}^{d})^{\otimes k}$ with the inner product
$\langle\cdot,\cdot\rangle_{(\mathbb{R}^{d})^{\otimes k}}$ defined on basis
elements as

$\langle e_{i_{1}}\otimes\cdots\otimes e_{i_{k}},e_{j_{1}}\otimes\cdots\otimes
e_{j_{k}}\rangle_{(\mathbb{R}^{d})^{\otimes
k}}=\delta_{(i_{1},\dots,i_{k})}^{(j_{1},\dots,j_{k})}$

We extend this product to $T(\mathbb{R}^{d})$ by

$\langle A,B\rangle_{T(\mathbb{R}^{d})}:=\sum_{k=0}^{\infty}\langle
a_{k},b_{k}\rangle_{(\mathbb{R}^{d})^{\otimes k}}$

where $A=(a_{0},a_{1},\dots)$ and $B=(b_{0},b_{1},\dots)$

Note how for any $A,B\in T(\mathbb{R}^{d})$ we have $\langle A\otimes
e_{i},B\otimes e_{j}\rangle_{T(\mathbb{R}^{d})}=\langle
A,B\rangle_{T(\mathbb{R}^{d})}\langle e_{i},e_{j}\rangle_{\mathbb{R}^{d}}$, we
refer to this as to the _coproduct property_.

######  Definition A.2 (Infinite Tensor Algebra).

The infinite tensor algebra is defined as the space
$T((\mathbb{R}^{d})):=\prod_{k=0}^{\infty}(\mathbb{R}^{d})^{\otimes k}$
equipped with the operations $+$ and $\otimes$ which act in the natural
algebraic way; its elements are called _tensor series_.

It is easily seen that $(T((\mathbb{R}^{d})),+,\otimes)$ is an algebra with
unit $\textbf{1}=(1,0,0,\cdots)$ and we can endow it with a natural product
which inherits the coproduct property.

Another point of view could be taken on the definitions of these spaces, one
that we will prefer later on. If we define $\mathbb{W}_{d}$ to be the set of
words in $d$ letters then
$T((\mathbb{R}^{d}))\sim\mathbb{R}^{\mathbb{W}_{d}}$, $T(\mathbb{R}^{d})$ is
the subset of such functions with finite support and

$\langle
A,B\rangle_{T(\mathbb{R}^{d})}=\sum_{I\in\mathbb{W}_{d}}A_{I}B_{I}=\sum_{k=0}^{\infty}\sum_{|I|=k}A_{I}B_{I}$

where $|I|$ is the length of the word $I$. The empty word, the only one with
length $0$, is denoted by $()$ and corresponds to the basis element of
$(\mathbb{R}^{d})^{\otimes 0}$. In this view the tensor product coincides with
concatenation of words accordingly distributed and the closure of
$T(\mathbb{R}^{d})$ with respect to its product is just the $l^{2}$ space
$l^{2}(\mathbb{W}_{d})$.

######  Definition A.3 (Signature).

Given $\gamma\in C_{1,0}([0,1];\mathbb{R}^{d})$ and $s,t\in[0,1]$ s.t. $s\leq
t$, the signature $Sig(\gamma)_{s,t}\in T((\mathbb{R}^{d}))$ of the path
$\gamma$ over $[s,t]$ is defined as

$\text{Sig}(\gamma)_{s,t}:=(1,\int\limits_{s<u_{1}<t}d\gamma_{u_{1}},\hskip
3.0pt\cdots,\idotsint\limits_{s<u_{1}<\cdots<u_{k}<t}d\gamma_{u_{1}}\otimes\cdots\otimes
d\gamma_{u_{k}},\cdots)$ (17)

Equivalently $\text{Sig}(\gamma)_{s,t}$ is that element of
$l^{2}(\mathbb{W}_{d})$ defined recursively on words as

$\text{Sig}(\gamma)_{s,t}^{()}=1,\quad\text{Sig}(\gamma)^{Ij}_{s,t}=\int_{s}^{t}\text{Sig}(\gamma)^{I}_{s,r}d\gamma^{j}_{r}.$
(18)

###  A.3 Notable Results

Here we present some notable results of which we will make use through the
paper. We omit the proofs if they can be easily found in the suggested
references.

The first result is about bounding the norm of Signature entries:

######  Proposition A.4 (Factorial Decay Rate).

Given $\gamma\in C_{1,0}([0,1];\mathbb{R}^{d})$, for all $k\geq 1$ and
$s,t\in[0,1]$ s.t. $s\leq t$ one has

$\left\lVert\hskip
5.0pt\idotsint\limits_{s<u_{1}<\cdots<u_{k}<t}d\gamma_{u_{1}}\otimes\cdots\otimes
d\gamma_{u_{k}}~{}\right\rVert_{(\mathbb{R}^{d})^{\otimes
k}}\leq\frac{\left\lVert\gamma\right\rVert_{1-var,[s,t]}^{k}}{k!}$ (19)

The most important fact about Signature is that it acts as the basis for a
Taylor expansion in path space. In fact just as finite linear combinations of
monomials are dense in the continuous functions with a compact input set,
finite linear combinations of Signature entries are dense in continuous
functions from compact path-spaces:

######  Theorem A.5 (Universal Approximation (Fermanian, 2020)).

Fix $K\subset C_{1,0}([0,1];\mathbb{R}^{d+1})$ compact such that for any
$\gamma\in K$ it holds $\gamma^{1}_{t}=t$. For any $F\in C^{0}(K;\mathbb{R})$
and $\epsilon>0$ there is an integer $N\geq 0$ such that

$\sup\limits_{\gamma\in K}|F(\gamma)-\sum_{|I|\leq
N}\alpha_{I}\text{Sig}(\gamma)^{I}_{0,1}|\leq\epsilon$ (20)

for some finite sequence $(\alpha_{I})_{|I|\leq N}$ of real numbers.

######  Remark A.6.

There is no magic in this result, it is just an application of Stone-
Weiestrass enabled by the rich algebraic structure of iterated integrals,
studied originally in (Chen, 1958).

We will need to restrict some paths to sub-intervals of $[0,1]$ in such a way
to still be able to consider them meaningfully as elements of
$C_{1,0}([0,1];\mathbb{R}^{d})$, this is done in the following way:

######  Definition A.7.

Given any path $\gamma\in C_{1,0}([0,1];\mathbb{R}^{d})$ we define its
restriction on a sub-interval $[s,t]\subseteq[0,1]$ as the path
$\gamma_{[s,t]}\in C_{1,0}([0,1];\mathbb{R}^{d})$ with values

$\gamma_{[s,t]}(r):=\begin{cases}0&\text{ if }r<s\\\
\gamma_{r}-\gamma_{s}&\text{ if }s\leq r\leq t\\\ \gamma_{t}-\gamma_{s}&\text{
if }r>t\end{cases}$ (21)

This definition is such that the following important equation holds

$\text{Sig}(\gamma)_{s,t}=\text{Sig}(\gamma_{[s,t]})_{0,1}$ (22)

With the right augmentation of the paths one can see that the Signature
distinguishes between different sections of paths, this will be crucial for
some of the original results presented in this work.

######  Lemma A.8.

Assume $\omega,\gamma\in C_{1,0}([0,1];\mathbb{R}^{d+2})$ with
$\omega^{1}_{t}=\gamma^{1}_{t}\equiv t$ and
$\omega^{2}_{t}=\gamma^{2}_{t}\equiv t^{2}$. Then

$\text{Sig}(\omega)_{s,t}=\text{Sig}(\gamma)_{s^{\prime},t^{\prime}}\iff\omega_{[s,t]}=\gamma_{[s^{\prime},t^{\prime}]}$
(23)

###### Proof.

The _if_ part is follows from
$\text{Sig}(\gamma)_{s,t}=\text{Sig}(\gamma_{[s,t]})_{0,1}$. For the _only if_
part, If $s=s^{\prime}$ and $t=t^{\prime}$ the statement holds; this is
because if the signatures over the time interval $[s,t]$ of two time-augmented
paths are equal, then the two paths must be equal on $[s,t]$. We now show that
augmenting the path with $t^{2}$ and imposing equality of signatures, implies
$s=s^{\prime}$ and $t=t^{\prime}$, which will in turn allow us to conclude the
proof by the previous remark. Assume
$\text{Sig}(\omega)_{s,t}=\text{Sig}(\gamma)_{s^{\prime},t^{\prime}}$, in
particular we must have

$\displaystyle\int_{s}^{t}d(r^{2})=t^{2}-s^{2}=(t^{\prime})^{2}-(s^{\prime})^{2}=\int_{s^{\prime}}^{t^{\prime}}d(r^{2})$
(24)
$\displaystyle\int_{s}^{t}d(r)=t-s=t^{\prime}-s^{\prime}=\int_{s^{\prime}}^{t^{\prime}}d(r)$
(25)

which reduces to the system

$\begin{cases}t^{2}-s^{2}=(t^{\prime})^{2}-(s^{\prime})^{2}\\\
t-s=t^{\prime}-s^{\prime}\end{cases}\begin{cases}t+s=t^{\prime}+s^{\prime}\\\
t-s=t^{\prime}-s^{\prime}\end{cases}\begin{cases}2t=2t^{\prime}\\\
2s=2s^{\prime}\end{cases}$

Hence it must be true that $t=t^{\prime}$ and $s=s^{\prime}$. ∎

##  Appendix B Expressivity

###  B.1 Model Recap

In the body of the paper we have presented the main results with the
simplified assumption of $Z^{\text{X}}_{0}=0$ or at best
$Z^{\text{X}}_{0}=Z_{0}$ _i.e._ with an initial value independent from the
input. In this appendix we will carry on the proofs in a more general setting
in which $Z^{\text{X}}_{0}$ is allowed to be input-dependent, as previously
discussed the choice of initial value is, in contrast to the classical
setting, meaningful inasmuch it allows to approximate linear maps on the
signature of $\omega^{\text{X}}_{[0,1]}$. In order to do so we have to
introduce a new gate, the initial value gate, in the form of a map

$\displaystyle(\cdot)_{0}$ $\displaystyle:\mathbb{X}\to\mathbb{R}^{d_{0}}$
(26) $\displaystyle X\mapsto X_{0}$

Despite the notation, there is no reason why $(X)_{0}$ should be the initial
value of the path $X$, one should think of this map as the one summarizing the
data which still matters for the task but which does not have a time-series
nature.

To recapitulate, the general setting of our models is the following: a
topological _input space_ space $\mathbb{X}$,

$\displaystyle(\cdot)_{0}:\mathbb{X}\to\mathbb{R}^{d_{0}},$
($(\cdot)_{0}$-gate) $\displaystyle\omega:\mathbb{X}\to
C_{1,0}([0,1];\mathbb{R}^{d_{\omega}}),$ ($\omega$-gate)
$\displaystyle\xi:\mathbb{X}\to C_{1,0}([0,1];\mathbb{R}^{d_{\xi}}).$
($\xi$-gate)

where all the gates are continuous functions on $\mathbb{X}$. The space
$\mathbb{X}$ does not have to be a space of paths, a topological structure
suffices, as long as the gates $(\cdot)_{0},\omega,\xi$ are well defined and
continuous.

######  Remark B.1.

Typical examples for the choice of gates are $\mathbb{X}$ space of paths and

$\displaystyle(X)_{0}=0\quad\omega^{\text{X}}_{t}=t\quad\xi^{\text{X}}_{t}=\int_{0}^{t}X_{s}ds$
(S4)
$\displaystyle(X)_{0}=0\quad\omega^{\text{X}}_{t}=\int_{0}^{t}softplus(\alpha
X_{s}+\beta)ds\quad\xi^{\text{X}}_{t}=\int_{0}^{t}softplus(\alpha
X_{s}+\beta)X_{s}ds$ (Mamba)

Then the main object of study, ”gated” Linear CDEs, are defined as:

######  Definition B.2.

Fix gates $(\cdot)_{0},\omega,\xi$ as above, $N\in\mathbb{N}$, matrices
$\\{A_{i}\\}_{i=1,\dots,d_{\omega}}$ ($A_{i}\in\mathbb{R}^{N\times N}$),
$B\in\mathbb{R}^{N\times d_{\xi}}$, $C\in\mathbb{R}^{N\times d_{0}}$. The
corresponding Linear CDE is the functional

$\displaystyle Z:\mathbb{X}\to C_{1}([0,1];\mathbb{R}^{N})$ (27)
$\displaystyle
Z^{\text{X}}_{t}=\sum_{i=1}^{d_{\omega}}A_{i}Z^{\text{X}}_{t}d\omega^{\text{X},i}_{t}+Bd\xi^{\text{X}}_{t}$
(28) $\displaystyle Z^{\text{X}}_{0}=CX_{0}$ (29)

###  B.2 Main Result - Statement and Strategy

Here we present the unified expressivity result in its most general form:

######  Theorem B.3.

For any compact set $\mathbb{K}\subseteq\mathbb{X}$ and continuous gates
$(\cdot)_{0},\omega,\xi$ with $\omega^{\text{X},1}_{t}\equiv t$ and
$\omega^{\text{X},2}_{t}\equiv t^{2}$. For any $\epsilon>0$ and any

$F\in\left\\{(X,t)\mapsto\Psi(\omega^{\text{X}}_{[0,t]})\cdot
X_{0}+\int_{0}^{t}\Phi(\omega^{\text{X}}_{[s,t]})\cdot
d\xi^{\text{X}}_{s}\right\\}$ (30)

where $\Psi\in C^{0}(C_{1,0};\mathbb{R}^{d_{0}})$ and $\Phi\in
C^{0}(C_{1,0};\mathbb{R}^{d_{\xi}})$, there exist a choice of hidden dimension
$N\geq 1$ and parameters $v\in\mathbb{R}^{N},A_{i}\in\mathbb{R}^{N\times
N},B\in\mathbb{R}^{N\times d_{\xi}},C\in\mathbb{R}^{N\times d_{0}}$ such that

$\sup\limits_{(X,t)\in\mathbb{K}\times[0,1]}|F(X,t)-\langle
v,Z^{\text{X}}_{t}\rangle|\leq\epsilon$ (31)

Moreover generic parameters suffice with high probability in the sense that
under LeCun initialization

$[A_{i}]_{n,j}\overset{\text{iid}}{\sim}\mathcal{N}(0,\frac{1}{N})\quad
C_{n,j},B_{n,j}\overset{\text{iid}}{\sim}\mathcal{N}(0,1)$

the following holds:

$\lim\limits_{N\to\infty}\mathbb{P}\big{[}\exists v\in\mathbb{R}^{N}:\text{
(\ref{app:eqn:dense_RKHS_main}) holds}\big{]}=1$

If the $A_{i}$s are constrained to be diagonal, as often is the case in
practice, the requirements $\omega^{\text{X},1}_{t}\equiv t$,
$\omega^{\text{X},2}_{t}\equiv t^{2}$ can be dropped and the existence result
only holds with

$F\in\left\\{(X,t)\mapsto\psi(\omega^{\text{X}}_{t})\cdot
X_{0}+\int_{0}^{t}\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}\right\\}$ (32)

for $\psi\in C^{0}(\mathbb{R}^{d_{\omega}};\mathbb{R}^{d_{0}})$ and $\phi\in
C^{0}(\mathbb{R}^{d_{\omega}};\mathbb{R}^{d_{\xi}})$.

Moreover in both the dense and diagonal cases the ”reverse” also holds in the
sense that, given any choice of matrices $A_{i},B,C$ there is an
$\epsilon$-close map $F$ in the corresponding family.

As one can see the theorem is composed of different sub-results, which we
believe are better understood separately from each other. The proof will thus
be split in the following steps:

  1. 1.

Using the theory developed in Appendix E we see how linear functions on the
$Z_{t}$s can be seen as linear functions on certain terms of the Signature
Transform.

  2. 2.

Such terms define a _feature map_ $T(X)_{0,t}$ which generates a Reproducing
Kernel Hilbert Space $\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}$. This
abstract space acts as an upper bound on expressivity: linear functions on
$Z_{t}$ always belong to its closure (in uniform norm), independently of
dimension and weights chosen, hence they cannot reach what functions in
$\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}$ can’t approximate.

  3. 3.

The full expressive range of $\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}$
is shown to be captured by generic $Z_{t}$s.

  4. 4.

Diagonal systems are shown to be restricted to a subset of the
$\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}$ of which they capture the
full expressive range.

###  B.3 Main Result - Proofs

####  B.3.1 An expansion for $Z^{\text{X}}_{t}$

######  Proposition B.4.

For any choice of $A_{i}\in\mathbb{R}^{N\times N},B\in\mathbb{R}^{N\times
d_{\xi}}$ and $C\in\mathbb{R}^{N\times d_{0}}$, the unique solution to

$\displaystyle
dZ^{\text{X}}_{t}=\sum_{i=1}^{d_{\omega}}A_{i}Z^{\text{X}}_{t}d\omega^{\text{X},i}_{t}+Bd\xi^{\text{X}}_{t}$
(33) $\displaystyle Z^{\text{X}}_{0}=CX_{0}\in\mathbb{R}^{N}$

is given, using the notation $A_{Ij}:=A_{j}A_{I}$, by

$\displaystyle Z^{\text{X}}_{t}=$
$\displaystyle\sum_{i=1}^{d_{0}}\sum_{I\in\mathbb{W}_{d_{\omega}}}A_{I}C_{i}\hskip
3.0ptX_{0}^{i}\text{Sig}(\omega^{\text{X}})_{0,t}^{I}+\sum_{j=1}^{d_{\xi}}\sum_{I\in\mathbb{W}_{d_{\omega}}}A_{I}B_{j}\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}d\xi^{\text{X},j}_{s}\in\mathbb{R}^{N}$
(34)

Notice here $A_{I}C_{i},A_{I}B_{j}\in\mathbb{R}^{N}$ and
$X_{0}^{i}\text{Sig}(\omega^{\text{X}})_{0,t}^{I},\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}d\xi^{\text{X},j}_{s}\in\mathbb{R}$.

###### Proof.

Just apply Theorems (E.2) and (E.6) of Appendix E. ∎

######  Remark B.5.

A property highlighted by the previous result is the interpretability of these
models. After training the NCDEs one can compute the matrix multiplications
and observe which entries of the signature the model chooses to take into
consideration, to attend.

####  B.3.2 The feature map $T$ and its RKHS

The expression in (34) is a _linear map_ on a _feature vector_ given, at time
$t$, by

$T(X)_{0,t}:=\left(X_{0}^{i}\text{Sig}(\omega^{\text{X}})_{0,t}^{I},\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}d\xi^{\text{X},j}_{s}:i\in[d_{0}],I\in\mathbb{W}_{d_{\omega}},j\in[d_{\xi}]\right)$
(35)

This feature vector can be understood as a tensor in the following way:

######  Definition B.6.

Let $\mathbb{W}_{d_{0},d_{\omega},d_{\xi}}$ be the set of words in the
alphabet

$\mathcal{A}_{d_{0},d_{\omega},d_{\xi}}:=\\{\boldsymbol{e}_{i}\\}_{i=1,\dots,d_{0}}\cup\\{\boldsymbol{\epsilon}^{\xi}_{j}\\}_{j=1,\dots,d_{\xi}}\cup\\{\boldsymbol{\epsilon}^{\omega}_{k}\\}_{k=1,\dots,d_{\omega}}$

Fixed the gates $(\cdot)_{0},\omega,\xi$ we define $T(X):[0,1]\to
l^{2}(\mathbb{W}_{d_{0},d_{\omega},d_{\xi}})\subseteq
T((\mathcal{A}_{d_{0},d_{\omega},d_{\xi}}))$ as the unique solution to:

$\displaystyle T(X)_{0,t}=$
$\displaystyle~{}\sum_{i=1}^{d}X_{0}^{i}\boldsymbol{e}_{i}+\sum_{j=1}^{d_{\xi}}\xi^{\text{X},j}_{t}\boldsymbol{\epsilon}^{\xi}_{j}+\sum_{k=1}^{d_{\omega}}\int_{0}^{t}T(X)_{0,s}~{}d\omega^{\text{X},k}_{s}\otimes\boldsymbol{\epsilon}^{\omega}_{k}$
(36)

In fact one readily sees that the only non-zero terms of $T(X)_{0,t}$ defined
as above are

$\displaystyle\langle T(X)_{0,t},\boldsymbol{e}_{i}\rangle=X_{0}^{i}$
$\displaystyle\langle
T(X)_{0,t},\boldsymbol{e}_{i}\otimes\boldsymbol{\epsilon}^{\omega}_{Ik}\rangle=\int_{0}^{t}\langle
T(X)_{0,s},\boldsymbol{e}_{i}\otimes\boldsymbol{\epsilon}^{\omega}_{I}\rangle
d\omega^{\text{X},k}_{s}=X_{0}^{i}~{}\text{Sig}(\omega^{\text{X}})_{0,t}^{Ik}$
$\displaystyle\langle
T(X)_{0,t},\boldsymbol{\epsilon}^{\xi}_{j}\rangle=\xi^{\text{X},j}_{t}=\int_{0}^{t}d\xi^{\text{X},j}_{s}$
$\displaystyle\langle
T(X)_{0,t},\boldsymbol{\epsilon}^{\xi}_{j}\otimes\boldsymbol{\epsilon}^{\omega}_{Ik}\rangle=\int_{0}^{t}\langle
T(X)_{0,s},\boldsymbol{\epsilon}^{\xi}_{j}\otimes\boldsymbol{\epsilon}^{\omega}_{I}\rangle
d\omega^{\text{X},k}_{s}=\int_{s=0}^{t}\int_{r=0}^{s}\text{Sig}(\omega^{\text{X}})_{r,s}^{I}d\xi^{\text{X},j}_{r}d\omega^{\text{X},k}_{s}$
$\displaystyle\hskip
15.0pt=\int_{r=0}^{t}\int_{s=r}^{t}\text{Sig}(\omega^{\text{X}})_{r,s}^{I}d\omega^{\text{X},k}_{s}d\xi^{\text{X},j}_{r}=\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{r,t}^{I}~{}d\xi^{\text{X},j}_{r}$

This is similar to the tensor-valued CDE defining the signature as a tensor
_i.e._ (Salvi et al., 2021a)

$\text{Sig}(\omega)_{0,t}=()+\int_{0}^{t}\text{Sig}(\omega)_{0,s}\otimes
d\omega_{s}$

with the addition of two terms to track $X_{0}$ and $\xi^{\text{X}}$. One
could also understand $T(X)_{s,t}$ as a sub-tensor of

$X_{0}\otimes\text{Sig}((\omega^{\text{X}},\xi^{\text{X}}))_{s,t}$

but in doing this one would have to explicitly ignore most of the terms of
this vector; the CDE (36) does exactly this, but implicitly. In any case the
subtensor view shows that $T:\mathbb{X}\times[0,1]^{2}\to
l^{2}(\mathbb{W}_{d_{0},d_{\omega},d_{\xi}})$ is well defined and continuous.

To the feature map $T(\cdot)_{0,t}$ with values in the Hilbert space
$l^{2}(\mathbb{W}_{d_{0},d_{\omega},d_{\xi}})$ is then associated a
Reproducing Kernel Hilbert Space (Berlinet & Thomas-Agnan, 2011), where the
Kernel is the one induced by the $l^{2}$ product, which we denote by

$\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}\subseteq
C^{0}(\mathbb{X};\mathbb{R})$ (37)

Classical RKHS theory tells us that we can characterize its elements as:

######  Proposition B.7.

A map $F(\cdot)_{t}:\mathbb{X}\to\mathbb{R}$ is an element of
$\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}$ if and only if it is of the
form

$\displaystyle F(x)_{t}=$
$\displaystyle\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle+\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}$ (38)

for $\alpha_{i},\beta_{j}\in l^{2}(\mathbb{W}_{d_{\omega}})$. Moreover
$\left\lVert
F(\cdot)_{t}\right\rVert^{2}_{\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}}$
is equal to the minimal value of

$\sum_{i=1}^{d_{0}}\left\lVert\alpha_{i}\right\rVert^{2}_{l^{2}(\mathbb{W}_{d_{\omega}})}+\sum_{j=1}^{d_{\xi}}\left\lVert\beta_{j}\right\rVert^{2}_{l^{2}(\mathbb{W}_{d_{\omega}})}$

taken over those $\gamma,\beta$ for which the above equality holds.

_Signature kernels_ (Salvi et al., 2021a) are a class of _universal kernels_
on sequential data which have received attention in recent years thanks to
their efficiency in handling path-dependent problems (Lemercier et al., 2021;
Salvi et al., 2021c; Cochrane et al., 2021; Salvi et al., 2021b; Cirone et
al., 2023; Issa et al., 2023).

Just as signature kernels, the kernel associated to $T(X)_{0,t}$ can be
explicitly written as the solution of a two-parameter CDE:

######  Lemma B.8.

Let $\mathcal{K}^{\text{X},\text{Y}}(s,t):=\langle
T(X)_{0,s},T(Y)_{0,t}\rangle_{l^{2}}$ then

$\displaystyle\mathcal{K}^{\text{X},\text{Y}}(s,t)=$ $\displaystyle~{}\langle
X_{0},Y_{0}\rangle+\langle\xi^{\text{X}}_{s},\xi^{\text{Y}}_{t}\rangle+\int_{\eta=0}^{s}\int_{\tau=0}^{t}\mathcal{K}^{\text{X},\text{Y}}(\eta,\tau)\langle
d\omega^{\text{X}}_{\eta},d\omega^{\text{Y}}_{\tau}\rangle$ (39)

or, directly in terms of Signature, also

$\displaystyle\mathcal{K}^{\text{X},\text{Y}}(s,t)=$ $\displaystyle\langle
X_{0},Y_{0}\rangle\langle\text{Sig}(\omega^{\text{X}})_{0,s},\text{Sig}(\omega^{\text{Y}})_{0,t}\rangle+\int_{\eta=0}^{s}\int_{\tau=0}^{t}\langle\text{Sig}(\omega^{\text{X}})_{\eta,s},\text{Sig}(\omega^{\text{Y}})_{\tau,t}\rangle\langle
d\xi^{\text{X}}_{\eta},d\xi^{\text{Y}}_{\tau}\rangle$ (40)

###### Proof.

The first expression follows immediately from Eqn. (36) the second one by
summing the products of $T(X)_{0,s}$’s and $T(Y)_{0,t}$’s entries given above.
∎

######  Definition B.9.

Define the space $\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}\subseteq
C^{0}(\mathbb{X}\times[0,1];\mathbb{R})$ as the space of functions of form

$\displaystyle(X,t)\mapsto$
$\displaystyle\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle+\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}$ (41)

for $\alpha_{i},\beta_{j}\in l^{2}(\mathbb{W}_{d_{\omega}})$. Thus for all
$t\in[0,1]$ and $F\in\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ it
holds $F(\cdot,t)\in\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{t}$.

####  B.3.3 Linear maps on $Z^{\text{X}}_{t}$ are close to the RKHS

The following proposition will show how linear maps on $Z^{\text{X}}_{t}$
cannot be more expressive than elements of the RKHS
$\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ since their closure is in
the closure of $\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$. In this
precise sense these spaces act like upper bounds to expressiveness.

######  Proposition B.10.

Assume $\mathbb{X}$ compact. Consider fixed the gates and
$A_{i}\in\mathbb{R}^{N\times N},B\in\mathbb{R}^{N\times d_{\xi}}$ and
$C\in\mathbb{R}^{N\times d_{0}}$. Consider a linear readout
$v\in\mathbb{R}^{N}$. For any $\epsilon>0$ there exist choices of
$\alpha_{i},\beta_{j}\in l^{2}(\mathbb{W}_{d_{\omega}})$ such that

$\sup_{(X,t)\in\mathbb{X}\times[0,1]}|\langle
v,Z^{\text{X}}_{t}\rangle-F(X,t)|\leq\epsilon$ (42)

where $F\in\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$. In other
words, linear maps on the $Z^{\text{X}}_{t}$ are in the uniform closure of
$\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$.

###### Proof.

Using Eqn. (34) we see that $\langle v,Z^{\text{X}}_{t}\rangle$ is a linear
map on $T(X)_{0,t}$ with coefficients

$v^{\top}A_{I}B_{j}\quad v^{\top}A_{I}C_{i}$

using Cauchy-Schwartz it’s moreover easy to see the existence of a constant
$\lambda\geq 0$ such that for all $I,i,j$ one has

$|v^{\top}A_{I}B_{j}|\leq\lambda^{|I|}\quad|v^{\top}A_{I}C_{i}|\leq\lambda^{|I|}.$

Since
$|\text{Sig}(\omega)^{I}_{s,t}|\leq\frac{1}{|I|!}\left\lVert\omega\right\rVert_{1-var,[s,t]}^{|I|}$
we have that, given an integer $M\geq 0$, the bound

$\displaystyle R_{M}(t)$ $\displaystyle:=\left|\sum_{i=1}^{d_{0}}\sum_{|I|\geq
M}v^{\top}A_{I}C_{i}\hskip
3.0ptX_{0}^{i}\text{Sig}(\omega^{\text{X}})_{0,t}^{I}+\sum_{j=1}^{d_{\xi}}\sum_{|I|\geq
M}v^{\top}A_{I}B_{j}\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}d\xi^{\text{X},j}_{s}\right|$
$\displaystyle\leq(\left\lVert
X_{0}\right\rVert_{1}+\left\lVert\xi^{\text{X}}_{t}\right\rVert_{1})\sum_{m=M}^{\infty}\frac{\lambda^{m}d_{\omega}^{m}\left\lVert\omega^{\text{X}}\right\rVert_{1-var,[0,t]}^{m}}{m!}$
$\displaystyle\leq(\left\lVert
X_{0}\right\rVert_{1}+\left\lVert\xi^{\text{X}}_{t}\right\rVert_{1})\sum_{m=M}^{\infty}\frac{\lambda^{m}d_{\omega}^{m}\left\lVert\omega^{\text{X}}\right\rVert_{1-var,[0,1]}^{m}}{m!}\leq
K\sum_{m=M}^{\infty}\frac{(\lambda d_{\omega}K)^{m}}{m!}$

where $K\geq 0$ is a constant which must exist by compactness of $\mathbb{X}$
and continuity of the gates. Since $K\sum_{m=M}^{\infty}\frac{(\lambda
d_{\omega}K)^{m}}{m!}$ is just the tail of the taylor expansion of
$Ke^{\lambda d_{\omega}K}$ there must be an $M$ such that
$\sup_{t\in[0,1]}R_{M}(t)\leq\epsilon$. But then the choice

$\alpha_{i}^{I}:=v^{\top}A_{I}C_{i}~{}\mathbb{I}(|I|<M)\quad\beta_{j}^{I}:=v^{\top}A_{I}B_{j}~{}\mathbb{I}(|I|<M)$

suffices for the required bound.

∎

####  B.3.4 Uniform closure of the RKHS

Now that we have established the theoretical interest of the
$\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ we proceed to
characterize which maps $(X,t)\to\mathbb{R}$ can be uniformly approximated
trough them.

######  Proposition B.11.

Fix a compact input set $\mathbb{X}$ and continuous gates
$(\cdot)_{0},\omega,\xi$ with $\omega^{\text{X},1}_{t}\equiv t$ and
$\omega^{\text{X},2}_{t}\equiv t^{2}$. For any $\epsilon>0$ and any

$F\in\left\\{(X,t)\mapsto\Psi(\omega^{\text{X}}_{[0,t]})\cdot
X_{0}+\int_{0}^{t}\Phi(\omega^{\text{X}}_{[s,t]})\cdot
d\xi^{\text{X}}_{s}\right\\}$ (43)

where $\Psi\in C^{0}(C_{1,0};\mathbb{R}^{d_{0}})$ and $\Phi\in
C^{0}(C_{1,0};\mathbb{R}^{d_{\xi}})$, there exist a
$G\in\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ such that

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|F(X,t)-G(X,t)|\leq\epsilon$ (44)

###### Proof.

Note first that the map

$\mathbb{X}\times[0,1]\times[0,1]\to
C_{1,0}([0,1];\mathbb{R}^{d_{\omega}})\quad(X,s,t)\mapsto\omega^{\text{X}}_{[s,t]}$

is a continuous map from a compact space, thus the image must be compact too.
Moreover by Prop. A.8 the Signature separates the points in this image. Since
any $G$ as above has form

$\displaystyle G(X,t)$
$\displaystyle=\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle+\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}$
$\displaystyle=\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\alpha_{i},\text{Sig}(\omega^{\text{X}}_{[0,t]})_{0,1}\rangle+\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\beta_{j},\text{Sig}(\omega^{\text{X}}_{[s,t]})_{0,1}\rangle
d\xi^{\text{X},j}_{s}$

the proof follows from the uniform density on compact sets of linear
functionals on the (truncated) Signature (Thm. A.5), by also uniformly
bounding thanks to compactness and continuity the norms of $X_{0}$ and
$\xi^{\text{X}}_{1}$. ∎

####  B.3.5 Generic Weights are fully expressive

We have seen how linear maps on $Z^{\text{X}}_{t}$ are in the uniform closure
of $\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$, and we have
explicitly characterized this closure. It is then natural to ask ”how much” of
this closure the $Z^{\text{X}}_{t}$ are able to ”explore”. The present section
not only shows that the $Z^{\text{X}}_{t}$ ”explore” all the closure, but also
that a generic choice of weights is enough to eventually do this with high
probability.

The fact that these maps are ”universal” in the above sense is not surprising,
since it is well known that Linear CDEs are universal for path-to-point tasks
_cf._ (Kidger, 2022), what is surprising is that this universality can be
achieved probabilistically with one of the _standard_ parametrizations used in
ML practice (LeCun) 141414It can be proved, using the results of (Dubach &
Peled, 2021), that the sampling measure does not have to be Gaussian if it
satisfies certain moment requirements..

######  Theorem B.12.

Fix $\mathbb{X}$ compact and $\epsilon>0$. For all
$F\in\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ there exist a choice
of hidden dimension $N\geq 1$ and parameters
$v\in\mathbb{R}^{N},A_{i}\in\mathbb{R}^{N\times N},B\in\mathbb{R}^{N\times
d_{\xi}},C\in\mathbb{R}^{N\times d_{0}}$ such that

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|F(X,t)-\langle
v,Z^{\text{X}}_{t}\rangle|\leq\epsilon$ (45)

Moreover generic weight choices suffice with high probability, in the sense
that under LeCun initialization

$[A_{j}]_{n,n^{\prime}}\overset{\text{iid}}{\sim}\mathcal{N}(0,\frac{1}{N})\quad[C]_{n,i},[B]_{n,j}\overset{\text{iid}}{\sim}\mathcal{N}(0,1)$

the following holds

$\lim\limits_{N\to\infty}\mathbb{P}\big{[}\exists v\in\mathbb{R}^{N}:\text{
(\ref{app:eqn:dense_RKHS}) holds }\big{]}=1$

We propose two proofs, the first one of a deterministic character concerns the
first claim in the theorem, the second one is probabilistic and concerns the
whole result. The deterministic proof follows the same arguments employed by
(Kidger, 2022) and is included to highlight the main idea of the probabilistic
result, which reduces to a ”spin” on the central argument of this proof.

###### Deterministic Proof..

Any $F\in\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ has form

$F(X,t)=\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle+\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}$ (46)

for fixed $\alpha_{i},\beta_{j}\in l^{2}(\mathbb{W}_{d_{\omega}})$. Consider
an integer $M\geq 0$ such that

$\sup\limits_{(x,t)\in\mathbb{X}\times[0,1]}|F(X,t)-\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\pi_{M}\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle-\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\pi_{M}\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}|\leq\epsilon$ (47)

where $\pi_{M}$ is the truncation at length $M$.

Fix $d=d_{0}+d_{\omega}+d_{\xi}$. Consider $\mu(M,d)\in\mathbb{N}$ such that
$\mathbb{R}^{\mu(M,d)}\simeq T^{M}(\mathbb{R}^{d})$. We are going to write
$e_{I}\in\mathbb{R}^{\mu(M,d)}$ to mean the image of $e_{I}\in
T^{M}(\mathbb{R}^{d})$ trough this identification. Note that
$(\cdot)\otimes_{M}e_{k}:T^{M}(\mathbb{R}^{d})\to T^{M}(\mathbb{R}^{d})$ is a
linear map, it does then correspond to a matrix
$\Lambda_{k}\in\mathbb{R}^{\mu(M,d)\times\mu(M,d)}$. Write
$\varepsilon^{\xi}_{j}:=e_{d_{0}+j}$ for $j=1,\dots,d_{\xi}$ and
$\varepsilon^{\omega}_{k}:=e_{d_{0}+d_{\xi}+k}$ for $k=1,\dots,d_{\omega}$.
Then the solution to

$\mathbb{R}^{\mu(M,d)}\ni\tilde{Z}_{t}=\sum_{i=1}^{d_{0}}X_{0}^{i}e_{i}+\sum_{j=1}^{d_{\xi}}\xi^{\text{X},j}_{t}\varepsilon^{B}_{j}+\sum_{k=1}^{d_{\omega}}\int_{0}^{t}\Lambda_{d_{0}+d_{\xi}+k}\tilde{Z}_{s}d\omega^{\text{X},k}_{s}$
(48)

is the object in $\mathbb{R}^{\mu(M,d)}$ corresponding to the truncated tensor
$\pi_{M}(T(X)_{0,t})$.

This $\tilde{Z}_{t}$ is of the form $Z^{\text{X}}_{t}$ with $N=\mu(M,d)$,
$A_{k}=\Lambda_{d_{0}+d_{\xi}+k}$,
$B=\left[\varepsilon^{\xi}_{1}|\cdots|\varepsilon^{\xi}_{d_{\xi}}\right]$ and
$C=\left[e_{1}|\cdots|e_{d_{0}}\right]$.

In particular note how these matrices are such that

$e_{J}^{T}A_{I}C_{i}=\mathbb{I}(e_{J}=e_{i}\otimes\varepsilon^{\omega}_{I}),\quad
e_{J}^{T}A_{I}B_{j}=\mathbb{I}(e_{J}=\varepsilon^{\xi}_{j}\otimes\varepsilon^{\omega}_{I}),$
(49)

since it holds that

$A_{I}C_{i}=e_{i}\otimes\varepsilon^{\omega}_{I},\quad
A_{I}B_{j}=\varepsilon^{\xi}_{j}\otimes\varepsilon^{\omega}_{I},$ (50)

and for all $|I|>M$ one has necessarily $A_{I}=0$.

Our strategy is that of using these equaities to create a vector
$v\in\mathbb{R}^{N}$ corresponding to the $\pi_{M}\alpha_{i}$ and
$\pi_{M}\beta_{j}$. Define the vector

$v:=\sum_{i=1}^{d_{0}}\sum_{|I|\leq
M}\alpha_{i}^{I}~{}e_{i}\otimes\varepsilon^{\omega}_{I}+\sum_{j=1}^{d_{\omega}}\sum_{|I|\leq
M}\beta_{j}^{I}~{}\varepsilon^{\xi}_{j}\otimes\varepsilon^{\omega}_{I}\in\mathbb{R}^{\mu(M,d)}$
(51)

Then expanding $Z^{\text{X}}_{t}$ as in (34) and using the equalities above
one has

$\displaystyle\langle v,Z^{\text{X}}_{t}\rangle=$
$\displaystyle\sum_{i=1}^{d_{0}}\sum_{I}v^{\top}A_{I}C_{i}~{}X_{0}^{i}\text{Sig}(\omega^{\text{X}})_{0,t}+\sum_{j=1}^{d_{\omega}}\sum_{I}v^{\top}A_{I}B_{j}~{}\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}d\xi^{\text{X},j}_{s}$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{d_{0}}\sum_{|I|\leq
M}\alpha_{i}^{I}X_{0}^{i}\text{Sig}(\omega^{\text{X}})_{0,t}+\sum_{j=1}^{d_{\xi}}\sum_{|I|\leq
M}\beta_{j}^{I}\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}d\xi^{\text{X},j}_{s}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\pi_{M}\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle+\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\pi_{M}\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}$

proving that for such $v$ and $Z^{\text{X}}$ it holds

$\sup\limits_{(x,t)\in\mathbb{X}\times[0,1]}|F(X,t)-\langle
v,Z^{\text{X}}_{t}\rangle|\leq\epsilon$ (52)

∎

The crucial ingredient for the success of this proof is the possibility to
recreate the space $T^{M}(\mathbb{R}^{d_{0}+d_{\omega}+d_{\xi}})$ as an
euclidean space. To do this one needs
$\mu(M,d_{0}+d_{\omega}+d_{\xi})\sim(d_{0}+d_{\omega}+d_{\xi})^{M}$ orthogonal
vectors and a way to express them using the matrices $A_{i},B$ and $C$, the
essential equations which capture this are given by (49).

The core idea of the following probabilistic proof of this same result is that
of allowing for some error in (49), so the idea is that of exhibiting only
_approximately_ orthogonal vectors. At the cost of losing exactness, one can
leverage results of the Johnson-Lindenstrauss (Dasgupta & Gupta, 2003) type to
find on the order of $\sim e^{\varepsilon^{2}N}$ vectors in $\mathbb{R}^{N}$
orthogonal up to an $\varepsilon$ error, using random projections. This idea
in the context of Signature goes back to (Cuchiero et al., 2021a), and allows
for much smaller hidden dimensions.

###### Proof.

(Probabilistic Proof) Any
$F\in\mathcal{H}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ has form

$F(X,t)=\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle+\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}$ (53)

for fixed $\alpha_{i},\beta_{j}\in l^{2}(\mathbb{W}_{d_{\omega}})$. Consider
an integer $M\geq 0$ such that

$\sup\limits_{(x,t)\in\mathbb{X}\times[0,1]}|F(X,t)-\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\pi_{M}\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle-\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\pi_{M}\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}|\leq\epsilon$ (54)

where $\pi_{M}$ is the truncation at length $M$.

From (Cirone et al., 2023)[Appendix C] we know that

$\displaystyle\left\lVert\frac{1}{N}C_{i}^{\top}A_{I}^{\top}A_{J}C_{j}-\delta_{iI}^{jJ}\right\rVert_{L^{2}}=\mathcal{O}(\frac{1}{\sqrt{N}})2^{\frac{|I|+|J|}{2}}(|I|+|J|)!!$
(55)
$\displaystyle\left\lVert\frac{1}{N}C_{i}^{\top}A_{I}^{\top}A_{J}B_{j}\right\rVert_{L^{2}}=\mathcal{O}(\frac{1}{\sqrt{N}})2^{\frac{|I|+|J|}{2}}(|I|+|J|)!!$
(56)
$\displaystyle\left\lVert\frac{1}{N}B_{i}^{\top}A_{I}^{\top}A_{J}B_{j}-\delta_{iI}^{jJ}\right\rVert_{L^{2}}=\mathcal{O}(\frac{1}{\sqrt{N}})2^{\frac{|I|+|J|}{2}}(|I|+|J|)!!$
(57)

Our strategy is that of using these bounds to create a vector
$v\in\mathbb{R}^{N}$ ”acting” like the $\pi_{M}\alpha_{i}$ and
$\pi_{M}\beta_{j}$. Define, noting that the $A_{i},C_{i},B_{j}$ depend on $N$,
the vector

$v^{\text{N}}:=\frac{1}{N}\left(\sum_{i=1}^{d_{0}}\sum_{|I|\leq
M}\alpha_{i}^{I}~{}A_{I}C_{i}+\sum_{j=1}^{d_{\omega}}\sum_{|I|\leq
M}\beta_{j}^{I}~{}A_{I}B_{j}\right)$ (58)

Then expanding $Z^{\text{X}}_{t}$ as in (34)

$\displaystyle R_{M}:=$
$\displaystyle\left\lVert\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}\left|\langle
v^{\text{N}},Z^{\text{X}}_{t}\rangle-\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\pi_{M}\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle-\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\pi_{M}\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}\right|\right\rVert_{L^{2}}$ $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{d_{0}}\sum_{|I|\leq
M}\left\lVert(v^{\text{N}})^{\top}A_{I}C_{i}-\alpha_{i}^{I}\right\rVert_{L^{2}}\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|X_{0}^{i}\text{Sig}(\omega^{\text{X}})^{I}_{0,t}|$
$\displaystyle++\sum_{i=1}^{d_{0}}\sum_{|I|>M}\left\lVert(v^{\text{N}})^{\top}A_{I}C_{i}\right\rVert_{L^{2}}\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|X_{0}^{i}\text{Sig}(\omega^{\text{X}})^{I}_{0,t}|$
$\displaystyle+\sum_{j=1}^{d_{\omega}}\sum_{|I|\leq
M}\left\lVert(v^{\text{N}})^{\top}A_{I}B_{j}-\beta_{j}^{I}\right\rVert_{L^{2}}\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|\int_{0}^{t}Sig(\omega^{\text{X}})^{I}_{s,t}d\xi^{\text{X},j}_{s}|$
$\displaystyle++\sum_{j=1}^{d_{\omega}}\sum_{|I|>M}\left\lVert(v^{\text{N}})^{\top}A_{I}B_{j}\right\rVert_{L^{2}}\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|\int_{0}^{t}Sig(\omega^{\text{X}})^{I}_{s,t}d\xi^{\text{X},j}_{s}|$

Note how for $|I|\leq M$ one has

$\left\lVert(v^{\text{N}})^{\top}A_{I}C_{i}-\alpha_{i}^{I}\right\rVert_{L^{2}}\leq\mathcal{O}_{M}(\frac{1}{\sqrt{N}})$

and that similarly for $|I|>M$

$\left\lVert(v^{\text{N}})^{\top}A_{I}C_{i}\right\rVert_{L^{2}}\leq\mathcal{O}_{M}(\frac{1}{\sqrt{N}})2^{\frac{|I|}{2}}(M+|I|)!!$

Which leads, thanks to the same bounds of (Cirone et al., 2023)[Appendix C],
to

$R_{M}=\frac{1}{\sqrt{N}}\mathcal{O}_{M,\mathbb{X}}(1)$ (59)

But then by Markov’s inequality it holds that

$\mathbb{P}\left[\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}\left|\langle
v^{\text{N}},Z^{\text{X}}_{t}\rangle-\sum_{i=1}^{d_{0}}X_{0}^{i}\langle\pi_{M}\alpha_{i},\text{Sig}(\omega^{\text{X}})_{0,t}\rangle-\sum_{j=1}^{d_{\xi}}\int_{0}^{t}\langle\pi_{M}\beta_{j},\text{Sig}(\omega^{\text{X}})_{s,t}\rangle
d\xi^{\text{X},j}_{s}\right|\leq\epsilon\right]\to 1$ (60)

and thus there must be a choice of $N,\\{A_{i}\\},B,C$ such that the
inequality holds, and we thus obtain using (54)

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|F(X,t)-\langle
v^{\text{N}},Z^{\text{X}}_{t}\rangle|\leq 2\epsilon$

and we conclude by arbitrariness of $\epsilon$.

∎

###  B.4 The Diagonal Case

Here we study the particular, but empirically important, case where the
matrices $A_{i}$ are taken to be diagonal151515It is equivalent to ask for
them to be commuting..

What we’ll discover is that the $Z^{\text{X}}_{t}$ cannot differentiate
between $\text{Sig}(\omega^{\text{X}})_{s,t}^{I}$ and other
$\text{Sig}(\omega^{\text{X}})_{s,t}^{\sigma(I)}$ for any permutation $\sigma$
of the letters in the word $I$.

####  B.4.1 Diagonal Expansion for $Z^{\text{X}}_{t}$

######  Proposition B.13.

For any choice of $V\in\mathbb{R}^{N\times d_{\omega}},B\in\mathbb{R}^{N\times
d_{\xi}}$ and $C\in\mathbb{R}^{N\times d_{0}}$, writing
$A_{i}:=\operatorname{diag}(V_{i})$, the unique solution to

$\displaystyle
dZ^{\text{X}}_{t}=\sum_{i=1}^{d_{\omega}}A_{i}Z^{\text{X}}_{t}d\omega^{\text{X},i}_{t}+Bd\xi^{\text{X}}_{t}$
(61) $\displaystyle Z^{\text{X}}_{0}=CX_{0}\in\mathbb{R}^{N}$

is given by

$Z^{\text{X}}_{t}=e^{\operatorname{diag}(V\omega^{\text{X}}_{t})}CX_{0}+\int_{0}^{t}e^{\operatorname{diag}(V(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s}))}Bd\xi^{\text{X}}_{s}$
(62)

which can be expanded as

$\displaystyle Z^{\text{X}}_{t}=$
$\displaystyle\sum_{i=1}^{d_{0}}\sum_{I\in\mathbb{W}_{d_{\omega}}}A^{sym}_{I}C_{i}~{}X_{0}^{i}\text{Sig}(\omega^{\text{X}})_{0,t}^{sym,I}+\sum_{j=1}^{d_{\xi}}\sum_{I\in\mathbb{W}_{d_{\omega}}}A^{sym}_{I}B_{j}\int_{0}^{t}\text{Sig}(\omega^{\text{X}})_{s,t}^{sym,I}d\xi^{\text{X},j}_{s}\in\mathbb{R}^{N}$
(63)

where

$A^{sym}_{I}:=\frac{1}{|I|!}\sum_{\sigma\in
S_{k}}A_{\sigma(I)}=A_{I}\quad\text{Sig}(\omega^{\text{X}})_{s,t}^{sym,I}:=\frac{1}{|I|!}\sum_{\sigma\in
S_{k}}\text{Sig}(\omega^{\text{X}})_{s,t}^{\sigma(I)}.$ (64)

###### Proof.

By Theorem E.1 and Theorem E.6 we know that the solution of

$Z^{\text{X}}_{t}=Z^{\text{X}}_{0}+\sum_{i=1}^{d_{\omega}}\int_{0}^{t}A_{i}Z^{\text{X}}_{t}d\omega^{\text{X},i}_{t}+\int_{0}^{t}Bd\xi^{\text{X}}_{t}$
(65)

is explicitly given by

$Z_{t}^{\text{X}}=W^{\text{X}}_{0,t}Z^{\text{X}}_{0}+\int_{0}^{t}W^{\text{X}}_{s,t}Bd\xi^{\text{X}}_{s}$
(66)

where $W_{s,t}$ is the unique solution to

$W^{\text{X}}_{s,t}=Id+\sum_{i=1}^{d_{\omega}}\int_{s}^{t}A_{i}W^{\text{X}}_{s,r}d\omega^{\text{X},i}_{r}$
(67)

In case the $A_{i}$s are commuting matrices one can explicitly write the
solution as

$W^{\text{X}}_{s,t}=\exp{\left(\sum_{i=1}^{d_{\omega}}\int_{s}^{t}A_{i}d\omega^{\text{X},i}_{r}\right)}=\exp{\left(\operatorname{diag}(V(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s}))\right)}$
(68)

since for fixed $s$ one has, using commutativity, that

$dW^{\text{X}}_{s,t}=W^{\text{X}}_{s,t}\left(\sum_{i=1}^{d_{\omega}}A_{i}d\omega^{\text{X},i}_{t}\right)=\sum_{i=1}^{d_{\omega}}A_{i}W^{\text{X}}_{s,t}d\omega^{\text{X},i}_{t}$

On the other hand we know, Theorem E.2, that

$W^{\text{X}}_{s,t}=\sum_{I\in\mathbb{W}_{d_{\omega}}}A_{I}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}=\sum_{k=0}^{\infty}\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}A_{I}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}$
(69)

The two views are reconciled by noticing that the symmetric group $S_{k}$ acts
on $\mathbb{W}_{d_{\omega}}^{k}$, the space of words of lenth $k$, by
permuting the letters and, by commutativity,

$\forall\sigma\in S_{k}.\forall I\in\mathbb{W}_{d_{\omega}}^{k}.\hskip
5.0ptA_{I}=A_{\sigma(I)}$

Then we have

$\displaystyle\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}A_{I}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}=$
$\displaystyle\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}\frac{1}{k!}\sum_{\sigma\in
S_{k}}A_{\sigma(I)}\text{Sig}(\omega^{\text{X}})_{s,t}^{\sigma(I)}=\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}\frac{A_{I}}{k!}\sum_{\sigma\in
S_{k}}\text{Sig}(\omega^{\text{X}})_{s,t}^{\sigma(I)}$

recalling then how $e_{I_{1}}\shuffle\cdots\shuffle e_{I_{k}}=\sum_{\sigma\in
S_{k}}e_{\sigma(I)}$ we get to

$\displaystyle\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}A_{I}\text{Sig}(\omega^{\text{X}})_{s,t}^{I}=$
$\displaystyle\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}\frac{A_{I}}{k!}\sum_{\sigma\in
S_{k}}\text{Sig}(\omega^{\text{X}})_{s,t}^{\sigma(I)}=\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}\frac{A_{I}}{k!}\prod_{i=1}^{k}\text{Sig}(\omega^{\text{X}})^{I_{i}}_{s,t}$
$\displaystyle=$
$\displaystyle\sum_{I\in\mathbb{W}_{d_{\omega}}^{k}}\frac{1}{k!}\prod_{i=1}^{k}A_{I_{i}}\text{Sig}(\omega^{\text{X}})^{I_{i}}_{s,t}=\frac{1}{k!}\left(\sum_{i=1}^{d_{\omega}}A_{i}\text{Sig}(\omega^{\text{X}})^{i}_{s,t}\right)^{k}=\frac{1}{k!}\left(\sum_{i=1}^{d_{\omega}}\int_{s}^{t}A_{i}d\omega^{\text{X},i}_{r}\right)^{k}$

In particular we see how in the commuting case

$W^{\text{X}}_{s,t}=\sum_{I\in\mathbb{W}_{d_{\omega}}}A_{I}^{sym}\text{Sig}(\omega^{\text{X}})_{s,t}^{sym,I}$
(70)

where

$A^{sym}_{I}:=\frac{1}{|I|!}\sum_{\sigma\in
S_{k}}A_{\sigma(I)}=A_{I}\quad\text{Sig}(\omega^{\text{X}})_{s,t}^{sym,I}:=\frac{1}{|I|!}\sum_{\sigma\in
S_{k}}\text{Sig}(\omega^{\text{X}})_{s,t}^{\sigma(I)}.$

∎

####  B.4.2 Diagonal Expressiveness

######  Theorem B.14.

Fix a compact input set $\mathbb{X}$ and continuous gates
$(\cdot)_{0},\omega,\xi$. For any $\epsilon>0$ and any

$F\in\left\\{(X,t)\mapsto\psi(\omega^{\text{X}}_{t})\cdot
X_{0}+\int_{0}^{t}\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}\right\\}$ (71)

for $\psi\in C^{0}(\mathbb{R}^{d_{\omega}};\mathbb{R}^{d_{0}})$ and $\phi\in
C^{0}(\mathbb{R}^{d_{\omega}};\mathbb{R}^{d_{\xi}})$, there exist a choice of
hidden dimension $N\geq 1$ and parameters
$v\in\mathbb{R}^{N},B\in\mathbb{R}^{N\times d_{\xi}},C\in\mathbb{R}^{N\times
d_{0}}$ and diagonal $A_{i}\in\mathbb{R}^{N\times N}$ such that

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|F(X,t)-\langle
v,Z^{\text{X}}_{t}\rangle|\leq\epsilon$ (72)

Moreover the ”reverse” also holds _i.e._ given any choice of matrices
$A_{i},B,C$ there is an $\epsilon$-close map $F$ in the family.

###### Proof.

This is just a repetition of the arguments used for the dense case with little
more care to get the uniformity in time.

One defines the subset
$Sym({\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]})\subset{\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$
of those $F$ of type (41) defined by $\alpha_{i},\beta_{j}\in
l^{2}(\mathbb{W}_{d_{\omega}})$ such that for any word $I$ and any permutation
$\sigma(I)$ of it

$\alpha_{i}^{I}=\alpha_{i}^{\sigma(I)}\quad\beta_{j}^{I}=\beta_{j}^{\sigma(I)}$
(73)

The same argument of Proposition B.10 shows that the uniform closure of the
space of linear maps on the $Z^{\text{X}}_{t}$ is contained in the uniform
closure of $Sym({\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]})$, and
the same bounds show that this latter closure is the same as that of its
subset composed of those $F\in
Sym({\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]})$ having entries
eventually equal to $0$.

Since

$\text{Sig}(\omega^{\text{X}})_{s,t}^{sym,I}:=\frac{1}{|I|!}\sum_{\sigma\in
S_{k}}\text{Sig}(\omega^{\text{X}})_{s,t}^{\sigma(I)}=\frac{1}{|I|!}\prod_{i=1}^{|I|}(\omega^{\text{X},I_{i}}_{t}-\omega^{\text{X},I_{i}}_{s}),$

such maps can be expressed exactly in the form

$P(\omega^{\text{X}}_{t})\cdot
X_{0}+\int_{0}^{t}Q(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}$

for polynomial maps $P,Q$ fixed in time. The usual compactness and continuity
argument, together with an application of Stone-Weiestrass, thus proves that
the uniform closure of
$Sym({\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]})$ has the form
needed.

The final ingredient is the density of the space of linear maps on the
$Z^{\text{X}}_{t}$ in
$Sym({\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]})$; this is another
consequence of Stone-Weiestrass as seen from Proposition B.17. ∎

######  Remark B.15.

Notice how here there is no need to augment the paths in creative ways in
order to ensure separability of the points. The map
$(\omega,s,t)\mapsto\omega_{[s,t]}\in C_{1,0}([0,1];\mathbb{R}^{d_{\omega}})$
is replaced by
$(\omega,s,t)\mapsto\omega_{t}-\omega_{s}\in\mathbb{R}^{d_{\omega}}$ and the
space of polynomials always separates points in $\mathbb{R}^{d_{\omega}}$.

######  Remark B.16.

It is not necessary to pass trough
$Sym({\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]})$ to prove the
previous result, since it directly follows from Proposition B.17. This choice
of presentation has been motivated by the conviction of the usefulness of
drawing parallels and comparisons.

######  Proposition B.17.

Fix a compact set $\mathbb{K}\subset\mathbb{R}^{d}$ and a $d$-dimensional
convex cone $C$ containing the origin. The space

$\mathcal{E}:=Span\left(\mathbb{K}\ni x\mapsto
e^{\langle\alpha,x\rangle_{\mathbb{R}^{d}}}\in\mathbb{R}:\alpha\in C\right)$

is uniformly dense in $C^{0}(\mathbb{K};\mathbb{R})$.

###### Proof.

This is an application of Stone-Weiestrass: $\mathcal{E}$ is a sub-algebra
since

$e^{\langle\alpha,x\rangle}e^{\langle\beta,x\rangle_{\mathbb{R}^{d}}}=e^{\langle\alpha+\beta,x\rangle_{\mathbb{R}^{d}}}$

and $\alpha,\beta\in C\implies\alpha+\beta\in C$ by convexity of the cone;
$\mathcal{E}$ contains the constant function $e^{\langle 0,x\rangle}=1$ and is
clearly point separating since the cone, being $d$-dimensional, it contains a
basis of the whole space. ∎

######  Remark B.18.

The usefulness of stating the previous result in such a general setting is the
following: with this formalism we can, for example, restrict to $\alpha\leq
0$, in this way we would have a method to control the stability (_cf._
Appendix C.1) of the linear CDEs by choosing the gate with a.s.
$\dot{\omega}^{\text{X}}\geq 0$.

##  Appendix C Stability and Chaining of Diagonal Systems

For this section consider, unless otherwise stated, a fixed $N\geq 0$, compact
$\mathbb{X}$ and gates $(\cdot)_{0},\omega,\xi$.

We will study the stability and chaining of diagonal systems defined by the
choice of a matrix $V\in\mathbb{R}^{N\times d_{\omega}}$ such that
$A_{i}:=diag(V_{i})$, where $V=[V_{1}|\cdots|V_{d_{\omega}}]$.

Note that the present discussion holds even for non-diagonal but _commuting_
matrices, since these can be simultaneously diagonalized (at the cost of
considering the complex plane).

###  C.1 Stability

Here we explore the stability of the dynamical system $Z^{\text{X}}$, thus we
need to study the eigenvalues of the $W^{\text{X}}_{s,t}$. Recall how in this
setting

$W^{\text{X}}_{s,t}=\exp{\left(\sum_{i=1}^{d_{\omega}}\int_{s}^{t}A_{i}d\omega^{\text{X},i}_{r}\right)}=\exp{\left(\operatorname{diag}(\int_{s}^{t}Vd\omega^{\text{X}}_{r})\right)}=\exp{\left(\operatorname{diag}\big{(}V(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\big{)}\right)}$
(74)

Note that because $\omega^{\text{X}}$ is continuous and of bounded variation,
it can be reparameterised to be Lipschitz continuous, hence absolutely
continuous. Thus we can assume that $\omega^{\text{X}}$ is almost everywhere
differentiable and its derivative $\dot{\omega}\in L^{1}$.

The stability of the dynamical system then depends on the alignment between
$\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s}$ and the singular vectors of $V$.
If $V\dot{\omega}^{\text{X}}_{t}\leq 0$ for all times, where the inequality is
coordinate-wise, then $W^{\text{X}}_{s,t}$ has eigenvalues all in $[0,1]$ thus
the system is stable making training easier (Orvieto et al., 2023b).

Consider the singular value decomposition (SVD) of the matrix $V$

$V=\sum_{k=1}^{K}\sigma_{k}~{}v_{k}u_{k}^{\top}$ (75)

Then, a sufficient condition for stability is that for any $k=1,...,K$

$\displaystyle 0>\sigma_{k}\in\mathbb{R},\quad 0\leq
v_{k}\in\mathbb{R}^{N},\quad\text{and}\quad\langle
u_{k},\dot{\omega}^{\text{X}}_{t}\rangle\geq 0\ \text{ for any }t\in[0,T].$
(76)

####  C.1.1 The case of Mamba

In the case of Mamba (Gu & Dao, 2023) the matrices are diagonal and

$d\omega^{\text{X}}_{t}=softplus(Wx_{t}+\lambda)dt,\quad
d\xi^{\text{X}}_{t}=x_{t}\odot d\omega^{\text{X}}_{t},$

moreover the proposed choices of $V$ are all of type

$V=-\mathbf{v}\otimes\boldsymbol{1}_{d_{\omega}}$

for some choice of $0\leq\mathbf{v}\in\mathbb{R}^{N}$. Note that $softmax$ is
just a smooth approximation of $ReLU$ and that
$Im(ReLU)\subseteq\\{w\in\mathbb{R}^{d_{\omega}}:\langle\boldsymbol{1}_{d_{\omega}},w\rangle\geq
0\\}$ hence mamba is implicitly ensuring that the dynamical system is
approximately always well-conditioned.

###  C.2 Chaining

The diagonal case differs from the general one not only in the fact that the
class of approximable functions is much weaker but also in the necessity for
the presence of $\xi^{\text{X}}$ in order to obtain any path-dependence. The
term

$\int_{0}^{t}\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}$

becomes then a crucial component. At first sight one might think that such a
term allows to recover at least level two components of the Signature of
$(\omega^{\text{X}},\xi^{\text{X}})$, unfortunately things are not as easy as
they may seem. Notice how inside of the integral time is ”going backwards”
from the perspective of $\omega^{\text{X}}$, thus we can in general
approximate terms of type

$\int_{0}^{t}\int_{s}^{t}d\omega^{\text{X},i}_{r}d\xi^{\text{X},j}_{s}=\int_{1-t}^{1}\int_{1-t}^{r}d\overleftarrow{\omega}^{\text{X},i}_{r}d\overleftarrow{\xi}^{\text{X},j}_{s}=\text{Sig}((\overleftarrow{\omega}^{\text{X}},\overleftarrow{\xi}^{\text{X}}))^{i_{\omega}j_{\xi}}_{1-t,1}$

which are indeed terms of the Signature, but of the reverse paths
$\overleftarrow{\omega}^{\text{X}}_{r}=\omega^{\text{X}}_{1-r}$ and
$\overleftarrow{\xi}_{s}=\xi^{\text{X}}_{1-s}$!

######  Proposition C.1.

Fix a compact input set $\mathbb{X}$, continuous gates
$(\cdot)_{0},\omega,\xi$ and $X_{0}^{1}=1$. If the components of
$\xi^{\text{X}}$ are linear combinations of those of $\omega^{\text{X}}$, with
time-independent weights, then linear functionals on $Z^{\text{X}}_{t}$ can,
uniformly in $\mathbb{X}\times[0,1]$, approximate arbitrarily well the
following level $2$ terms of $Sig((\omega^{\text{X}},\xi^{\text{X}}))_{0,t}$:

$\int_{0}^{t}\int_{0}^{s}d\omega^{\text{X},i}_{r}d\xi^{\text{X},j}_{s}=\text{Sig}((\omega^{\text{X}},\xi^{\text{X}}))_{0,t}^{i_{\omega}j_{\xi}}$

###### Proof.

Under these hypotheses we know that linear functionals on $Z^{\text{X}}_{t}$
are uniformly dense, for continuous $\psi,\phi$, in

$\left\\{(X,t)\mapsto\psi(\omega^{\text{X}}_{t})\cdot
X_{0}+\int_{0}^{t}\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}\right\\}.$

Assume $\xi^{\text{X},j}_{s}=\langle\alpha_{j},\omega^{\text{X}}_{t}\rangle$
and consider the choices

$\psi(x)=(x^{i}\langle\alpha_{j},x\rangle,0,\cdots,0)^{\top},\quad\phi(x)=-(0,\cdots,0,x^{i},0,\cdots,0).$
(77)

so that

$\psi(\omega^{\text{X}}_{t})\cdot
X_{0}=\omega^{\text{X},i}_{t}\xi^{\text{X},j}_{t}\quad\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}=-(\omega^{\text{X},i}_{t}-\omega^{\text{X},i}_{s})d\xi^{\text{X},j}_{s}.$
(78)

To conclude note that

$\displaystyle\omega^{\text{X},i}_{t}\xi^{\text{X},j}_{t}=$
$\displaystyle\int_{s=0}^{t}\int_{r=0}^{t}d\omega^{\text{X},i}_{r}d\xi^{\text{X},j}_{s}=\int_{s=0}^{t}\int_{r=0}^{s}d\omega^{\text{X},i}_{r}d\xi^{\text{X},j}_{s}+\int_{s=0}^{t}\int_{r=s}^{t}d\omega^{\text{X},i}_{r}d\xi^{\text{X},j}_{s}$
$\displaystyle=$
$\displaystyle\int_{0}^{t}\int_{0}^{s}d\omega^{\text{X},i}_{r}d\xi^{\text{X},j}_{s}+\int_{s=0}^{t}(\omega^{\text{X},i}_{t}-\omega^{\text{X},i}_{s})d\xi^{\text{X},j}_{s}$

hence

$\int_{0}^{t}\int_{0}^{s}d\omega^{\text{X},i}_{r}d\xi^{\text{X},j}_{s}=\omega^{\text{X},i}_{t}\xi^{\text{X},j}_{t}-\int_{s=0}^{t}(\omega^{\text{X},i}_{t}-\omega^{\text{X},i}_{s})d\xi^{\text{X},j}_{s}=\psi(\omega^{\text{X}}_{t})\cdot
X_{0}+\int_{0}^{t}\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}$

∎

If $X\in C_{1,0}([0,1];\mathbb{R}^{d})$ we can use the previous result to
compute its Signature entries by chaining _diagonal_ linear CDEs.

######  Theorem C.2.

Assume a compact input set $\mathbb{X}\subset C_{1,0}([0,1];\mathbb{R}^{d})$.
For any $I\in\mathbb{W}_{d}$ with $|I|\geq 2$ and $\epsilon>0$ there is a
sequence of linear maps $W_{k}\in\mathbb{R}^{N_{k}\times 1}$ and weights for
the following family of _chained_ linear CDEs

$\displaystyle
dZ_{t}^{1,\text{X}}=\sum_{i=1}^{d}A^{(1)}_{i}Z^{1,\text{X}}_{t}dX^{i}_{t}+B^{(1)}d{{X}}_{t}\in\mathbb{R}^{N_{1}},\quad
Z^{1,\text{X}}_{0}=Z_{0}^{1},$ (79) $\displaystyle
dZ_{t}^{k+1,\text{X}}=\sum_{i=1}^{d+1}A^{(k+1)}_{i}Z^{k+1,\text{X}}_{t}d\begin{bmatrix}W_{k}Z^{k,\text{X}}\\\
{X}\end{bmatrix}^{i}_{t}+B^{(k+1)}dX_{t}\in\mathbb{R}^{N_{k+1}},\quad
Z^{k+1,\text{X}}_{0}=Z_{0}^{k+1},$ (80)

such that for some $v\in\mathbb{R}^{N_{|I|-1}}$ one has

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|Sig(X)^{I}_{0,t}-\langle
v,Z_{t}^{|I|-1,\text{X}}\rangle|\leq\epsilon$ (81)

###### Proof.

For $|I|=2$ we can apply Prop. C.1. Assume the theorem holds for $|I|\leq k$
and let $M:=\sup_{X\in\mathbb{X}}\left\lVert X\right\rVert_{1-var}$. Fix
$|Ij|=k+1$ and $W_{k-1}\in\mathbb{R}^{N_{k-1}\times 1}$ such that

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|Sig(X)^{I}_{0,t}-W_{k-1}Z_{t}^{k-1,\text{X}}|\leq\frac{\epsilon}{M}.$

Again by Prop. C.1 there are a $N_{k}$ and $v\in\mathbb{R}^{N_{k}}$ such that

$\sup\limits_{(X,t)\in\mathbb{X}\times[0,1]}|\int_{0}^{t}W_{k-1}Z_{s}^{k-1,\text{X}}dX^{j}_{s}-\langle
v,Z_{t}^{k,\text{X}}\rangle|\leq\epsilon.$

Then

$\displaystyle|\text{Sig}(X)^{Ij}_{0,t}-\langle
v,Z_{t}^{k,\text{X}}\rangle|\leq$
$\displaystyle|\int_{0}^{t}\text{Sig}(X)^{I}_{0,s}dX^{j}_{s}-\int_{0}^{t}W_{k-1}Z_{s}^{k-1,\text{X}}dX^{j}_{s}|+|\int_{0}^{t}W_{k-1}Z_{s}^{k-1,\text{X}}dX^{j}_{s}-\langle
v,Z_{t}^{k,\text{X}}\rangle|$ $\displaystyle\leq$
$\displaystyle\int_{0}^{t}|\text{Sig}(X)^{I}_{0,s}-W_{k-1}Z_{s}^{k-1,\text{X}}||dX^{j}_{s}|+\epsilon$
$\displaystyle\leq$
$\displaystyle\int_{0}^{t}\frac{\epsilon}{M}|dX^{j}_{s}|+\epsilon\leq
2\epsilon$

thus concluding the proof. ∎

####  C.2.1 $ReLU$ activation choice

Models like _Mamba_ do not only use diagonal matrices but also consider
controls of a specific kind:

$\omega^{\text{X}}_{t}=\int_{0}^{t}ReLU(WX_{s}+b)ds$

The choice of $ReLU$ enforces $\dot{\omega}_{t}\geq 0$ for all times as seen
above, but could, a priori, destroy information about $X$ which allows for the
recovery, after chaining, of its Signature.

Does this choice keep some expressivity? Fortunately almost all of it: since

$ReLU(x)-ReLU(-x)=x$

one can choose a linear map $W$ which allows to linearly recover

$\tilde{\omega}_{t}^{\text{X}}=\int_{0}^{t}X_{s}ds$

from $\omega^{\text{X}}_{t}$. By correspondingly modifying the form of $\psi$
and $\phi$ in Eqn. (77) such that

$\psi(\omega^{\text{X}}_{t})\cdot
X_{0}=\tilde{\omega}^{\text{X},i}_{t}\xi^{\text{X},j}_{t}\quad\phi(\omega^{\text{X}}_{t}-\omega^{\text{X}}_{s})\cdot
d\xi^{\text{X}}_{s}=-(\tilde{\omega}^{\text{X},i}_{t}-\tilde{\omega}^{\text{X},i}_{s})d\xi^{\text{X},j}_{s}.$
(82)

one is able, through a similar chaining procedure, to recover arbitrarily deep
entries of the Signature of
$\tilde{\omega}_{t}^{\text{X}}=\int_{0}^{t}X_{s}ds$.

##  Appendix D Path-to-Path

######  Definition D.1.

A map $G\in C^{0}(C_{1,0}([0,1];\mathbb{R}^{d})\times[0,1];\mathbb{R})$ is
_causal_ iff for all $t\in[0,1]$ and paths $\omega,\tilde{\omega}\in
C_{1,0}([0,1];\mathbb{R}^{d})$ one has

$\omega|_{[0,t]}=\tilde{\omega}|_{[0,t]}\implies
G(\omega,t)=G(\tilde{\omega},t)$

_i.e._ G is _causal_ if it does not look in the future.

######  Proposition D.2.

Assume a compact input set $\mathbb{X}$, continuous $(\cdot)_{0},\omega,\xi$,
$X_{0}^{1}\equiv 1$ and $\omega^{\text{X},1}_{t}\equiv t$. Then for all
$\epsilon>0$ and all _causal_ $G\in
C^{0}(C_{1,0}([0,1];\mathbb{R}^{d_{\omega}})\times[0,1];\mathbb{R})$ there
exist an integer $N\geq 0$, some Feed Forward neural network
$F:\mathbb{R}^{N}\to\mathbb{R}$, and parameters $C\in\mathbb{R}^{N\times
d_{0}},A_{i}\in\mathbb{R}^{N\times N},B\in\mathbb{R}^{N\times d_{\xi}}$ such
that

$\sup\limits_{X\in\mathbb{X}}\sup\limits_{t\in[0,1]}|F(Z^{\text{X}}_{t})-G(\omega^{\text{X}},t)|<\epsilon$
(83)

###### Proof.

Fix $\epsilon>0$. By B.7 the space
${\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ contains all
functionals of form

$(X,t)\mapsto\langle\alpha,\text{Sig}(\omega^{\text{X}})_{0,t}\rangle$

thus, by the properties of the signature and by compactness of $\mathbb{X}$,
for any fixed $s_{0}\in[0,1]$ there is some
$f\in{\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ such that

$\sup\limits_{X\in\mathbb{X}}|f(X,s_{0})-G(\omega^{\text{X}},s_{0})|<\epsilon$

Using the fact that $G\in
C^{0}([0,1];C^{0}(C_{1,0}([0,1];\mathbb{R}^{d_{\omega}});\mathbb{R}))$ and
compactness of $[0,1]$, we find a finite set $\\{0\leq s_{0}\leq\dots\leq
s_{M}\leq 1\\}$ of points and
$f_{0},\dots,f_{M}\in{\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$
such that

$\displaystyle\sup\limits_{(X,s)\in\mathbb{X}\times[s_{i-1},s_{i+1}]}|G(\omega^{\text{X}},s)-G(\omega^{\text{X}},s_{i})|<\epsilon$
(84)
$\displaystyle\sup\limits_{X\in\mathbb{X}}|f_{i}(X,s_{i})-G(\omega^{\text{X}},s_{i})|<\epsilon$
(85)
$\displaystyle\sup\limits_{(X,s)\in\mathbb{X}\times[s_{i-1},s_{i+1}]}|f_{i}(X,s)-f_{i}(X,s_{i})|<\epsilon$
(86)

for $i=0,\dots,M-1$. Notice then how for all $X\in\mathbb{X}$ and
$s\in[s_{i-1},s_{i+1}]$

$\displaystyle|f_{i}(X,s)-G(\omega^{\text{X}},s)|\leq$
$\displaystyle~{}|f_{i}(X,s)-f_{i}(X,s_{i})|+|f_{i}(X,s_{i})-G(\omega^{\text{X}},s_{i})|+|G(\omega^{\text{X}},s_{i})-G(\omega^{\text{X}},s)|\leq~{}3\epsilon$

It follows that the map $F\in C^{0}([0,1]\times\mathbb{X};\mathbb{R})$
linearly interpolating the $f_{i}$ in time satisfies

$\sup\limits_{X\in\mathbb{X}}\sup\limits_{t\in[0,1]}|F(X)_{t}-G(\omega^{\text{X}},t)|<6\epsilon$

To conclude note that $\mathbb{X}$ being compact, the $f_{i}$ take values in a
common compact set $K\subseteq\mathbb{R}$. There exist then a neural network
$\Psi:[0,1]\times K^{M}\to\mathbb{R}$ such that

$\sup\limits_{i\in
0,\dots,M-1}\sup\limits_{s\in[s_{i},s_{i+1}]}|\Psi(t,z)-\left(\frac{s_{i+1}-s}{s_{i+1}-s_{i}}z_{i}+\frac{s-s_{i}}{s_{i+1}-s_{i}}z_{i+1}\right)|<\epsilon$

which means that

$\sup\limits_{X\in\mathbb{X}}\sup\limits_{t\in[0,1]}|\Psi(t,f_{0}(X,t),\dots,f_{M}(X,t))-F(X,t)|<\epsilon$

Recalling that $\omega^{\text{X},1}_{t}=t$ we get that $X\mapsto\\{t\mapsto
t\\}\in{\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ so that, given
density of linear maps on $Z^{\text{X}}$ in the space,
$\Psi(t,f_{0}(X,t),\dots,f_{M}(X,t))$ can be uniformly approximated.
Triangular inequality gives finally

$\sup\limits_{X\in\mathbb{X}}\sup\limits_{t\in[0,1]}|\Psi(t,f_{0}(X,t),\dots,f_{M}(X,t))-G(\omega^{\text{X}},t)|<7\epsilon$

which, by arbitrariness of $\epsilon$, gives the thesis. ∎

The non-linearity is crucial for the path-to-path result. A map of type
$(\omega,t)\mapsto\langle t\alpha,\text{Sig}(\omega)_{0,t}\rangle$ cannot be
approximated arbitrarily well by
$(\omega,t)\mapsto\langle\beta,\text{Sig}(\omega)_{0,t}\rangle$.

In any case, note that in the proof the role of the neural network is only
that of interpolating the RKHS elements in the right order and at the right
time. All the non-linear complexity of learning the particular $G$ is
offloaded and taken care of by the RKHS elements.

######  Remark D.3.

In the proof we have only considered the part of $T(X)$ concerning
$\omega^{\text{X}}$, but $T(X)_{t}$ depends linearly on $X_{0}$ and
$\xi^{\text{X}}$ suggesting that neural networks on
${\mathcal{H}}^{\tiny(\cdot)_{0},\omega,\eta}_{[0,1]}$ have stronger
generalization properties. In fact one can prove that it is possible to
approximate all continuous $G(X_{0},\omega^{\text{X}},\xi^{\text{X}},t)$, this
is done by reconstructing $X_{0}$ and $\xi^{\text{X}}_{[0,1]}$ as in the
classical SSM case _cf._ (Orvieto et al., 2023a).

##  Appendix E Wronskian Matrix Theory

In this section we obtain a unified theory studying the solutions to general
linear CDEs. The results presented here are not new and can be found in
different terms in the literature (Friz & Victoir, 2010), despite this we have
decided to reproduce them from scratch for completeness, notational reasons
and to present a self-contained theory.

######  Theorem E.1.

For any choice $\\{A^{1},\dots,A^{d}\\}\subseteq
C^{0}([0,1];\mathbb{R}^{N\times N})$ and $\omega\in
C_{1}([0,1];\mathbb{R}^{d})$ there exist a unique map $W\in
C^{0}([0,1]\times[0,1];\mathbb{R}^{N\times N})$ solving the following CDE

$W_{s,t}=Id_{N}+\sum_{i=1}^{d}\int_{\tau=s}^{t}A_{\tau}^{i}W_{s,\tau}d\omega^{i}_{\tau}$
(87)

###### Proof.

We will use Banach fixed point theorem leveraging the completeness of the
space $\Omega:=C^{0}([0,1]\times[0,1];\mathbb{R}^{N\times N})$ with the
uniform norm

$\left\lVert X\right\rVert_{\infty}:=\sup_{s,t\in[0,1]}\left\lVert
X_{s,t}\right\rVert_{op}$

Define the map $\Gamma:\Omega\to\Omega$ as

$\Gamma(X)_{s,t}=Id_{N}+\sum_{i=1}^{d}\int_{\tau=s}^{t}A_{\tau}^{i}X_{s,\tau}d\omega^{i}_{\tau}$

One has, for $X,Y\in\Omega$ and $k\in\mathbb{N}$ setting
$\Gamma^{0}=Id_{\Omega}$, that

$\Gamma^{k+1}(X)_{s,t}-\Gamma^{k+1}(Y)_{s,t}=\sum_{i=1}^{d}\int_{\tau=s}^{t}A_{\tau}^{i}\left(\Gamma^{k}(X)_{s,\tau}-\Gamma^{k}(Y)_{s,\tau}\right)d\omega^{i}_{\tau}$

which iterated gives

$\displaystyle\Gamma^{k+1}(X)_{s,t}-\Gamma^{k+1}(Y)_{s,t}=$
$\displaystyle\sum_{\begin{subarray}{c}I\in\mathcal{W}_{d}\\\
|I|=k+1\end{subarray}}\int_{\tau_{k+1}=s}^{t}\cdots\int_{\tau_{1}=s}^{\tau_{2}}\left(\prod_{j=k+1}^{1}A^{I_{j}}_{\tau_{j}}\right)\left(X_{s,\tau_{1}}-Z_{s,\tau_{1}}\right)\prod_{j=1}^{k+1}d\omega^{I_{j}}_{\tau_{j}}$
$\displaystyle=$ $\displaystyle\sum_{\begin{subarray}{c}I\in\mathcal{W}_{d}\\\
|I|=k+1\end{subarray}}\int_{\tau\in\Delta^{k+1}_{[s,t]}}A^{I}_{\tau}\left(X_{s,\tau_{1}}-Z_{s,\tau_{1}}\right)d\omega^{I}_{\tau}$

where $\mathcal{W}_{d}$ is the set of words in the alphabet $\\{1,\dots,d\\}$
and

$\Delta^{k}_{[s,t]}:=\\{(\tau_{1},\dots,\tau_{k})\in[0,1]^{k}:\forall
j\in{1,\dots,k-1}.\hskip 5.0pt\tau_{j}\leq\tau_{j+1}\\}$
$A^{I}_{\tau}:=\prod_{j=k+1}^{1}A^{I_{j}}_{\tau_{j}}\hskip
10.0ptd\omega^{I}_{\tau}:=\prod_{j=1}^{k+1}d\omega^{I_{j}}_{\tau_{j}}$

By defining $M=\max\\{\left\lVert
A^{i}\right\rVert_{\infty}:i\in\\{1,\dots,d\\}\\}$ then one clearly has

$\left\lVert\Gamma^{k}(X)-\Gamma^{k}(Y)\right\rVert_{\infty}\leq\frac{(dM\left\lVert\omega\right\rVert_{1-var})^{k}}{k!}\left\lVert
X-Y\right\rVert_{\infty}$ (88)

thus definitely (in $k$) the map $\Gamma^{k}$ is a contraction. By Banach
fixed point there exist a unique fixed point $W\in\Omega$. ∎

######  Theorem E.2.

Under the assumptions of the previous theorem one can write $W_{s,t}$
explicitly as

$W_{s,t}=\sum_{I\in\mathcal{W}_{d}}\int_{\tau\in\Delta^{|I|}_{[s,t]}}A^{I}_{\tau}d\omega^{I}_{\tau}$
(89)

moreover if for all $i$ the matrix-valued maps are constant on all $[0,1]$
_i.e._ $A^{i}_{t}\equiv A_{i}$ then

$W_{s,t}=\sum_{I\in\mathcal{W}_{d}}A_{I}\text{Sig}(\omega)_{s,t}^{I}$ (90)

where $\text{Sig}(\omega)_{s,t}^{I}$ is the Signature of the path $\omega$.

###### Proof.

The second assertion follows from the first by definition of the Signature of
a path.

Regarding the first notice how the series is absolutely convergent in
$\mathbb{R}^{N\times N}$, uniformly in $s,t$ since

$\displaystyle\sum_{I\in\mathcal{W}_{d}}\left\lVert\int_{\tau\in\Delta^{|I|}_{[s,t]}}A^{I}_{\tau}d\omega^{I}_{\tau}\right\rVert_{op}\leq$
$\displaystyle\sum_{k=0}^{\infty}d^{k}M^{k}\frac{\left\lVert\omega\right\rVert_{1-var,[s,t]}^{k}}{k!}$
$\displaystyle=$ $\displaystyle
e^{dM\left\lVert\omega\right\rVert_{1-var,[s,t]}}\leq
e^{dM\left\lVert\omega\right\rVert_{1-var,[0,1]}}$

thus for any $s,t\in[0,1]$ the series defines an element of
$\tilde{W}_{s,t}\in\mathbb{R}^{N\times N}$.

Using the uniformity of this bound and the fact that for all
$I\in\mathcal{W}_{d}$ one has

$\tilde{W}_{s,t}^{I}:=\int_{\tau\in\Delta^{|I|}_{[s,t]}}A^{I}_{\tau}d\omega^{I}_{\tau}\in\Omega$

as a function of $(s,t)$, which moreover is uniformly continuous

$\displaystyle\left\lVert\tilde{W}_{s_{1},t_{1}}^{I}-\tilde{W}_{s_{2},t_{2}}^{I}\right\rVert_{op}=$
$\displaystyle\left\lVert\int_{\tau\in\Delta^{|I|}_{[s_{1}\wedge
s_{2},t_{1}\vee
t_{2}]}}(\delta_{\tau\in\Delta^{|I|}_{[s_{1},t_{1}]}}-\delta_{\tau\in\Delta^{|I|}_{[s_{2},t_{2}]}})A^{I}_{\tau}d\omega^{I}_{\tau}\right\rVert_{op}$
$\displaystyle\leq$ $\displaystyle
M^{|I|}\int_{\tau\in\Delta^{|I|}_{[s_{1}\wedge s_{2},t_{1}\vee
t_{2}]}}\left|\delta_{\tau\in\Delta^{|I|}_{[s_{1},t_{1}]}}-\delta_{\tau\in\Delta^{|I|}_{[s_{2},t_{2}]}}\right||d\omega^{I}_{\tau}|$
$\displaystyle\leq$ $\displaystyle
M^{|I|}{\left\lVert\omega\right\rVert^{|I|}_{[s_{1}\wedge s_{2},s_{1}\vee
s_{2}]\cup[t_{1}\wedge t_{2},t_{1}\vee t_{2}]}},$

one concludes that $\tilde{W}_{s,t}\in\Omega$. Finally notice that
$\tilde{W}_{s,t}$ is a fixed point of $\Gamma$

$\displaystyle\Gamma(\tilde{W}_{s,t})=$ $\displaystyle
Id_{N}+\sum_{i=1}^{d}\int_{\tau=s}^{t}A_{\tau}^{i}\left(\sum_{I\in\mathcal{W}_{d}}\int_{\tau\in\Delta^{|I|}_{[0,1]}}A^{I}_{\tau}d\omega^{I}_{\tau}\right)d\omega^{i}_{\tau}$
$\displaystyle=$ $\displaystyle
Id_{N}+\sum_{\begin{subarray}{c}I\in\mathcal{W}_{d}\\\ |I|\geq
1\end{subarray}}\int_{\tau\in\Delta^{|I|}_{[0,1]}}A^{I}_{\tau}d\omega^{I}_{\tau}d\omega^{i}_{\tau}$
$\displaystyle=$
$\displaystyle\sum_{I\in\mathcal{W}_{d}}\int_{\tau\in\Delta^{|I|}_{[0,1]}}A^{I}_{\tau}d\omega^{I}_{\tau}=\tilde{W}_{s,t}$

and conclude by uniqueness. ∎

######  Proposition E.3.

Under the previous conditions, the unique solution of the $N$-dimensional CDE

$dX_{t}=X_{0}+\sum_{i=1}^{d}\int_{\tau=0}^{t}A^{i}_{\tau}X_{\tau}d\omega^{i}_{\tau}$
(91)

is given by

$X_{t}=W_{0,t}X_{0}$ (92)

###### Proof.

The solutions are unique by standard results (Friz & Victoir, 2010)[Thm. 3.7],
moreover

$\displaystyle W_{0,t}X_{0}=$
$\displaystyle\left(Id_{N}+\sum_{i=1}^{d}\int_{\tau=0}^{t}A_{\tau}^{i}W_{0,\tau}d\omega^{i}_{\tau}\right)X_{0}=X_{0}+\sum_{i=1}^{d}\int_{\tau=0}^{t}A_{\tau}^{i}(W_{0,\tau}X_{0})d\omega^{i}_{\tau}$

∎

######  Proposition E.4.

The Wronskian matrix has the following properties:

  1. 1.

$\forall r,s,t\in[0,1].\hskip 10.0ptW_{r,t}=W_{s,t}W_{r,s}$

  2. 2.

$\forall s,t\in[0,1].\hskip 10.0ptW_{s,t}^{-1}=W_{t,s}$

  3. 3.

$\forall s,t\in[0,1].\hskip
10.0ptW_{s,t}=Id_{N}+\sum_{i=1}^{d}\int_{\sigma=s}^{t}W_{\sigma,t}A^{i}_{\sigma}d\omega^{i}_{\sigma}$

###### Proof.

Regarding the first statement notice that for all $X_{0}\in\mathbb{R}^{N}$ one
has

$\displaystyle\tilde{X}_{t}:=$ $\displaystyle
W_{s,t}W_{r,s}X_{0}=\left(Id_{N}+\sum_{i=1}^{d}\int_{\tau=s}^{t}A_{\tau}^{i}W_{s,\tau}d\omega^{i}_{\tau}\right)W_{r,s}X_{0}$
$\displaystyle=$ $\displaystyle
W_{r,s}X_{0}+\sum_{i=1}^{d}\int_{\tau=s}^{t}A_{\tau}^{i}(W_{s,\tau}W_{r,s}X_{0})d\omega^{i}_{\tau}$
$\displaystyle=$ $\displaystyle
W_{r,s}X_{0}+\sum_{i=1}^{d}\int_{\tau=s}^{t}A_{\tau}^{i}\tilde{X}_{\tau}d\omega^{i}_{\tau}$

and by the previous proposition also

$X_{t}:=W_{r,t}X_{0}=W_{r,t}X_{0}+\sum_{i=1}^{d}\int_{\tau=r}^{t}A_{\tau}^{i}X_{\tau}d\omega^{i}_{\tau}$

thus $X_{t}$ and $\tilde{X}_{t}$ solve the same $CDE$ and coincide at time
$t=s$. This means, by uniqueness, that $X_{t}$ and $\tilde{X}_{t}$ coincide
for all times; hence $W_{s,t}W_{r,s}$ and $W_{r,t}$ coincide for all times too
since for any choice of $X_{0}$ one has $W_{s,t}W_{r,s}X_{0}=W_{r,t}X_{0}$.

The second statement follows from the previous one setting first $r=t$ and
subsequently exchanging $s$ and $t$.

To prove the third equality note that

$0=d_{s}(W_{s,t}W_{t,s})=(d_{s}W_{s,t})W_{t,s}+W_{s,t}(d_{s}W_{t,s})$

hence

$d_{s}W_{s,t}=-W_{s,t}(d_{s}W_{t,s})W_{t,s}^{-1}=-W_{s,t}(\sum_{i=1}^{d}A^{i}_{s}W_{t,s}d\omega^{i}_{s})W_{t,s}^{-1}=-\sum_{i=1}^{d}W_{s,t}A^{i}_{s}d\omega^{i}_{s}$

∎

######  Proposition E.5 (Liouville’s Formula).

Under the assumptions of the previous theorems, if $\omega\in
C^{1}([0,1];\mathbb{R}^{d})$ then

$det(W_{s,t})=1+\sum_{i=1}^{d}\int_{\tau=s}^{t}tr(A^{i}_{\tau})det(W_{s,t})d\omega^{i}_{\tau}=\exp\left(\sum_{i=1}^{d}\int_{\tau=s}^{t}tr(A^{i}_{\tau})d\omega^{i}_{\tau}\right)$
(93)

###### Proof.

This just follows from the classical case since we can write