arXiv:1712.00754v2 [cs.NE] 2 Mar 2018

Universal discrete-time reservoir computers with
stochastic inputs and linear readouts using
non-homogeneous state-affine systems
Lyudmila Grigoryeva1 and Juan-Pablo Ortega2,3
Abstract
A new class of non-homogeneous state-affine systems is introduced for use in reservoir computing.
Sufficient conditions are identified that guarantee first, that the associated reservoir computers with
linear readouts are causal, time-invariant, and satisfy the fading memory property and second, that
a subset of this class is universal in the category of fading memory filters with stochastic almost
surely uniformly bounded inputs. This means that any discrete-time filter that satisfies the fading
memory property with random inputs of that type can be uniformly approximated by elements in
the non-homogeneous state-affine family.

Key Words: reservoir computing, state-affine systems, SAS, echo state networks, ESN, echo state
affine systems, ESAS, machine learning, universality, fading memory property, linear training, stochastic
signal treatment.

1

Introduction

A reservoir computer (RC) [Jaeg 10, Jaeg 04, Maas 02, Maas 11, Croo 07, Vers 07, Luko 09] or a RC
system is a specific type of recurrent neural network determined by two maps, namely a reservoir
F : RN × Rn −→ RN , n, N ∈ N, and a readout map h : RN → R that under certain hypotheses
transform (or filter) an infinite discrete-time input z = (. . . , z−1 , z0 , z1 , . . .) ∈ (Rn )Z into an output
signal y ∈ RZ of the same type using the state-space transformation given by:


xt = F (xt−1 , zt ),

(1.1)

yt = h(xt ),

(1.2)

where t ∈ Z and the dimension N ∈ N of the state vectors xt ∈ RN will be referred to as the number
of virtual neurons of the system. The expressions (1.1)-(1.2) determine a nonlinear state-space system
and many of its dynamical properties (stability, controlability) have been studied for decades in the
literature from that point of view.
In supervised machine learning applications, the reservoir map is very often randomly generated
(see, for instance, the echo state networks in [Jaeg 10, Jaeg 04]) and the memoryless readout is trained
1 Department of Mathematics and Statistics.
Universität Konstanz. Box 146. D-78457 Konstanz. Germany.
Lyudmila.Grigoryeva@uni-konstanz.de
2 Universität Sankt Gallen. Faculty of Mathematics and Statistics. Bodanstrasse 6. CH-9000 Sankt Gallen. Switzerland. Juan-Pablo.Ortega@unisg.ch
3 Centre National de la Recherche Scientifique (CNRS). France.

1

Universal reservoir computers using non-homogeneous state-affine systems

2

so that the output matches a given teaching signal that we will denote by d ∈ RZ . Two important
advantages of this approach lay on the fact that they reduce the training of a dynamic task to a static
problem and, moreover, if the reservoir map is rich enough, good performances can be attained with
readouts that have a relatively simple functional form. Indeed, in many occasions it suffices to use an
affine map h : RN → R that is trained via a (eventually regularized) linear regression that minimizes
the Euclidean distance between the output y and the teaching signal d. These features circumvent
well-known difficulties in the training of generic recurrent neural networks having to do with bifurcation
phenomena that render classical gradient descent methods non-convergent [Doya 92].
There are two central questions that need to be addressed when designing a machine learning
paradigm, namely, the capacity and the universality problems. The capacity problem concerns the
estimation of the error that is going to be committed in the execution of a specific task. This estimation
can have the form of generic bounds that incorporate various architecture parameters of the system like
in [Pisi 81, Jone 92, Barr 93, Kurk 05]. In the specific context of reservoir computing, it has been the
subject of much research [Jaeg 02, Whit 04, Gang 08, Herm 10, Damb 12, Grig 15, Coui 16, Grig 16a].
The universality problem consists in showing that the set of input/output functionals that can be
generated with a specific architecture is dense in a sufficiently rich class, like the one containing, for
example, all continuous or all measurable functionals. For classical machine learning paradigms like
neural networks, this question has given rise to well-known results [Kolm 56, Arno 57, Spre 65, Spre 96,
Spre 97, Cybe 89, Horn 89, Rusc 98] that show that they can be considered as universal approximators
in a static and deterministic setup.
There is no general recipe that allows one to conclude the universality of a given supervised machine
learning paradigm. The proof strategy depends much on the specific paradigm itself and, more importantly, on the nature of the inputs and the outputs. In the context of reservoir computing there are
several situations for which universality has been established when the inputs/outputs are deterministic, that is, when dealing with real-valued curves or time series. There are two features that influence
significantly the level of mathematical sophistication that is needed to conclude universality: first, the
compactness of the time domain under consideration and second, if one works in continuous or discrete
time. In the following paragraphs we briefly review the results that have already been obtained and, in
passing, we present and put in context the contributions contained in this paper.
The compactness of the time domain is crucial because, as we will see later on, universality is
obtained as a consequence of various versions of the Stone-Weierstrass, that is invariably formulated
for functions defined on a compact metric space. When the time domain is compact, this property is
naturally inherited by the spaces relevant in the proofs. However, when it is not, it is obtained by
restricting the study to functionals that satisfy a condition introduced in [Boyd 85] and known as the
fading memory property. The distinction between continuous and discrete time inputs is justified
by the availability in the continuous setup of different tools coming from functional analysis that do not
exist for discrete time.
Reservoir computing universality for compact time domains is obtained as a corollary of classical
results in systems theory. Indeed, in the continuous time setup, it can be established [Flie 76, Suss 76] for
linear systems using polynomial readouts or with bilinear systems using linear readouts. In the discretetime setup, the situation is more convoluted when the readout is linear and required the introduction
in [Flie 80] of the so-called (homogeneous) state-affine systems (SAS) (see also [Sont 79a, Sont 79b]).
The extension of these results to continuous non-compact time intervals was carried out in [Boyd 85] for
fading memory filters using exponentially stable linear RCs with polynomial readouts and their bilinear
counterparts with linear readouts (see also [Maas 00, Maas 02, Maas 04, Maas 07]). An extension to
the non-compact discrete-time setup based on the Stone-Weierstrass theorem is, to our knowledge, not
available in the literature. This problem has only been tackled from an internal approximation point of
view, which consists in uniformly approximating the reservoir and readout maps in (1.1)-(1.2) in order to
obtain an approximation of the resulting filter; this strategy has been introduced in [Matt 92, Matt 93]

Universal reservoir computers using non-homogeneous state-affine systems

3

for absolutely summable systems. The proofs in those works were unfortunately based on an invalid
compactness assumption. Even though corrections were proposed in [Perr 96, Stub 97a], this approach
yields, in the best of cases, universality only within the reservoir filter category, while we aim at proving
that statement in the much larger category of fading memory filters.
Our paper contains the following four main contributions:
• A non-homogeneous variant of the state-affine systems in [Flie 80] is introduced and we identify
sufficient conditions that guarantee that the associated reservoir computers with linear readouts
have the echo state property, are causal, time-invariant, and satisfy the fading memory property.
• A subset of this class is characterized that is universal in the category of fading memory filters
with uniformly bounded inputs.
• These results are extended to the stochastic setup by formulating a version of this universality
result that is valid for almost surely uniformly bounded inputs. This result shows that any discretetime filter that has the fading memory property with almost surely uniformly bounded stochastic
inputs can be uniformly approximated by elements in the non-homogeneous state-affine family.
• The universal non-homogeneous state-affine family suggests a generalization of the echo state
networks introduced in [Jaeg 04] that have been very successful in many information processing
tasks. We call this generalization echo state affine systems (ESAS) and we empirically show
that they outperform echo state networks in a standard benchmark forecasting task having to do
with the chaotic time series generated by the Mackey-Glass system [Mack 77].
Despite some preexisting work on the uniform approximation in probability of stochastic systems
with finite memory [Perr 96, Perr 97, Stub 97b], the universality result in the stochastic setup is, to our
knowledge, the first of its type in the literature and opens the door to new developments in the learning of
stochastic processes and their obvious applications to forecasting [Galt 14]. Indeed, in the deterministic
setup, RC has been very successful (see for instance [Jaeg 04]) at the time of learning the attractors
of various dynamical systems which, in passing, is used for forecasting by continuing the paths of the
system in question using its synthetically learnt proxy. This approach led to several orders of magnitude
accuracy improvements with respect to most standard dynamical systems forecasting tecniques based
on Takens’ Theorem [Take 81] and we expect that should have analogous beneficial effects in the density
forecasting of stochastic processes that satisfy the hypotheses of the results that are formulated later
on in the paper.

2

Notation, definitions, and preliminary discussions

Vector and matrix notations. Polynomials. A column vector is denoted by a bold lower case
symbol like r and r> indicates its transpose. Given a vector v ∈ Rn , we denote its entries by vi , with
i ∈ {1, . . . , n}; we also write v = (vi )i∈{1,...,n} . We denote by Mn,m the space of real n × m matrices
with m, n ∈ N. When n = m, we use the symbol Mn to refer to the space of square matrices of
order n. Given a matrix A ∈ Mn,m , we denote its components by Aij and we write A = (Aij ), with
i ∈ {1, . . . , n}, j ∈ {1, . . . m}. Given a vector v ∈ Rn , the symbol kvk stands for its Euclidean norm.
For any A ∈ Mn,m , kAk2 denotes its matrix norm induced by the Euclidean norms in Rm and Rn , and
satisfies [Horn 13, Example 5.6.6] that kAk2 = σmax (A), with σmax (A) the largest singular value of A.
kAk2 is sometimes referred to as the spectral norm of A [Horn 13].
Given an element z ∈ Rn , we denote by R[z] the real-valued multivariate polynomials on z with real
coefficients. Analogously, Pol(Rn , R) will denote the set of real-valued polynomials on Rn . When z ∈ R

Universal reservoir computers using non-homogeneous state-affine systems

4

is a scalar and m, n ∈ N, we define the set Mm,n [z] of Mm,n -valued polynomials on z with coefficients
in Mm,n as
Mm,n [z] := {A0 + zA1 + z 2 A2 + · · · + z N AN | N ∈ N, A0 , A1 , A2 , . . . , AN ∈ Mm,n }.

(2.1)

Filters. The symbol (Rn )Z denotes the set of infinite real sequences of the form z = (. . . , z−1 , z0 , z1 , . . .),
zi ∈ Rn ; (Rn )Z− and (Rn )Z+ are the subspaces consisting of, respectively, left and right infinite sequences: (Rn )Z− = {z = (. . . z−2 , z−1 , z0 ) | zi ∈ Rn }, (Rn )Z+ = {z = (z0 , z1 , z2 , . . .) | zi ∈ Rn }. In most
cases we shall use in these infinite product spaces either the product topology (see [Munk 14, Chapter
2]) or the topology induced by the supremum norm kzk∞ := supn∈Z {. . . , z−1 , z0 , z1 , . . .}. The symbols
n
`∞ (Rn ) and `∞
± (R ) will be used to denote the Banach spaces formed by the elements in those infinite
product spaces that have a finite supremum norm k · k∞ .
We will refer to the maps of the type U : (Rn )Z −→ RZ as filters or operators and to those like
H : (Rn )Z −→ R (or H : (Rn )Z± −→ R) as functionals. A filter U : (Rn )Z −→ RZ is called causal
when for any two elements z, w ∈ RZ that satisfy that zτ = wτ for any τ ≤ t, for a given t ∈ Z, we have
that (U z)t = (U w)t . The filter U is called time-invariant when, for any τ ∈ Z, it commutes with the
associated time delay operator Uτ : (Rn )Z −→ (Rn )Z defined by (Uτ z)t := zt−τ , that is, Uτ ◦ U = U ◦ Uτ
(in this expression, the two time delay operators Uτ have to be understood as defined in the appropriate
sequence spaces). We recall (see for instance [Boyd 85]) that there is a bijection between causal timeinvariant filters and functionals on (Rn )Z− . Indeed, given a time-invariant filter U , we can associate
to it a functional HU : (Rn )Z− −→ R via the assignment HU (z) := U (ze )0 , where ze ∈ (Rn )Z is an
arbitrary extension of z ∈ (Rn )Z− to (Rn )Z . Conversely, for any functional H : (Rn )Z− −→ R, we can
define a time-invariant causal filter UH : (Rn )Z −→ (Rn )Z by UH (z)t := H(PZ− ◦ U−t (z)), where U−t is
the (−t)-time delay operator and PZ− : (Rn )Z −→ (Rn )Z− is the natural projection. It is easy to verify
that:
HUH

= H,

for any functional H : (Rn )Z− −→ R,

UHU

= U,

for any causal time-invariant filter

U : (Rn )Z −→ RZ .

Additionally, let H1 , H2 : (Rn )Z− −→ R and λ ∈ R, then UH1 +λH2 z = UH1 z+λUH2 z, for any z ∈ (Rn )Z .
Reservoir filters. Consider now the RC system determined by (1.1)–(1.2) and assume, additionally,
Z
that the following existence and uniqueness property holds: for each z ∈ (Rn ) there exists a unique

Z
x ∈ RN such that for each t ∈ Z, the relation (1.1) holds. This condition is known in the literature as
the echo state property [Jaeg 10, Yild 12] and has deserved much attention in the context of echo state
networks [Jaeg 04, Bueh 06, Bai 12, Wain 16, Manj 13]. We emphasize that the echo state property is
a genuine condition that is not automatically satisfied by all RC systems.
RC systems that satisfy the echo state property have a naturally associated filter. We will denote by
U F : (Rn )Z −→ (RN )Z the filter determined by the reservoir map via (1.1), that is, (U F z)t := xt ∈ RN
and by UhF : (Rn )Z −→ RZ the one determined by the entire reservoir system, that is, (UhF z)t := yt . UhF
will be called the reservoir filter associated to the RC system (1.1)–(1.2). The filters U F and UhF are
causal by construction and it can also be shown that they are necessarily time-invariant [Grig 18]. We
can hence associate to UhF a reservoir functional HhF : (Rn )Z− −→ R determined by HhF := HUhF .
Weighted norms and the fading memory property (FMP). Let w : N −→ (0, 1] be a decreasing
sequence with zero limit and D ⊂ Rn . We define the associated weighted norm k·kw on DZ− ⊂ (Rn )Z−
associated to the weighting sequence w as the map:
k · k w : D Z−
z

R+
−→
7−→ kzkw := supt∈Z− kzt w−t k,

Universal reservoir computers using non-homogeneous state-affine systems
where k · k denotes the Euclidean norm in Rn . It is worth noting that the space
n
o
n
n Z−
`∞
| kzkw < ∞ ,
w (R ) := z ∈ (R )

5

(2.2)

endowed with weighted norm k · kw forms a Banach space [Grig 18].
All along the paper, we will work with uniformly bounded families of sequences, both in the
deterministic and the stochastic setups. The two main properties of these subspaces in relation with
the weighted norms are spelled out in the following two lemmas.
Lemma 2.1 Let M > 0 and let KM be the set of uniformly bounded elements in DZ− by M , that is,

KM := z ∈ DZ− | kzt k ≤ M for all t ∈ Z− .
(2.3)
Then, for any weighting sequence w and z ∈ KM , we have that kzkw < ∞.
Additionally, let λ, ρ ∈ (0, 1) and let w, wρ , w1−ρ be the weighting sequences given by wt := λt ,
ρ
wt := λρt , wt1−ρ := λ(1−ρ)t , t ∈ N. Then, the following series are convergent and satisfy the inequalities:
∞
X
t=0
∞
X

kz−t kwt
kz−t kwt

t=0

=
=

∞
X
t=0
∞
X

1
,
1 − λρ

(2.4)

1
.
1 − λ1−ρ

(2.5)

kz−t kλt ≤ kzkw1−ρ
kz−t kλt ≤ kzkwρ

t=0

The following result is a discrete-time version of Lemma 1 in [Boyd 85] that is easily obtained by
noticing that in the discrete-time setup all functions are trivially continuous if we consider the discrete
topology for their domains and, moreover, all families of functions are equicontinuous. A proof is given
in the appendices for the sake of completeness.
Lemma 2.2 Let M > 0 and let KM be as in (2.3). Let w : N −→ (0, 1] be an arbitrary weighting
sequence. Then KM is a compact topological space when endowed with the relative topology inherited
from (DZ− , k · kw ).
Definition 2.3 Let K ⊂ DZ− and let HU : (Rn )Z− −→ R be the functional associated to the causal
and time-invariant filter U : (Rn )Z −→ (Rn )Z . We say that U has the fading memory property
(FMP) on K whenever there exists a weighting sequence w : N −→ (0, 1] such that the map HU : K ⊂
(DZ− , k · kw ) −→ R is continuous. This means that for any z ∈ K and any  > 0 there exists a δ() > 0
such that for any s ∈ K that satisfies that
kz − skw = sup k(zt − st )w−t k < δ(),

then

|HU (z) − HU (s)| < .

t∈Z−

If the weighting sequence w is such that wt = λt , for some λ ∈ (0, 1) and all t ∈ N, then U is said to
have the λ-exponential fading memory property.
Remark 2.4 The fading memory property is in some occasions also related to the Lyapunov stability
of the autonomous system associated to the reservoir map. This connection has been made explicit, for
example, for discrete-time nonlinear state-space models that are affine in their inputs, and have direct
feed-through term in the output [Zang 04] or for time-delay reservoirs [Grig 16b].
Remark 2.5 Time-invariant fading memory filters always have the bounded input, bounded output
(BIBO) property. Indeed, if for simplicity we consider functionals HU that map the zero input to zero,
that is HU (0) = 0, and we want bounded outputs such that |HU (z)| < k, for a given constant k > 0,
by Definition 2.3 it suffices to consider inputs z ∈ (RN )Z− such that kzk∞ := supt∈Z− kzt k =< δ(k).
Indeed, if HU has the FMP with respect to a weighting sequence w, then kzkw ≤ kzk∞ < δ(k) and
hence |HU (z)| < k, as required.

Universal reservoir computers using non-homogeneous state-affine systems

6

The following lemma, that will be used later on in the paper, spells out how the FMP depends on
the weighting sequence used to define it.
Lemma 2.6 Let K ⊂ DZ− and let HU : (Rn )Z− −→ R be the functional associated to the causal and
time-invariant filter U : (Rn )Z −→ (Rn )Z . If HU : K ⊂ DZ− −→ R has the FMP with respect to a given
weighting sequence w, then it also has it with respect to any other weighting sequence w0 that satisfies
that
wt
< λ, for a fixed λ > 0 and for all t ∈ N.
wt0
In particular, the thesis of the lemma holds when w0 dominates w, that is when λ = 1.
It can be shown [Grig 18] that when in this lemma the set K is made of uniformly bounded sequences,
that is, K = KM , with KM as in (2.1), then if a filter has the FMP with respect to a given weighting
sequence, it necessarily has the same property with respect to any other weighting sequence.

3

Universality results in the deterministic setup

In this section we consider deterministic filters, in the sense that their inputs belong to a subset of
KM ⊂ (Rn )Z formed by uniformly bounded elements, as in the definition in (2.3).
We will formulate two different universality results. In the first one, we show that polynomial
algebras of filters generated by reservoir computers with the fading memory property that separate
points are able to approximate any fading memory filter. Such families of reservoir computers are said
to be universal. Two important consequences of this result is that the entire family of fading memory
RCs itself is universal, as well as the one containing all the linear reservoirs with polynomial readouts,
when certain spectral restrictions are imposed on the reservoir matrices. In the second result, we restrict
ourselves to reservoir computers with linear readouts and introduce the non-homogeneous state-affine
family in order to be able to obtain a similar universality statement.
The first result can be seen as a discrete-time translation of the one formulated in [Boyd 85] for
continuous-time filters while the second one is an extension to infinite time intervals of the main approximation result in [Flie 80] formulated for compact time intervals using homogeneous state-affine
systems.

3.1

Universality for fading memory RCs with non-linear readouts

The following statement is a direct consequence of the compactness result in Lemma 2.3 and the StoneWeierstrass theorem for polynomial subalgebras of real-valued functions defined on compact metric
spaces, as formulated in Theorem 7.3.1 in [Dieu 69]. See Appendix 6.4 for a detailed proof.
Theorem 3.1 Let KM ⊂ (Rn )Z− be a subset of the type defined in (2.3) and let
R := {HhFii : KM −→ R | hi ∈ C ∞ (RNi ), Fi : RNi × Rn −→ RNi , i ∈ I, Ni ∈ N}

(3.1)

be a set of reservoir filters defined on KM that have the FMP with respect to a given weighted norm
k · kw . Let A(R) be the polynomial algebra generated by R, that is, the set formed by finite products
and linear combinations of elements in R. If the algebra A(R) contains the constant functionals and
separates the points in KM , then any causal, time-invariant fading memory filter H : KM −→ R can
be uniformly approximated by elements in A(R), that is, A(R) is dense in the set (C 0 (KM ), k · kw )
of real-valued continuous functions on (KM , k · kw ). More explicitly, this implies that for any fading
memory filter H and any  > 0, there exist indices {i1 , . . . , ir } ⊂ I and a polynomial p : Rr −→ R such
that
kH − HhF k∞ := sup |H(z) − HhF (z)| < 
z∈KM

with

h := p(hi1 , . . . , hir )

and

F := (Fi1 , . . . , Fir ).

Universal reservoir computers using non-homogeneous state-affine systems

7

An important fact is that the polynomial algebra A(R) generated by a set formed by fading memory
reservoir filters is made of fading memory reservoir filters. Indeed, let hi ∈ C ∞ (RNi ), Fi : RNi × Rn −→
RNi , i ∈ {1, 2}, and λ ∈ R. Then, the product HhF11 · HhF22 and the linear combination HhF11 + λHhF22 filters
are such that
HhF11 · HhF22
HhF11

+

λHhF22

=

HhF ,

=

HhF0 ,

with

h := h1 · h2 ∈ C ∞ (RN1 +N2 ),
0

∞

with h := h1 + λh2 ∈ C (R

N1 +N2

(3.2)
),

(3.3)

and where
F : RN1 +N2 × Rn −→ RN1 +N2

is the map given by F ((x1 , x2 ), z) := (F1 (x1 , z), F2 (x2 , z)) .

(3.4)

We emphasize that the functionals HhF and HhF0 in (3.2) and (3.3) are well defined because if the reservoir
Z
Z
maps F1 and F2 satisfy the echo state property then so does F . Indeed, if x1 ∈ RN1 and x2 ∈ RN2
Z
are the solutions of the reservoir equation (1.1) for F1 and F2 associated to the input z ∈ (Rn ) , then

Z
so is x1 ⊕ x2 ∈ RN1 +N2 for F in (3.4).
This observation has as a consequence that the set of all the RC systems that have the echo state
property and the FMP with respect to a given weighted norm k · kw form a polynomial algebra that contains the constant functions (they can be obtained by using as readouts constant elements in C ∞ (RNi ))
and separate points (take the trivial reservoir map F (x, z) = z and use the separation property of
C ∞ (Rn )). This remark, put together with Theorem 3.1 yields the following corollary.
Corollary 3.2 Let KM ⊂ (Rn )Z− be a subset of the type defined in (2.3) and let
Rw := {HhF : KM −→ R | h ∈ C ∞ (RN ), F : RN × Rn −→ RN , N ∈ N}

(3.5)

be the set of all reservoir filters defined on KM that have the FMP with respect to a given weighted norm
k · kw . Then Rw is universal, that is, it is dense in the set (C 0 (KM ), k · kw ) of real-valued continuous
functions on (KM , k · kw ).
According to the previous corollary, reservoir filters that have the FMP are able to approximate any
time-invariant fading memory filter. We now show that actually a much smaller family of reservoirs
suffices to do that, namely, certain classes of linear reservoirs with polynomial readouts. Consider the
RC system determined by the expressions


xt = Axt−1 + czt ,
yt = h(xt ),

A ∈ MN , c ∈ MN,n ,

h ∈ R[x].

(3.6)
(3.7)

If this system has a reservoir filter associated (the next result provides a sufficient condition for this
to happen) we will denote by HhA,c : K −→ R the associated functional and we will refer to it as the
linear reservoir filter determined by A, c, and the polynomial h. These filters exhibit the following
universality property that is proved in Appendix 6.5.
Corollary 3.3 Let KM ⊂ (Rn )Z− be a subset of the type defined in (2.3) and let  ∈ R be such that
1 >  > 0. Consider the set L formed by all the linear reservoir systems as in (3.6)-(3.7) determined
by polynomial readouts and by matrices A ∈ MN such that σmax (A) < 1 − . Then, the elements in L
generate λρ -exponential fading memory reservoir filters, with λρ := (1 − )ρ , for any ρ ∈ (0, 1), that can
be explicitly written down using the expression:
!
∞
X
A,c
i
Hh (z) = h
A cz−i , for any z ∈ KM .
(3.8)
i=0

This family is dense in (C (KM ), k · kwρ ) with wtρ := λtρ , for any ρ ∈ (0, 1).
0

Universal reservoir computers using non-homogeneous state-affine systems

3.2

8

State-affine systems and universality for fading memory RCs with linear
readouts

As it was explained in the introduction, it is is particularly convenient to work with RCs that have a
linear readout since in that case the training reduces to the solution of a regression problem. That is
in most cases feasible when there is need, as it happens in many applications, for a high number of
neurons. This point makes relevant the identification of families of reservoirs that are universal when
the readout is restricted to be linear, which is the subject of this subsection. In order to simplify the
presentation, we restrict ourselves in this case to one-dimensional input signals, that is, all along this
section we set n = 1. The extension to the general case is straightforward even though more convoluted
to write down (see Remark 3.12).
Definition 3.4 Let N ∈ N, W ∈ RN , and let p(z) ∈ MN,N [z] and q(z) ∈ MN,1 [z] be two polynomials on
the variable z with matrix coefficients, as they were introduced in (2.1). The non-homogeneous stateaffine system (SAS) associated to p, q and W is the reservoir system determined by the state-space
transformation:
(
xt = p(zt )xt−1 + q(zt ),
(3.9)
yt = W > x t .

(3.10)

Notice that the linear reservoir equation (3.6) is a particular case of the SAS state equation (3.9)
that is obtained by taking for p and q polynomials of degree zero.
Our next result spells out a sufficient condition that guarantees that the SAS reservoir system (3.9)(3.10) has the echo state property. Moreover, it provides an explicit expression for the unique causal
and time-invariant solution associated to a given input. Recall that for any A ∈ Mn,m , kAk2 denotes
its matrix norm induced by the Euclidean norms in Rm and Rn and that kAk2 = σmax (A).
Proposition 3.5 Consider a non-homogeneous state-affine system as in (3.9)-(3.10) determined by
polynomials p, q, and a vector W, with inputs defined on I Z , I := [−1, 1]. Assume that
max kp(z)k2 = max σmax (p(z)) < 1.
z∈I

(3.11)

z∈I

Then, the reservoir system (3.9)-(3.10) has the echo state property and for each input z ∈ RZ it has a
unique causal and time-invariant solution given by

!
j−1
∞

Y
X

x =
p(zt−k ) q(zt−j ),
(3.12)
t
j=0 k=0



yt = W> xt .
(3.13)
p,q
p,q
In that situation, we will denote by UW
: I Z −→ I Z and HW
: I Z− −→ R the corresponding SAS
reservoir filter and SAS functional, respectively.

The next result presents two alternative conditions that imply the hypothesis maxz∈I kp(z)k2 < 1
in the previous proposition and that are easier to verify in practice.
Lemma 3.6 Let p(z) ∈ MN,N [z] be the polynomial given by
p(z) := A0 + zA1 + z 2 A2 + · · · + z n1 An1 ,
Consider the following three conditions:

n1 ∈ N.

Universal reservoir computers using non-homogeneous state-affine systems

9

(i) There exists a constant 0 < λ < 1, such that kAi k2 = σmax (Ai ) < λ, for any i ∈ {0, 1, . . . , n1 }, and
that at the same time satisfies that λ(n1 + 1) < 1.
(ii) Bp := kA0 k2 + kA1 k2 + · · · + kAn1 k2 < 1.
(iii) Mp := maxz∈I kp(z)k2 < 1.
Then, condition (i) implies (ii) and condition (ii) implies (iii).
We emphasize that since Proposition 3.5 was proved using condition (iii) in the previous lemma
then, any of the three conditions in that statement imply the echo state property for (3.12)-(3.13) and
the time-invariance of the corresponding solutions. The next result shows that the same situation holds
in relation with the fading memory property.
Proposition 3.7 Consider a non-homogeneous state-affine system as in (3.9)-(3.10) determined by
polynomials p, q, and a vector W, with inputs defined on I Z , I := [−1, 1]. If the polynomial p satisfies
any of the three conditions in Lemma 3.6 then the corresponding reservoir filter has the fading memory
p,q
property. More specifically, if p satisfies condition (i) in Lemma 3.6, then HW
: (I Z− , k · kwρ ) −→ R is
ρ
ρt ρt
continuous with wt := (n1 + 1) λ and ρ ∈ (0, 1) arbitrary. The same conclusion holds for conditions
(ii) and (iii) with wtρ := Bpρt and wtρ := Mpρt , respectively.
The importance of SAS in relation to the universality problem has to do with the fact that they
form a polynomial algebra which allows us, under certain conditions, to use the Stone-Weierstrass
theorem to prove a density statement. Before we show that, we observe that for any two polynomials
p1 (z) ∈ MN1 ,M1 [z] and p2 (z) ∈ MN2 ,M2 [z] given by
p1 (z)
p2 (z)

:= A10 + zA11 + z 2 A12 + · · · + z n1 A1n1 ,
:=

A20

+

zA21

+z

2

A22

+ ··· + z

n2

A2n2 ,

(3.14)
(3.15)

with n1 , n2 ∈ N, their direct sum p1 ⊕p2 (z) ∈ MN1 +N2 ,M1 +M2 [z] and their Kronecker product p1 ⊗p2 (z) ∈
MN1 ·N2 ,M1 ·M2 [z] is written as
p1 ⊕p2 (z) = A10 ⊕A20 +zA11 ⊕A21 +z 2 A12 ⊕A22 +· · ·+z n2 A1n2 ⊕A2n2 +z n2 +1 A1n2 +1 ⊕0+· · ·+z n1 A1n1 ⊕0, (3.16)
where we assumed that n2 ≤ n1 . Analogously,
p1 ⊗ p2 (z) =

n1 X
n2
X

z i+j A1i ⊗ A2j .

(3.17)

i=0 j=0
p1 ,q1
p2 ,q2
Proposition 3.8 Let D ⊂ R be an open set and let HW
, HW
: DZ− −→ R be two SAS reservoir
1
2
functionals associated to two corresponding time-invariant SAS reservoir systems that have V1 and V2 as
state spaces, respectively. Assume that the two polynomials with matrix coefficients p1 (z) ∈ MN1 ,M1 [z]
and p2 (z) ∈ MN2 ,M2 [z] satisfy that kp1 (z)k2 < 1 −  and kp2 (z)k2 < 1 −  for all z ∈ I := [−1, 1] and a
given 1 >  > 0. Then, with the notation introduced in the expressions (3.16) and (3.17), we have that:
p1 ,q1
p2 ,q2
(i) For any λ ∈ R, the linear combination HW
+ λHW
is a SAS reservoir functional associated to
1
2
a SAS that has V1 ⊕ V2 as state space and:
p2 ,q2
p1 ⊕p2 ,q1 ⊕q2
p1 ,q1
HW
+ λHW
= HW
.
2
1
1 ⊕λW2

(3.18)

Universal reservoir computers using non-homogeneous state-affine systems

10

p1 ,q1
p2 ,q2
(ii) The product HW
· HW
is a SAS reservoir functional associated to a SAS that has V1 ⊕ V2 ⊕
1
2
(V1 ⊗ V2 ) as state space and:
p,q ⊕q ⊕(q ⊗q )

p1 ,q1
p2 ,q2
1
2
1
2
HW
· HW
= H0⊕0⊕(W
,
1
2
1 ⊗λW2 )

(3.19)

where p(z) ∈ MN12 [z], N12 := dim V1 + dim V2 + dim V1 · dim V2 , is the polynomial with matrix
coefficients whose block-matrix expression for the three summands in V1 ⊕ V2 ⊕ (V1 ⊗ V2 ) is:


p1
0
0
.
0
p2
0
p := 
(3.20)
p1 ⊗ q2 q1 ⊗ p2 p1 ⊗ p2
The expression p1 ⊗ q2 (respectively, q1 ⊗ p2 ) denotes the linear map from V1 (respectively, V2 ) to
V1 ⊗V2 that associates to any v1 ∈ V1 the element (p1 (z)v1 )⊗q2 (z) (respectively, q1 (z)⊗(p2 (z)v2 )).
The equalities (3.18) and (3.19) show that the SAS family forms a polynomial algebra.
Theorem 3.9 (Universality of SAS reservoir computers) Let I Z− ⊂ RZ− be the subset of real
uniformly bounded sequences in I := [−1, 1] as in (2.3), that is,
I Z− := {z ∈ RZ− | zt ∈ [−1, 1], for all

t ≤ 0},

p,q
and let S be the family of functionals HW
: I Z− −→ R induced by the state-affine systems defined
in (3.9)-(3.10) that satisfy that Mp := maxz∈I kp(z)k2 < 1 −  and Mq := maxz∈I kq(z)k2 < 1 − . The
family S forms a polynomial subalgebra of Rwρ (as defined in (3.5)) with wtρ := (1 − )ρt and ρ ∈ (0, 1)
arbitrary, made of fading memory reservoir filters that contains the constant functions and separate
points. The subfamily S is hence dense in the set (C 0 (I Z− ), k · kwρ ) of real-valued continuous functions
on (I Z− , k · kwρ ) which implies that any causal, time-invariant fading memory filter H : I Z− −→ R
can be uniformly approximated by elements in S . More specifically, for any fading memory filter H
and any  > 0, there exist a natural number N ∈ N, polynomials p(z) ∈ MN,N [z], q(z) ∈ MN,1 [z] with
Mp , Mq < 1 − , and a vector W ∈ RN such that
p,q
p,q
kH − HW
k∞ := sup |H(z) − HW
(z)| < .
z∈I Z−

Remark 3.10 As it is stated in Theorem 3.9, it is the condition (iii) in Lemma 3.6 that yields a
universal family of SAS fading memory reservoirs. As it can deduced from its proof (available in
the Appendix 6.10), the families determined by conditions (i) or (ii) in that lemma contain SAS
fading memory reservoirs but they do not form a polynomial algebra. In such cases, and according to
Theorem 3.1, it is the algebras generated by them and not the families themselves that are universal.
Remark 3.11 A continuous-time analog of the universality result that we just proved can be obtained
using the bilinear systems considered in Section 5.3 of [Boyd 85]. In discrete time, but only when the
number of time steps is finite, this universal approximation property is exhibited [Flie 80] by homogeneous state-affine systems, that is, by setting q(z) = 0 in (3.9)-(3.10).
Remark 3.12 Generalization to multidimensional signals. When the input signal is defined in
InZ , with In := [−1, 1]n , a SAS family with the same universality properties can be defined by replacing
the polynomials p and q in Definition 3.4, by polynomials of the form:
X
iN
p(z) =
z1i1 · · · zN
Ai1 ,...,iN ,
Ai1 ,...,iN ∈ MN,N ,
i1 ,...,iN ∈{0,...,r}
i1 +···+iN ≤r

q(z)

=

X
i1 ,...,iN ∈{0,...,s}
i1 +···+iN ≤s

iN
z1i1 · · · zN
Bi1 ,...,iN ,

Ai1 ,...,iN ∈ MN,1 .

Universal reservoir computers using non-homogeneous state-affine systems

11

Remark 3.13 SAS with trigonometric polynomials. An analogous construction can be carried
out using trigonometric polynomials of the type:
X
p(z) =
cos (i1 · z1 + · · · + iN · zN ) Ai1 ,...,iN ,
Ai1 ,...,iN ∈ MN,N ,
i1 ,...,iN ∈{0,...,r}
i1 +···+iN ≤r

q(z)

X

=

cos (i1 · z1 + · · · + iN · zN ) Bi1 ,...,iN ,

Ai1 ,...,iN ∈ MN,1 .

i1 ,...,iN ∈{0,...,s}
i1 +···+iN ≤s

In this case, it is easy to establish that the resulting SAS family forms a polynomial algebra by invoking
Proposition 3.8 and by reformulating the expressions (3.16) and (3.17) using the trigonometric identity
cos(θ) cos(φ) =

1
(cos(θ − φ) + cos(θ + φ)) .
2

Additionally, the corresponding SAS family includes the linear family and hence the point separation
property can be established as in the proof of Theorem 3.9 in the Appendix 6.10.

4

Reservoir universality results in the stochastic setup

This section extends the previously stated deterministic universality results to a setup in which the
reservoir inputs and outputs are stochastic, that is, the reservoir is not driven anymore by infinite
sequences but by discrete-time stochastic processes. We emphasize that we restrict our discussion to
reservoirs that are deterministic and hence the only source of randomness in the systems considered is
the stochastic nature of the input.
The stochastic setup. All along this section we work on a probability space (Ω, A, P). If a condition
defined on this probability space holds everywhere except for a set with zero measure, we will see that
the relation is true almost surely and we will abbreviate it a.s. We will denote by L∞ (Ω, Rn ) the
set of Rn -valued random variables whose Euclidean norms have a finite essential supremum or that,
equivalently, have almost surely bounded Euclidean norms. More specifically, let X : Ω −→ Rn be a
random variable and let
kXkL∞ := ess sup kX(ω)k = inf {ρ ∈ R+ | kXk < ρ almost surely} .

(4.1)

L∞ (Ω, Rn ) := {X : Ω −→ Rn random variable | kXkL∞ < ∞} .

(4.2)

ω∈Ω

We define
∞

n

It can be shown that L (Ω, R ) is a Banach space (see [Ledo 91, pages 42 and 46], [Lord 14, page 149].
Given an element X ∈ L∞ (Ω, Rn ), we denote by E [X] its expectation. The following lemma collects
some elementary results that will be needed later on and shows, in particular, that the expectation E [X]
k
as well as that of all the powers kXk of its norm are finite for all the elements X ∈ L∞ (Ω, Rn ).
Lemma 4.1 Let X ∈ L∞ (Ω, Rn ) and let C > 0 be a real number. Then:
(i) kXk ≤ kXkL∞ almost surely.
(ii) kXkL∞ ≤ C if and only if kXk ≤ C almost surely.


(iii) kXk ≤ C almost surely if and only if E kXkk ≤ C k for any k ∈ N.
(iv) The components Xi of X, i ∈ {1, . . . , n}, are such that E [Xi ] ≤ kXkL∞ .

Universal reservoir computers using non-homogeneous state-affine systems

12

The first point in this lemma explains why we will refer to the elements of L∞ (Ω, Rn ) as almost surely
bounded random variables.
Inputs and outputs. The filters that we will consider in this section have almost surely bounded
time series or discrete-time stochastic processes as inputs and outputs. Recall that a discrete-time
stochastic process is a map of the type:
z: Z×Ω
(t, ω)

−→
7−→

Rn
zt (ω),

(4.3)

such that, for each t ∈ Z, the assignment zt : Ω −→ Rn is a random variable. For each ω ∈ Ω, we
will denote by z(ω) := {zt (ω) ∈ Rn | t ∈ Z} the realization or the sample path of the process z.
Additionally, we use the symbol F(z) := {Ft (zt ) | t ∈ Z}, with Ft (zt ) := σ ({zs | s ≤ t}) the sigma
algebra generated by the process z up to time t, to refer to the filtration generated by z. The results
that follow are presented for stochastic processes indexed by Z but are equally valid for Z+ and Z− .
Recall that a map of the type (4.3) is a Rn -valued stochastic process if and only if the corresponding
Z
map z : Ω −→ (Rn ) into path space (designated with the same symbol) is a random variable when in
Z
(Rn ) we consider the product sigma algebra generated by cylinder sets [Come 06, Chapter 1]. Then,
Z
using the same prescription as in (4.1) with the supremum norm k · k∞ in (Rn ) , we can define a norm
n
k · kL∞ in the space of R -valued stochastic processes by setting


(4.4)
kzkL∞ := ess sup kz(ω)k∞ = ess sup sup {kzt (ω)k} .
ω∈Ω

ω∈Ω

t∈Z

The following lemma provides an alternative characterization of the norm k·kL∞ that will be very useful
in the proofs of the results that follow and in which the supremum and the essential supremum have
been intertwined. The last statement contained in it complements part (ii) of Lemma 4.1 for processes.
Lemma 4.2 Let z : Ω −→ (Rn ) be a stochastic process. Then,




kzkL∞ := ess sup sup {kzt (ω)k} = sup ess sup {kzt (ω)k} .
Z

ω∈Ω

t∈Z

t∈Z

(4.5)

ω∈Ω

Equivalently, using the notation in Lemma 4.1,
= sup kzt (ω)kL∞ .

kzkL∞ := sup kzt (ω)k
t∈Z

L∞

(4.6)

t∈Z

These equalities imply that for any positive real number C > 0, the process z satisfies that kzkL∞ ≤ C
if and only if kzt kL∞ ≤ C for all t ∈ Z or, equivalently, if and only if supt∈Z kzt kL∞ ≤ C.

We now consider the space L∞ Ω, (Rn )Z of processes with finite k·kL∞ norm, that is,

L∞ Ω, (Rn )Z := {z : Z × Ω −→ Rn stochastic process | kzkL∞ < ∞} .

We refer to the elements of L∞ Ω, (Rn )Z as almost surely bounded time series. The following
result shows that L∞ Ω, (Rn )Z coincides with the space of processes that take values in the Banach
space (`∞ (Rn ), k · k∞ ) and it is hence a Banach space.
Lemma 4.3 In the setup that we just introduced

L∞ Ω, (Rn )Z = L∞ (Ω, `∞ (Rn ))


and L∞ Ω, (Rn )Z , k · kL∞ is a Banach space.

(4.7)

Universal reservoir computers using non-homogeneous state-affine systems

13

Let now w be a weighting sequence and let k · kw be the associated weighted norm in (Rn ) − . If we
replace in (4.4) the `∞ norm k · k∞ by the weighted norm k · kw , we obtain a weighted norm k · kL∞
in
w
the space of processes z : Z− × Ω −→ Rn indexed by Z− as:


kzkL∞
:=
ess
sup
kz(ω)k
=
ess
sup
sup
{kz
(ω)kw
}
.
(4.8)
t
−t
w
w
Z

ω∈Ω

ω∈Ω

t∈Z

n Z−
We will denote by L∞
the space of processes with finite k·kL∞
norm. Since the space
w Ω, (R )
w
∞
n
`w (R ) introduced
in (2.2) is a Banach space [Grig 18] and a result similar
to Lemma 4.3 shows that


n Z−
n
∞
n Z−
L∞
= L∞ (Ω, `∞
(R
)
is
a
Banach space. Additionw Ω, (R )
w (R )), we can conclude that Lw Ω,

n Z−
:
Ω,
(R
)
ally, as in Lemma 4.2, we have that for any z ∈ L∞
w




(4.9)
kzkL∞ := ess sup sup {kzt (ω)kw−t } = sup ess sup {kzt (ω)kw−t } .



w

ω∈Ω

t∈Z

t∈Z

ω∈Ω

Deterministic filters in a stochastic setup. As we already pointed out, we consider filters U that
have almost surely bounded time series inputs and outputs, that is, if the inputs can take values in
Rn then U : L∞ (Ω, (Rn )Z ) −→ L∞ (Ω, RZ ). The same conventions as in the deterministic setup will be
used in the identification of the different signals, namely, z will denote the filter inputs, the symbol y is
reserved for the output, and d for the teaching signals. We emphasize that unlike in the deterministic
case, the components of all these signals are this time random variables and not points in a Euclidean
space.
The concepts of causality and time-invariance are defined as in the deterministic case by replacing equalities by almost sure equalities in the corresponding identities. The same applies to the correspondence between time-invariant filters U : L∞ (Ω, (Rn )Z ) −→ L∞ (Ω, RZ ) and functionals HU :
L∞ (Ω, (Rn )Z− ) −→ L∞ (Ω, R). We draw attention to the fact that assuming that the filters map into
almost surely bounded processes is a genuine hypothesis that will need to be verified in each specific
case considered.
We underline again that we will restrict our attention to intrinsically deterministic filters that are
obtained by presenting almost surely bounded stochastic inputs z ∈ L∞ (Ω, (Rn )Z− ) to causal and timeinvariant filters H : (Rn )Z− −→ R similar to those introduced in the previous section which, in some
cases, yields maps of the type H : L∞ (Ω, (Rn )Z− ) −→ L∞ (Ω, R) and that we will denote with the same
symbol. In that situation, the dependence on the probability space of the image (H(z))(ω) takes place
exclusively through the dependence z(ω) in the input. Causal and time-invariant deterministic filters
with stochastic inputs produce almost surely causal and time-invariant filters. Moreover, for any t ∈ Z,
the random variable UH (z)t := H(PZ− ◦ Ut (z)) = H (zt , zt−1 , zt−2 , . . .) is clearly Ft (zt )-measurable.
Given a weighting sequence w : N −→ (0, 1] and a time invariant filter U : L∞ (Ω, (Rn )Z ) −→
∞
L (Ω, RZ ) with stochastic inputs, we will say that U has the fading memory property with respect
to the weighting sequence w when the corresponding functional HU : (L∞ (Ω, (Rn )Z− ), k · kL∞
) −→
w
L∞ (Ω, R) is a continuous map.
Let M > 0 and define, using Lemma 4.2,


L∞
KM
:= z ∈ L∞ (Ω, (Rn )Z− ) | kzkL∞ ≤ M = z ∈ L∞ (Ω, (Rn )Z− ) | kzt kL∞ ≤ M, for all t ∈ Z− .
(4.10)
L∞
The sets KM
are the stochastic counterparts of the sets KM in the deterministic setup; we will say
L∞
that KM
is a set of almost surely uniformly bounded processes. A stochastic analog of Lemma
L∞
2.1 can be formulated for them with KM replaced by KM
, the norm k·k by k·kL∞ , and the weighted
norm k·kw by k·kL∞ .
The following result shows that the fading memory and the universality properties are naturally
inherited by deterministic filters with almost surely bounded inputs.

Universal reservoir computers using non-homogeneous state-affine systems

14

∞

L
Theorem 4.4 Let M > 0 and let KM and KM
be the sets of deterministic and stochastic inputs
defined in (2.3) and (4.10), respectively. The following properties hold true:

(i) Let H : (KM , k·kw ) −→ R be a causal and time-invariant filter. Then H : (KM , k·kw ) −→ R has
the fading memory property if and only if the corresponding filter with almost surely uniformly
L∞
bounded inputs has almost surely bounded outputs, that is, H : (KM
, k · k L∞
) −→ L∞ (Ω, R), and
w
it has the fading memory property.
(ii) Let T := {Hi : (KM , k·kw ) −→ R | i ∈ I} be a family of causal and time-invariant fading memory
filters. Then, T is dense in the set (C 0 (KM ), k · kw ) if and only if the corresponding family with
L∞
L∞
intputs in KM
is universal in the set of continuous maps of the type H : (KM
, k · kL∞
) −→
w
L∞ (Ω, R).
A first universality result using RC systems. The following result is a stochastic analog of
Theorem 3.1 and shows that any fading memory filter with almost surely uniformly bounded inputs
can be approximated using the elements of a polynomial algebra of reservoir filters with the same kind
of inputs, provided that it contains the constant functionals and has the separation property. We note
that, as in the deterministic case, the existence of the reservoir filter associated to a reservoir system
like (1.1)-(1.2) is guaranteed only in the presence of the echo state property. It is easy to verify that
if a reservoir system with uniformly bounded deterministic inputs satisfies the echo state property and
the FMP then so does its counterpart with almost surely uniformly bounded inputs.
∞

L
Theorem 4.5 Let M > 0 and let KM
duced in (4.10). Consider the set R

be the set of almost surely uniformly bounded processes intro-

∞

L
R := {HhFii : KM
−→ L∞ (Ω, R) | hi ∈ Pol(RNi , R), Fi : RNi × Rn −→ RNi , i ∈ I, Ni ∈ N}

(4.11)

formed by deterministic fading memory reservoir filters with respect to a given weighted norm k · kw
L∞
. Let A(R) be the polynomial algebra generated by R. If the
and driven by stochastic inputs in KM
algebra A(R) has the separation property and contains contains all the constant functionals, then any
L∞
deterministic, causal, time-invariant fading memory filter H : (KM
, k · k L∞
) −→ L∞ (Ω, R) can be
w
uniformly approximated by elements in A(R), that is, for any  > 0, there exist indices {i1 , . . . , ir } ⊂ I
and a polynomial p : Rr −→ R such that
kH − HhF k∞ := sup kH(z) − HhF (z)kL∞ < 

with

∞

h := p(hi1 , . . . , hir )

and

F := (Fi1 , . . . , Fir ).

L
z∈KM

In the next paragraphs we identify, as in the deterministic case, families of reservoirs that satisfy
the hypotheses of this theorem and where we will eventually impose linearity constraints on the readout
function. The following corollary to Theorem 4.5 is the stochastic analog of Corollary 3.2.
∞

L
Corollary 4.6 Let M > 0 and let KM
duced in (4.10). Let

be the set of almost surely uniformly bounded processes intro-

∞

L
Rw := {HhF : KM
−→ L∞ (Ω, R) | h ∈ Pol(RN , R), F : RN × Rn −→ RN , N ∈ N}
∞

(4.12)

L
be the set of all the reservoir filters defined on KM
that have the FMP with respect to a given weighted
L∞
norm k · kL∞
.
Then
R
is
universal,
that
is,
for
any
time-invariant fading memory filter H : (KM
,k·
w
w
∞
F
F
kL∞
)
−→
L
(Ω,
R)
and
any

>
0,
there
exists
a
reservoir
filter
H
∈
R
such
that
kH
−
H
k
w
h
h ∞ :=
w
F
supz∈KM
L∞ kH(z) − H (z)kL∞ < .
h

Universal reservoir computers using non-homogeneous state-affine systems

15

Linear reservoir computers with stochastic inputs are universal. As it was the case in the
deterministic setup, we can prove in the stochastic case that the linear RC family introduced in (3.6)(3.7) suffices to achieve universality. The proof of the following statement is a direct consequence of
Corollary 3.3 and Theorem 4.4.
∞

L
Corollary 4.7 Let M > 0 and let KM
be the set of almost surely uniformly bounded processes introduced in (4.10). Let L be the family introduced in Corollary 3.3 and formed by all the linear reservoir
filters HpA,c determined by matrices A ∈ MN such that σmax (A) < 1 − . The elements in L map
L∞
KM
into L∞ (Ω, R) and are time-invariant fading memory filters with respect to the weighted norm
L∞
k · kwρ associated to wtρ := (1 − )ρt , for any ρ ∈ (0, 1). Moreover, they are universal, that is, for any
L∞
time-invariant and causal fading memory filter H : (KM
, k · k L∞
) −→ L∞ (Ω, R) and any ε > 0, there
wρ
A,c
A,c
A,c
exists Hp ∈ L such that kH − Hp k∞ := supz∈KM
(z)kL∞ < ε.
L∞ kH(z) − Hp

Remark 4.8 The previous corollary has interesting consequences in the realm of time series analysis.
Indeed, many well-known parametric time series models consist in autoregressive relations, possibly
nonlinear, driven by independent or uncorrelated innovations. The parameter constraints that are
imposed on them in order to ensure that they have (second order) stationary solutions imply, in may
situations, that the resulting filter has the FMP. In those cases, Corollary 4.7 allows us to conclude that
when those models are driven by almost surely uniformly bounded innovations, they can be arbitrarily
well approximated by a polynomial function of a strong vector autoregressive model (VAR) of order 1.
This statement applies, for example, to any stationary ARMA [Box 76, Broc 06] or GARCH [Engl 82,
Boll 86, Fran 10] model driven by almost surely uniformly bounded innovations.
State-affine reservoir computers with almost surely uniformly bounded inputs are universal. As it was the case in the deterministic setup, non-homogeneous SAS are universal time-invariant
fading memory filters in the stochastic framework with almost surely uniformly bounded inputs. Their
advantage with respect to the families proposed in the previous corollary is that they use a linear readout which is of major importance in practical implementations. More specifically, the following result
holds true as a direct consequence of Theorem 3.9 and the equivalence stated in Theorem 4.4.
Theorem 4.9 (Universality of SAS reservoir computers with almost surely uniformly bounded
∞
inputs) Let KIL ⊂ L∞ (Ω, RZ− ) be the set of almost surely and uniformly bounded processes in the
interval I = [−1, 1], that is,

∞
KIL := z ∈ L∞ (Ω, RZ− ) | kzt kL∞ ≤ 1, for all t ∈ Z− .
∞

p,q
Let S be the family of functionals HW
: KIL −→ L∞ (Ω, R) induced by the state-affine systems defined
in (3.9)-(3.10) and that satisfy Mp := maxz∈I kp(z)k < 1 −  and Mq := maxz∈I kq(z)k < 1 − ,
with I := [−1, 1]. The family S forms a polynomial subalgebra of Rwρ (as defined in (4.12)) with
wtρ := (1 − )ρt , made of fading memory reservoir filters that map into L∞ (Ω, R).
∞
Moreover, for any time-invariant and causal fading memory filter H : (KIL , k · kL∞
) −→ L∞ (Ω, R)
wρ
and any  > 0, there exist a natural number N ∈ N, polynomials p(z) ∈ MN,N [z], q(z) ∈ MN,1 [z] with
Mp , Mq < 1 − , and a vector W ∈ RN such that
p,q
p,q
kH − HW
k∞ := sup kH(z) − HW
(z)kL∞ < .
∞

z∈KIL

Universal reservoir computers using non-homogeneous state-affine systems

5

16

Echo state affine systems (ESAS) and their forecasting performance

Echo state networks (ESNs) were introduced in [Jaeg 04] as one of the first families of reservoir computing architectures and have been very successful in many information processing tasks. An ESN is
determined by the following state-space transformation:
(
xt = σ (α + Axt−1 + γczt )) ,
>

yt = W xt .

(5.1)
(5.2)

In these equations z ∈ KM ⊂ (Rn ) is the input signal, c ∈ MN,n is called the input mask, α ∈ RN is
the input shift, and γ ∈ R is the input gain. The matrix A ∈ MN,N is referred to as the reservoir
matrix. The map σ in the state-space equation (5.1) is constructed by componentwise application of
a sigmoid function (like the hyperbolic tangent or the logistic function) and is called the activation
function. It can be shown (see [Jaeg 10]) that (5.1)-(5.2) induces a causal, time-invariant, and fading
memory filter whenever kAk2 = σmax (A) < 1. Moreover, the fading memory property does not hold
whenever the spectral radius ρ(A) of A exceeds one.
ESNs are implemented in practice by generating a large random reservoir matrix A and an input
mask c and by tuning the input shift, input gain, and the spectral radius of A so that the performance
in the execution of a specific task is maximized. Given specific input z ∈ KM and teaching signals
d ∈ RZ , the readout vector W is obtained by solving the ridge regularized regression problem:
!
t
1 X f>
2
2
(W xi − di ) + λkWk ,
W = arg min lim
t→∞ 2t
N
f
W∈R
i=−t
Z

where λ > 0 is the regularization constant.
The interesting universality properties associated to the non-homogeneous state-affine systems that
we proved in Section 3.2 suggest a generalization of the ESNs that we denominate echo state affine
systems (ESAS) and that are determined by the state-space equations:
(
xt = σ (p(zt )xt−1 + q(zt )) ,
>

yt = W x t .

(5.3)
(5.4)

An ESAS is hence a SAS in which an activation function has been added following the pattern of the
ESN case. ESAS are a strict generalization of ESNs: an ESAS for which the degree of the p polynomial
is zero and the degree of the q polynomial is one, is an ESN.
A forecasting exercise. A task in which ESNs have been particularly successful is the forecasting of
chaotic time series generated by the the Mackey-Glass system [Mack 77] characterized by the time-delay
differential equation:
dx
0.2 x(t − τ )
=
.
(5.5)
dt
1 + x(t − τ )10 − 0.1 x(t)
In our forecasting exercise we use for the delay τ the customary value in the forecasting literature of
τ = 17. The Lyapunov exponent of this system has been numerically estimated in [Jaeg 04], where
values around 6 · 10−3 were obtained, which shows that this system does indeed generate chaotic time
series.
Forecasting of those time series has been conducted using ESNs as in [Jaeg 04] by using a sparse (1%
connectivity) reservoir matrix A with dimension N = 1000 and with entries randomly drawn from a

Universal reservoir computers using non-homogeneous state-affine systems

17

uniform distribution in the interval [−1, 1]. The training is carried out by using as input z the sampling
with step size 1.0 of a solution of (5.5) with length 5000 and obtained from a differential equation solver
that produced an absolute accuracy of 1 · 10−16 . The teaching signal is set to d = U−1 z, that is, the
input signal shifted in time one step into the future. Forecasting is then carried out with the trained
system running autonomously by feeding the output into the input. The trained ESN is used in that
case as a proxy for the original system (5.5) that has been hence learned by (5.1)-(5.2). Using this
approach, the results reported in [Jaeg 04] improved by a factor of 700 the performances previously
documented in the literature.
We have checked if various ESAS architectures are able to improve the ESN performance in this
task. In order to do so and to make the two systems comparable, we have used ESAS of the same
dimension (N = 1000), the reservoir matrices in the p polyomial and the ESN reservoir matrix A are
sparse and have the same connectivity (1%) and, more importantly, the same hyperparameters have been
optimized. More specifically, in the ESN case we optimized the input shift and gain and we also tuned
the spectral radius of A. The same procedure was carried out in the ESAS case where, additionally, we
tuned the spectral radii of each of the reservoir matrices in the p polyomial.
The results of these forecasting exercises are depicted in Figure 1 where we plot the normalized
root mean square error (NRMSE) committed by the ESN and by several ESAS(r,s) arquitectures (r
and s stand for the degrees of the p and q polynomials, respectively) as a function of the forecasting
horizon. The NRMSE has been averaged over 2000 points. This figure shows that the chosen ESAS
architectures systematically outperform the ESN. A particularly significant improvement is exhibited
by the ESAS(1,2) that, at a forecasting horizon of 121, reduces the NRMSE of 39.18%.

6

Appendices

6.1

Proof of Lemma 2.1

Let w : N −→ (0, 1] be an arbitrary weighting sequence. Then for any z ∈ KM :
kzkw := sup kzt w−t k = sup kzt kw−t ≤ M · 1 = M < ∞.
t∈Z−

t∈Z−

Regarding the inequalities (2.4) and (2.5), notice that if wt = λt then:
∞
X
t=0

kz−t kwt =

∞
X

kz−t kλt =

t=0

∞
X
t=0

≤

∞
X

kz−t k(λ1−ρ λρ )t =

∞
X

kz−t kλ(1−ρ)t λρt

t=0

∞
n
o
n
oX
sup kz−i kλ(1−ρ)i λρt = sup kz−i kλ(1−ρ)i
λρt = kzkw1−ρ

t=0 i∈N

i∈N

t=0

1
,
1 − λρ

which proves (2.4). The proof of (2.5) is similar and follows from noticing that:
∞
X
t=0

6.2

kz−t kλ(1−ρ)t λρt ≤

∞
X

∞
X


sup kz−i kλρi λ(1−ρ)t) = sup kz−i kλρi
λ(1−ρ)t = kzkwρ

t=0 i∈N

i∈N

t=0

1
. 
1 − λ1−ρ

Proof of Lemma 2.2

We recall first that by Lemma 2.1 we have that kzkw < ∞, for any z ∈ KM . Second, since (DZ− , k·kw )
is a normed space it is hence metrizable and therefore so is (KM , k·kw ) when endowed with the relative
topology (see, for instance, [Munk 14, Exercise 1, page 131]). We will then conclude the compactness

Universal reservoir computers using non-homogeneous state-affine systems

18

Figure 1: Results of the Mackey-Glass chaotic time series forecasting exercise. The different panels depict the normalized
root mean square error (NRMSE) committed by the ESN and by several ESAS(r,s) arquitectures (r and s stand
for the degrees of the p and q polynomials, respectively) as a function of the forecasting horizon. The NRMSE
has been averaged over 2000 points. The chosen ESAS architectures systematically outperform the ESN. A
particularly significant improvement is exhibited by the ESAS(1,2) that at a forecasting horizon of 121 reduces
the NRMSE of 39.18%.

Universal reservoir computers using non-homogeneous state-affine systems

19

of (KM , k·kw ) by showing that this space is sequentially compact (see, for example [Munk 14, Theorem
28.2]). We proceed by using the strategy in the proof of Lemma 1 in [Boyd 85].
n
For any n ∈ N, let KM
be the set obtained by projecting into D{−n,...,−1,0} the elements of KM ⊂
Z−
n
D . Given an element z ∈ KM , we will denote by z(n) := (z−n , . . . , z0 ) its projection into KM
.
n
n
Additionally, notice that KM = [−M, M ] is a compact (and hence sequentially compact) topological
space with the product topology.
Let {z(n)}n∈N ⊂ KM be a sequence of elements in KM . The argument that we just stated proves
k
that for any k ∈ N, there is a subset Nk ⊂ N and an element z(k) ∈ KM
such that
(k)

zt (n) − zt

max
t∈{−k,...,0}

−→ 0,

as n → ∞, n ∈ Nk .

Moreover, the sets Nk can be constructed so that N ⊃ N1 ⊃ N2 ⊃ · · · and so that z(k) extends z(l) when
k ≥ l. This implies the existence of an element z ∈ KM such that, for each k ∈ N,
max
t∈{−k,...,0}

kzt (n) − zt k −→ 0,

as n → ∞, n ∈ Nk ,

and hence there exists and increasing subsequence nk such that nk ∈ Nk and that for each k0 ,
max
t∈{−k0 ,...,0}

kzt (nk ) − zt k −→ 0,

as k −→ ∞.

(6.1)

We conclude by showing that the sequence {z(nk )}k∈N converges in (KM , k·kw ) to the element z ∈ KM .
First, given that wt −→ 0 as t −→ ∞, then for any ε > 0 there exists k0 such that wk < ε/2M , for any
k ≥ k0 . Additionally, since z(nk ), z ∈ KM for any k ∈ N, we have that
sup kzt (nk ) − zt k w−t ≤ 2M wk0 < ε.

(6.2)

t≤−k0

Now, by (6.1) there exists k1 such that for any k ≥ k1
kzt (nk ) − zt k w−t <

sup
t∈{−k0 ,...,0}

sup

kzt (nk ) − zt k < ε.

Consequently, (6.2) and (6.3) imply that for any k > max{k0 , k1 }, kz(nk ) − zkw < ε, as required.

6.3

(6.3)

t∈{−k0 ,...,0}



Proof of Lemma 2.6

Let δ w () be the epsilon-delta relation for the FMP associated to the weighting sequence w. We now
0
show that HU has the FMP with respect to w0 via the epsilon-delta relation given by δ w () := δ w ()/λ.
0
Indeed, for any  > 0 and any z, s ∈ K such that kz − skw0 < δ w (), we have that
kz−skw = sup kzt −st kw−t = sup kzt −st k
t∈Z−

t∈Z−

0
w−t 0
0
w−t < λ sup kzt −st kw−t
< λkz−skw0 < λδ w () = δ w (),
0
w−t
t∈Z−

and consequently, since HU has the FMP with respect to the weighting sequence w, we can conclude
that |HU (z) − HU (s)| < . This shows that the implication
0

kz − skw0 < δ w () =⇒ |HU (z) − HU (s)| < 
holds, as required.



Universal reservoir computers using non-homogeneous state-affine systems

6.4

20

Proof of Theorem 3.1

Since the elements in R have the FMP with respect to a given weighted norm k · kw , then so do those
in A(R) since polynomial combinations of continuous elements of the form HhFii : (KM , k · kw ) −→ R
are also continuous. Therefore, under that hypothesis, A(R) is a polynomial subalgebra of the algebra
(C 0 (KM ), k · kw ) of real-valued continuous functions on (KM , k · kw ). Since by hypothesis A(R) contains
the constant functionals and separates the points in KM and, by Lemma 2.2, the set (KM , k · kw ) is
compact, the Stone-Weierstrass theorem (Theorem 7.3.1 in [Dieu 69]) implies that A(R) is dense in
(C 0 (KM ), k · kw ), which concludes the proof. 

6.5

Proof of Corollary 3.3

In order to show that the reservoir systems in L induce reservoir filters, we will show that they have
the echo state property by using the following lemma, whose proof can be found in [Grig 18].
Lemma 6.1 Let DN ⊂ RN and Dn ⊂ Rn and let F : DN × Dn −→ DN be a continuous reservoir map.
Suppose that F is a contraction map with contraction constant 0 < r < 1, that is:
kF (x, z) − F (y, z)k ≤ r kx − yk ,

for all x, y ∈ RN and all z ∈ Rn ,

then the corresponding reservoir system has the echo state property.
We start now by noting that the condition σmax (A) < 1 −  < 1 implies that the reservoir map
F (x, z) := Ax+cz associated to (3.6) is a contracting map with constant σmax (A) which, by hypothesis,
is smaller than one. Indeed,
kF (x, z) − F (y, z)k = kA(x − y)k ≤ σmax (A) kx − yk

for all x, y ∈ RN and all z ∈ Rn .

By Lemma 6.1 we can conclude that this reservoir system has a reservoir filter associated that we now
show is explicitly given by (3.8). We start by proving that the conditions σmax (A) < 1 −  < 1 and that
the elements in KM are uniformly bounded
Pn by a constant M imply that the infinite sum in (3.8) is
convergent. Let n, m ∈ N and let Sn := i=0 Ai cz−i . Now:

kSn − Sm k =

m
X
j=n+1

Ai cz−i ≤

m
X

i

kAk2 kck2 kz−i k ≤ M kck2

m
X

σmax (A)i ≤

j=n+1

j=n+1

M kck2

∞
X

σmax (A)i = M kck2

j=n+1
n+1

σmax (A)n+1
.
1 − σmax (A)

n+1

(c)σmax (A)
max (A)
The condition σmax (A) < 1− < 1 implies that M kck2 σ1−σ
= M σmax1−σ
→ 0 as n → ∞
max (A)
max (A)
N
and hence {Sn }n∈N is a Cauchy sequence in R that consequently converges.
The fact that the filter determined by the expression (3.8) is a solution of the recursions (3.6)(3.7) is a straightforward verification. In order to carry it out, it suffices to use that the filter UhA,c (z)
associated to the functional HhA,c (z) is given by
!
∞


X
A,c
i
Uh (z) = h
A czt−i ,
t

and that the time series xet defined by xet :=

i=0

P∞

i=0

Ai czt−i satisfies the recursion relation (3.6).

Universal reservoir computers using non-homogeneous state-affine systems

21

We now verify by hand that the filters UhA,c (z) are time-invariant. Let z ∈ KM and t, τ ∈ N arbitrary
and let Uτ be the corresponding time delay operator, then:
!
!
∞
∞

 


X
X
UhA,c ◦ Uτ (z) = UhA,c (Uτ (z)) = h
Ai cUτ (z)t−i = h
Ai czt−i−τ
(6.4)
t

t

i=0

i=0

At the same time,


Uτ ◦

UhA,c




 



(z) = Uτ UhA,c (z)
= UhA,c (z)
t

t

t−τ

= KM h

∞
X

!
i

A czt−τ −i

,

i=0

which coincides with (6.4) and proves the time-invariance of UhA,c .
The next step consists in showing that the elements in L are λρ -exponential fading memory filters,
with λρ := (1 − )ρ , for any ρ ∈ (0, 1), that is, L ⊂ Rwρ , with wρ : N → (0, 1] the sequence given by
wtρ := (1 − )ρt . Let k · kwρ be the associated weighted norm in KM and let z ∈ KM be an arbitrary
element. We start by noting that the continuity of the readout map h : RN → R implies that for any
ε > 0 there exists an element δ(ε) > 0 such that for any v ∈ RN that satisfies
!
∞
∞
X
X
i
i
(6.5)
A czt−i < ε.
A czt−i < δ(ε), then h(v) − h
v−
i=0

i=0

We now show that for any s ∈ KM such that
ks − zkwρ


δ(ε) 1 − (1 − )1−ρ
<
,
σmax (c)

then

HhA,c (s) − HhA,c (z) < ε.

(6.6)

Indeed,
∞
X

Ai cst−i −

i=0

∞
X
i=0

∞
X
i=0

Ai czt−i =

∞
X

Ai c(st−i − zt−i ) ≤

i=0

σmax (Ai ) kc(st−i − zt−i )k ≤

∞
X

Ai c(st−i − zt−i ) ≤

i=0
∞
X
i=0

σmax (A)i kc(st−i − zt−i )k ≤

∞
X
(1 − )i kc(st−i − zt−i )k .
i=0

If we now use (2.5) in Lemma 2.1 and the hypothesis in (6.6), we can conclude that
∞
X
i=0

(1 − )i kc(st−i − zt−i )k ≤ σmax (c)

∞
X
σmax (c)ks − zkwρ
(1 − )i k(st−i − zt−i )k ≤
< δ(ε),
1 − (1 − )1−ρ
i=0

which proves the continuity of the map HhA,c : (KM , k · kwρ ) −→ R and hence shows that HhA,c is a
λρ -exponential fading memory filter.
In order to establish the universality statement in the corollary we will proceed, as in the proof of
Theorem 3.1, by showing that L is a polynomial algebra that contains the constant functionals and
separates the points in KM and then by invoking the Stone-Weierstrass theorem using the compactness
of (C 0 (KM ), k · kwρ ).
In order to show that (L , k · kwρ ) is a polynomial algebra, notice first that if A1 , A2 ∈ MN are such
that σmax (A1 ), σmax (A1 ) < 1 − , then
σmax (A1 ⊕ A2 ) = max (σmax (A1 ), σmax (A2 )) < 1 − .

(6.7)

Universal reservoir computers using non-homogeneous state-affine systems

22

If we now take ci ∈ MNi ,ni , i ∈ {1, 2} and h1 , h2 two real-valued polynomials in N1 and N2 variables,
respectively, we have by the first part of the corollary that we just proved that the filter functionals
HhA11 ,c1 and HhA22 ,c2 are well defined. Additionally, by (3.2)-(3.3) so are the combinations HhA11 ,c1 · HhA22 ,c2
and HhA11 ,c1 + λHhA22 ,c2 that satisfy:
2 ,c1 ⊕c2
HhA11 ,c1 · HhA22 ,c2 = HhA11·h⊕A
,
2

⊕A2 ,c1 ⊕c2
HhA11 ,c1 + λHhA22 ,c2 = HhA11⊕λh
,
2

λ ∈ R.

(6.8)

Using the relations (6.8) and (6.7), we can conclude that both HhA11 ,c1 · HhA22 ,c2 and HhA11 ,c1 + λHhA22 ,c2
belong to L ⊂ Rwρ . This implies that (L , k · kwρ ) is a polynomial subalgebra of (Rwρ , k · kwρ )
Since L contains the constant functionals (just take constant readout maps h), in order to conclude
the proof, it is enough to show that the elements in L separate points in KM . Take z1 , z2 ∈ KM ⊂
Z
Z
(Rn ) − such that z1 6= z2 and let A ∈ M(n, n), with σmax (A) < 1−, and c := In . Let U A,c : (Rn ) − −→
n Z−
(R ) be the linear filter associated to A and c via the recursion (3.6). Using the preceding arguments
we have that
∞
X

Aj zt−j .
U A,c (z) t =
j=0


Z
Z
At the same time, it is easy to verify that the filter U In −A,c : (Rn ) − −→ (Rn ) − given by U In −A,c (z) t =
zt − Azt−1 , is the two-sided inverse of U A,c , that is, U A,c ◦ U In −A,c = U In −A,c ◦ U A,c = I(Rn )Z− ,
which guarantees the bijectivity of U A,c and implies in passing that U A,c (z1 ) 6= U A,c (z2 ). Since
polynomials in Rn separate points, there exists a polynomial readout map h : Rn −→ R such that
h U A,c (z1 ) 6= h U A,c (z2 ) which shows that the associated functional HhA,c is such that
HhA,c (z1 ) 6= HhA,c (z2 ) ,

6.6

as required. 

Proof of Proposition 3.5

We start by noting, as we did in the proof of Corollary 3.3, that the condition (3.11) implies that the
reservoir map associated to (3.9) is a contraction and hence, by Lemma 6.1, it satisfies the echo state
property and has a well-defined associated filter.
We now prove that the condition (3.11) implies the convergence of the series in the expression (3.12).
Let K1 := maxz∈I kp(z)k2 = maxz∈I σmax (p(z)) < 1 and K2 := maxz∈I kq(z)k2 = maxz∈I σmax (q(z));
notice that K
1 and K2 are
 well-defined due to the compactness of I. Let now n, m ∈ N and let
Pn Qj−1
Sn := j=0
p(z
)
q(zt−j ) ∈ RN . Then,
t−k
k=0

kSn − Sm k

=

≤

m
X

j−1
Y

j=n+1

k=0

j−1
m
X
Y

!
p(zt−k ) q(zt−j ) ≤

m
X

j−1
Y

j=n+1

k=0

kp(zt−k )k2 kq(zt−j )k ≤ K2

j=n+1 k=0

m
X
j=n+1

K K n+1

kq(zt−j )k

p(zt−k )

K1j ≤ K2

2
∞
X
j=n+1

K1j =

K2 K1n+1
.
1 − K1

2 1
The condition K1 < 1 implies that 1−K
→ 0 as n → ∞ and hence {Sn }n∈N is a Cauchy sequence
1
N
in R that consequently converges. This proves the convergence of the infinite series in (3.12) and
the causal character of the filter that it defines. The time-invariance can also be easily established by
mimicking the verification that we carried out in the proof of Corollary 3.3. We conclude by proving

Universal reservoir computers using non-homogeneous state-affine systems

23

that (3.12) is indeed a solution of (3.9):

∞
X
p(zt )xt−1 + q(zt ) = p(zt ) 

j−1
Y

j=0

k=0



!

p(zt−1−k ) q(zt−1−j ) + q(zt ) = q(zt ) + p(zt )q(zt−1 )

+ p(zt )p(zt−1 )q(zt−2 ) + p(zt )p(zt−1 )p(zt−2 )q(zt−3 ) + · · · =

6.7

∞
X

j−1
Y

j=0

k=0

!
p(zt−k ) q(zt−j ) = xt . 

Proof of Lemma 3.6

(i) =⇒ (ii): kA0 k2 + kA1 k2 + · · · + kAn1 k2 < λ + λ + · · · + λ = λ(n1 + 1) < 1.
(ii) =⇒ (iii): kp(z)k2 = kA0 + zA1 + z 2 A2 + · · · + z n1 An1 k2 ≤ kA0 k2 + |z|kA1 k2 + |z 2 |kA2 k2 + · · · +
|z n1 |kAn1 k2 < kA0 k2 + kA1 k2 + · · · + kAn1 k2 < 1.

6.8

Proof of Proposition 3.7

We start by formulating and proving an elementary result that will be needed later on.
Lemma 6.2 Let f : U ⊂ Rn −→ Mm be a differentiable function defined on the convex set U . For any
z ∈ U denote by ∂i f (z) ∈ Mm the matrix containing the partial derivatives of the components of f with
respect to their ith-entry. Then, for any x, y ∈ U we have:


√
kf (y) − f (x)k2 ≤ nm max
sup k∂i f (z)k2 kx − yk .
(6.9)
i∈{1,...,n}

z∈U

 Pn Pm
Proof. Given A = (Ai,j ) ∈ Mn,m , let kAkF := tr A> A = i=1 j=1 A2i,j be its Frobenius norm.
Recall (see Theorem 5.6.34 and Exercise 5.6.P24 in [Horn 13]) that
√
(6.10)
kAk2 ≤ kAkF ≤ r kAk2 ,
where r is the rank of A. Consider now x, y ∈ U arbitrary and let Df (z) : Rn −→ Mm be the differential
of f evaluated at z ∈ U . The convexity of U implies that the Mean Value Inequality holds (see Theorem
2.4.8 in [Abra 88]) and hence:
kf (y) − f (x)kF ≤ sup kDf ((1 − t)x + ty)k2 kx − yk .

(6.11)

t∈[0,1]

The first inequality in (6.10) and (6.11) imply that
kf (y) − f (x)k2 ≤ sup kDf (z)k2 kx − yk .

(6.12)

z∈U

At the same time, notice that by (6.10)
2

2
kDf (z)k2

≤

2
kDf (z)kF

=

n X
m
X
i=1 j=1

∂i fj2 (z) =

n
X
i=1

2

k∂i f (z)kF ≤ m

n
X
i=1

2

k∂i f (z)k2 ≤ mn

max
i∈{1,...,n}



2
k∂i f (z)k2 .

This inequality together with (6.12) imply the statement (6.9) since the maximum and the supremum
can be trivially exchanged. H
We now carry out the proof of the proposition under the hypothesis (iii) in Lemma 3.6 which
is implied by the other two. The modifications necessary to establish the result under the other two

Universal reservoir computers using non-homogeneous state-affine systems

24

hypotheses are straightforward. Consider two arbitrary elements z, s ∈ I Z− . Then, by the CauchySchwarz and Minkowski inequalities:

∞
X
p,q
p,q
|HW
(z) − HW
(s)| = W> 

j−1
Y

j=0

k=0

≤ kWk

∞
X

!
p(z−k ) q(z−j ) −

j−1
Y

!

!

p(s−k ) q(s−j ) 

k=0

aj (z−j+1 )q(z−j ) − aj (s−j+1 )q(s−j ) ,

where

aj (z−j+1 ) :=

j=0

j−1
Y

p(z−k ). (6.13)

k=0

We now bound the right hand side of (6.13) as follows:
∞
X

aj (z−j+1 )q(z−j ) − aj (s−j+1 )q(s−j )

j=0

=

∞
X

aj (z−j+1 )q(z−j ) + aj (z−j+1 )q(s−j ) − aj (z−j+1 )q(s−j ) − aj (s−j+1 )q(s−j )

j=0

≤

∞
X

aj (z−j+1 )

j=0

kq(z−j ) − q(s−j )k + aj (z−j+1 ) − aj (s−j+1 )

2

2

kq(s−j )k

(6.14)

If Lq is a Lipschitz constant of q : I −→ RN then
aj (z−j+1 )

2

kq(z−j ) − q(s−j )k ≤ Mpj Lq |z−j − s−j | ,

(6.15)

which inserted in (6.14) and in (6.13) implies that

∞
∞
X
X
p,q
p,q
|HW
(z) − HW
(s)| ≤ kWk Lq 
Mpj |z−j − s−j | +
aj (z−j+1 ) − aj (s−j+1 )
j=0

j=0


2

(6.16)



We now bound above the second summand in (6.16) using the inequality (6.9) in the statement of
Lemma 6.2 as well as the following straightforward identity:
aj (z−j+1 ) − aj (s−j+1 ) =

j−1
X
(p(s0 ) · · · p(s−(l−1) ) · p(z−l ) · p(z−(l+1) ) · · · p(z−(j−1) )
l=0

− p(s0 ) · · · p(s−(l−1) ) · p(s−l ) · p(z−(l+1) ) · · · p(z−(j−1) )).
Using this relation we can write:
aj (z−j+1 ) − aj (s−j+1 )

≤

j−1
X

≤
2

j−1
X

p(s0 ) · · · p(s−(l−1) ) · (p(z−l ) − p(s−l )) · p(z−(l+1) ) · · · p(z−(j−1) )

2

l=0

kp(s0 )k2 · · · p(s−(l−1) )

2

· kp(z−l ) − p(s−l )k2 · p(z−(l+1) )

2

· · · p(z−(j−1) )

2

l=0
j
X
√
|z−j+l − s−j+l | ,
≤ Mpj−1 N sup (kp0 (z)k2 )
z∈I

l=1

Universal reservoir computers using non-homogeneous state-affine systems

where the last inequality is a consequence of (6.9). Let Mp0 :=
aj (z−j+1 ) − aj (s−j+1 )

≤
2

√

25

N supz∈I (kp0 (z)k2 ), then

j
j
M p0 j X
Mp0 X l j−l
z−(j−l) − s−(j−l)
Mp
|z−j+l − s−j+l | =
M p Mp
Mp
Mp
l=1

l=1

Since the last term in this inequality is the Cauchy product of the series with general terms Mpn and
Mpn |z−n − s−n |, we can conclude using Merten’s Theorem [Apos 74, Theorem 8.46] that
∞
X

aj (z−j+1 ) − aj (s−j+1 )

j=0

≤
2

∞ j
Mp0 X X l j−l
z−(j−l) − s−(j−l)
M p Mp
Mp j=0
l=1

=

∞
X
1
M p0
M j |z−j − s−j | .
Mp 1 − Mp j=0 p

If we now substitute this relation in (6.16) and we use Lemma 2.1 with weighting sequences wtρ := Mpρt ,
for any ρ ∈ (0, 1), we obtain that:
p,q
p,q
|HW
(z) − HW
(s)|

≤
≤


X
∞
M p0
1
kWk Lq 1 +
M j |z−j − s−j |
Mp 1 − Mp j=0 p



1
1
M p0
kz − skwρ ,
kWk Lq 1 +
Mp 1 − M p
1 − Mp1−ρ

p,q
which proves the continuity of the map HW
: (I Z− , k · kwρ ) −→ R, as required.

6.9



Proof of Proposition 3.8

p2 ,q2
p1 ,q1
are well-defined then, by
, HW
We first recall that since by hypothesis the reservoir functionals HW
2
1
p1 ,q1
p2 ,q2
p1 ,q1
p2 ,q2
the comments that follow (3.2)-(3.3), so are HW1 + λHW2 and HW1 · HW
.
2
The proof of (i) is a straightforward verification. As to (ii), denote first by yt1 , yt2 and x1t , x2t the
outputs and the state variables, respectively, of the SAS corresponding to the two functionals that we
are considering. We note first that by (3.10):
>

yt1 · yt2 = W1> x1t · W2> x2t = (W1 ⊗ W2 ) (x1t ⊗ x2t ).
Using (3.9) it can be readily verified that the time evolution of the tensor product x1t ⊗ x2t is given by
x1t ⊗ x2t = (p1 (zt ) ⊗ p2 (zt ))(x1t−1 ⊗ x2t−1 ) + p1 (zt )x1t−1 ⊗ q2 (zt ) + q1 (zt ) ⊗ p2 (zt )x2t−1 + q1 (zt ) ⊗ q2 (zt ),
which proves (3.20) and hence (3.19).
In order to show that the reservoir functionals on the right hand side of (3.18) and (3.19) are
well-defined we prove the following lemma.
Lemma 6.3 Let p1 (z) ∈ MN1 ,M1 [z] and p2 (z) ∈ MN2 ,M2 [z] be two polynomials with matrix coefficients
and assume that they satisfy that kp1 (z)k2 < 1 −  and kp2 (z)k2 < 1 −  for all z ∈ I := [−1, 1] and a
given 1 >  > 0. Then:
(i) k(p1 ⊕ p2 )(z)k2 < 1 − ,
(ii) k(p1 ⊗ p2 )(z)k2 < 1 − ,

Universal reservoir computers using non-homogeneous state-affine systems

26

for all z ∈ I := [−1, 1].
Proof of the lemma. Suppose that the polynomials p1 and p2 are defined on the vector spaces V1
and V2 , respectively. Let x = x1 ⊕ x2 ∈ V1 ⊕ V2 , with x1 ∈ V1 and x2 ∈ V2 . Then, in order to prove
part (i) note that
k(p1 ⊕ p2 )(z) · xk2 = k(p1 (z) · x1 , p2 (z) · x2 )k2 = kp1 (z) · x1 k2 + kp2 (z) · x2 k2

≤ kp1 (z)k22 kx1 k2 + kp2 (z)k22 kx2 k2 ≤ (1 − )2 kx1 k2 + kx2 k2 = (1 − )2 kxk2 .
This inequality implies that
(1 − )kxk
k(p1 ⊕ p2 )(z) · xk
≤ sup
= 1 − ,
kxk
kxk
x6=0
x6=0

k(p1 ⊕ p2 )(z)k2 = sup

as required.

As to the statement in part (ii):
k(p1 ⊗p2 )(z)k2 = σmax ((p1 ⊗p2 )(z)) = σmax (p1 (z))σmax (p2 (z)) = kp1 (z)k2 kp2 (z)k2 < (1−)2 < (1−). H
p1 ⊕p2 ,q1 ⊕q2
Now, the first part of this lemma and Proposition 3.5 guarantee that HW
is well-defined.
1 ⊕λW2
p,q ⊕q ⊕(q ⊗q )

1
2
1
2
The same conclusion holds for H0⊕0⊕(W
because due to the block diagonal character of (3.20)
1 ⊗λW2 )
then σmax (p(z)) = σmax ((p1 (z) ⊕ p2 (z) ⊕ (p1 ⊗ p2 ) (z)) = kp1 (z) ⊕ p2 (z) ⊕ (p1 ⊗ p2 ) (z)k2 . By parts (i)
and (ii) in Lemma 6.3 we can conclude that kp(z)k2 < 1 −  for all z ∈ [−1, 1] and, again by Proposition
p,q1 ⊕q2 ⊕(q1 ⊗q2 )
3.5, the reservoir functional H0⊕0⊕(W
is well-defined. 
1 ⊗λW2 )

6.10

Proof of Theorem 3.9

Note first that the hypothesis Mp < 1 −  < 1 on the polynomials p associated to the elements in S
implies, by Propositions 3.5 and 3.7, that this family is made of time-invariant reservoir filters that have
the FMP with respect to weighting sequences of the form wtp := Mpρt , ρ ∈ (0, 1). Additionally, using
Lemma 2.6 and the hypothesis Mp < 1 − , for a fixed given  ∈ (0, 1), we can conclude that all the
reservoir filters in S have the FMP with the common weighting sequence wtρ := (1 − )ρt , ρ ∈ (0, 1).
We now show that the elements in S form a polynomial algebra as a consequence mainly of
p2 ,q2
p1 ,q1
: I Z− −→ R are two elements in S then
, HW
Lemma 6.3 and Proposition 3.8. Indeed, if HW
2
p2 ,q2
p11 ,q1
by (3.18) and part (i) of Lemma 6.3 so is HW1 + λHW2 , for any λ ∈ R. The same conclup1 ,q1
p2 ,q2
sion holds for the product HW
· HW
because due to the block diagonal character of (3.20) then
1
2
σmax (p(z)) = σmax ((p1 (z) ⊕ p2 (z) ⊕ (p1 ⊗ p2 ) (z)) = kp1 (z) ⊕ p2 (z) ⊕ (p1 ⊗ p2 ) (z)k2 . By parts (i) and
(ii) in Lemma 6.3 we can conclude that kp(z)k2 < 1 −  for all z ∈ [−1, 1]. The same fact can be stated
p1 ,q1
p2 ,q2
about q1 ⊕ q2 ⊕ (q1 ⊗ q2 ) and hence by (3.19) we obtain that the product HW
· HW
belongs to S .
1
2
Finally, we observe that the family S has the point separation property and contains all the constant
functionals. Indeed, since S includes the linear family L and we proved that given z1 , z2 ∈ KM ⊂
Z
(Rn ) − such that z1 6= z2 there exists A ∈ M(n, n), with σmax (A) < 1 −  and c := In such that
U A,c (z1 ) 6= U A,c (z2 ), this implies the existence of a t ∈ Z such that (U A,c (z1 ))t 6= (U A,c (z2 ))t . The
point separation property follows from choosing any vector W ∈ RN such that W> (U A,c (z1 ))t 6=
A,c
A,c
A,c
A,c
W> (U A,c (z2 ))t , which implies that (UW
(z1 ))t 6= (UW
(z2 ))t . Therefore, UW
(z1 ) 6= UW
(z2 ) and
HU A,c (z1 ) 6= HU A,c (z2 ), as required.
W
W
All the constant functionals can be obtained by taking for p the zero polynomial and for q the
constant polynomials (q has degree zero). In that case, the state variables are a constant sequence
p,q
xt = q and the associated functional is the constant map HW
(z) = W> q, for all z ∈ KM .
The universality result follows hence from the Stone-Weierstrass Theorem and the compactness of
(I Z− , k · kwρ ) established in Lemma 2.2. 

Universal reservoir computers using non-homogeneous state-affine systems

6.11

27

Proof of Lemma 4.1

(i) Let A := {ρ ∈ R+ | kXk < ρ almost surely}. It suffices to show that kXkL∞ := inf A ∈ A, which
implies that kXk ≤ kXkL∞ almost surely. Indeed, consider the sequence aj := kXkL∞ + 1/j, j ∈ N. By
the approximation property of the infimum, there exists a decreasing sequence of numbers {ρj }j∈N ⊂ A
in A satisfying kXkL∞ ≤ ρj < kXkL∞ + 1/j for all j ∈ N. Define F := {ω ∈ Ω | kX(ω)k > kXkL∞ }
and Fj := {ω ∈ Ω | kX(ω)k > ρj }. It is easy to see that Fj ⊂ Fj+1 , j ∈ N and that limj→∞ Fj = F
and, consequently, (see [Grim 01, Lemma 5, page 7]) limj→∞ P(Fj ) = P(F ). Since by construction
P(Fj ) = 0 for all j ∈ N then P(F ) = 0 necessarily, which shows that kXkL∞ ∈ A, as required.
(ii) If kXkL∞ ≤ C then by part (i), kXk ≤ kXkL∞ ≤ C almost surely. Conversely, if kXk ≤ C almost
surely, then C ∈ A = {ρ ∈ R+ | kXk < ρ almost surely}. Consequently, kXkL∞ = inf A ≤ C ∈ A, as
required.
(iii) Suppose first that kXk ≤ C almost surely and define F := {ω ∈ Ω | kX(ω)k > C}. By hypothesis,
we have that P(F ) = 0 and P(Ω \ F ) = 1. Then,
Z
Z
Z
h
i
k
k
k
k
E kXk
=
kXk dP =
kXk dP +
kXk dP
Ω
Ω\F
F
Z
Z
k
k
=
kXk dP ≤
C dP = C k P(Ω \ F ) = C k ,
Ω\F

Ω\F

h
i
k
as required. Conversely, assume that E kXk ≤ C k , for any k ∈ N, and define

Fn :=

1
ω ∈ Ω | kX(ω)k > C +
n


,

for all n ≥ 1. It is easy to see that Fn ⊂ Fn+1 and that limn→∞ Fn = F and, consequently, (see
[Grim 01, Lemma 5, page 7]) limn→∞ P(Fn ) = P(F ). Now,
Z
Z
h
i Z
k
k
k
k
k
C
≥ E kXk =
kXk dP =
kXk dP +
kXk dP
Ω

Z

k

Ω\Fn

Z



kXk dP ≥

≥
Fn

C+
Fn

1
n

Fn

k


dP =

C+

1
n

k
P(Fn ),

k
which implies that P(Fn ) ≤ C k / C + n1 for any k ∈ N and hence, by taking the limit k → ∞, we can
conclude that P(Fn ) = 0. Consequently, P(F ) = limn→∞ P(Fn ) = 0, which shows that kXk ≤ C a.s.
(iv) Since |Xi | ≤ kXk always and by part (i) kXk ≤ kXkL∞ almost surely, we can conclude that
|Xi | ≤ kXkL∞ almost surely. This implies that Xi ∈ L∞ (Ω, R) and hence the statement follows from
part (iii). 

6.12

Proof of Lemma 4.2

Suppose first that




ess sup sup {kzt (ω)k} < sup ess sup {kzt (ω)k} .
ω∈Ω

t∈Z

t∈Z

(6.17)

ω∈Ω

By the approximation property of the supremum [Apos 74, Theorem 1.14], there exists t0 ∈ Z such that




ess sup sup {kzt (ω)k} < ess sup {kzt0 (ω)k} ≤ sup ess sup {kzt (ω)k} .
(6.18)
ω∈Ω

t∈Z

ω∈Ω

t∈Z

ω∈Ω

Universal reservoir computers using non-homogeneous state-affine systems

28

However, kzt0 (ω)k ≤ supt∈Z kzt (ω)k for all ω ∈ Ω and hence by part (i) in Lemma 4.1


kzt0 (ω)k ≤ sup kzt (ω)k ≤ ess sup sup {kzt (ω)k} , almost surely.
ω∈Ω

t∈Z

t∈Z

Now, by part (ii) in Lemma 4.1, this implies that


ess sup {kzt0 (ω)k} ≤ ess sup sup {kzt (ω)k} .
ω∈Ω

ω∈Ω

t∈Z

However, this expression is in contradiction with the first inequality in (6.18) and hence the assumption
(6.17) cannot be correct. This argument implies that




ess sup sup {kzt (ω)k} ≥ sup ess sup {kzt (ω)k} .
ω∈Ω

t∈Z

t∈Z

ω∈Ω

We now prove the reverse inequality, that is,




ess sup sup {kzt (ω)k} ≤ sup ess sup {kzt (ω)k} .
ω∈Ω

t∈Z

t∈Z

By part (ii) of Lemma 4.1, this inequality holds if and only if


sup {kzt (ω)k} ≤ sup ess sup {kzt (ω)k} ,
t∈Z

(6.19)

ω∈Ω

almost surely.

(6.20)

ω∈Ω

t∈Z

Now, by part (i) in Lemma 4.1, we have that kzt (ω)k ≤ ess supω∈Ω {kzt (ω)k}, almost surely and for
each fixed t ∈ Z. Let
S At ⊂ Ω be the zero-measure set
S suchthatPkzt (ω)k > ess supω∈Ω {kzt (ω)k} for all
ω ∈ At . Let A := t∈Z At . Notice that P(A) = P t∈Z At ≤ t∈Z P(At ) = 0 and hence B := Ac has
measure one and
kzt (ω)k ≤ ess sup {kzt (ω)k} , for all ω ∈ B and all t ∈ Z.
ω∈Ω

Since B has measure one, this implies that




sup {kzt (ω)} k ≤ sup ess sup {kzt (ω)k} ,
t∈Z

t∈Z

almost surely,

which is exactly what is required in (6.20) in order for (6.19) to hold.

6.13

(6.21)

ω∈Ω



Proof of Lemma 4.3

It is obvious that L∞ (Ω, `∞ (Rn )) ⊂ L∞ (Ω, `∞ (Rn )). Conversely, if z ∈ L∞ (Ω, `∞ (Rn )) then, by
definition, kzkL∞ < ∞ or, equivalently, ess supω∈Ω {supt∈Z {kzt (ω)k}} < ∞. By part (i) in Lemma 4.1,
this implies that
sup kzt (ω)k < ∞, almost surely.
(6.22)
t∈Z

Since the elements in the spaces in (4.7) are equivalence classes containing almost surely equal random
variables, we can take another representative z∗ : Ω −→ (Rn )Z for the class containing z defined as

z(ω),
when supt∈Z kzt (ω)k < ∞,
∗
z (ω) :=
0,
otherwise.

Since the processes z and z∗ differ by (6.22) only in a set of zero measure, they are equal in L∞ Ω, (Rn )Z
but, this time, z∗ ∈ L∞ (Ω, `∞ (Rn )), as required. Since (`∞ (Rn ), k · k∞ ) is a Banach space, so is
(L∞ (Ω, `∞ (Rn )) , k · kL∞ ) by the references quoted after (4.2) and the statement follows. 

Universal reservoir computers using non-homogeneous state-affine systems

6.14

29

Proof of Theorem 4.4

Proof of part (i). All along this proof we will denote the elements in KM with a lower bold case
L∞
L∞
(z ∈ KM ) and those in KM
with an upper bold case (Z ∈ KM
).
We first assume that the functional H : (KM , k·kw ) −→ R has the fading memory property. This
means that H is a continuous map and since by Lemma 2.2 the space (KM , k·kw ) is compact, then so is
the image H(KM ) as a subset of the real line. This implies that there exists a finite real number L > 0
L∞
such that H(KM ) ⊂ [−L, L]. Let now Z ∈ KM
; the condition kZkL∞ ≤ M is equivalent to kZt k ≤ M ,
for all t ∈ Z− , almost surely, and hence implies that H (Z) ∈ [−L, L], almost surely or, equivalently,
L∞
that kH (Z)kL∞ ≤ L. This, in turn, implies that H(Z) ∈ L∞ (Ω, R) for any Z ∈ KM
, as required.
∞
L
∞
We now show that H : (KM
, k · k L∞
)
−→
L
(Ω,
R)
has
the
FMP.
The
FMP
hypothesis on
w
H : (KM , k·kw ) −→ R implies that for any z ∈ KM and any  > 0 there exists a δ() > 0 such that for
any s ∈ KM that satisfies that
kz − skw = sup k(zt − st )w−t k < δ(),

then

|H(z) − H(s)| < .

(6.23)

t∈Z−

Moreover, since by Lemma 2.2 the space (KM , k·kw ) is compact, the Uniform Continuity Theorem
[Munk 14, Theorem 7.3] guarantees that the relation δ() does not depend on the point z ∈ KM .
L∞
We now prove the statement by showing that for any  > 0 and Z ∈ KM
then kH(Z)−H(S)kL∞ < ,
∞
L
for all S ∈ KM
such that kZ − SkL∞
<
δ().
Indeed,
kZ
−
Sk
<
δ()
if
and
only if supt∈Z− kZt − St kL∞ w−t <
L∞
w
w
δ(). Given that for any l ∈ Z− we have that kZl − Sl kL∞ w−l ≤ supt∈Z− kZt − St kL∞ w−t < δ(),
part (ii) in Lemma 4.1 implies that kZl − Sl k w−l < δ() almost surely for any l ∈ Z− and hence
supt∈Z− kZt − St k w−t = kZ − Skw < δ(), almost surely. This implies, using (6.23), that |H(Z) −
H(S)| < , almost surely, which by part (ii) in Lemma 4.1 implies that kH(Z) − H(S)kL∞ < , as
required.
L∞
, k · kL∞
) −→ L∞ (Ω, R) has the fading memory property then so does
Conversely, if H : (KM
w
L∞
and kzk = kzkL∞ for the elements z ∈ KM .
H : (KM , k·kw ) −→ R because KM ⊂ KM
Proof of part (ii). We suppose first that T is dense in the set (C 0 (KM ), k · kw ) and show that the
L∞
L∞
corresponding family with intputs in KM
is universal. Let H : (KM
, k · k L∞
) −→ L∞ (Ω, R) be an
w
arbitrary causal and time-invariant FMP filter and let HS ∈ T such that supz∈KM kH(z) − HS (z)kL∞ <
. The existence of HS is ensured by the density hypothesis on T . We show that this ensures that
supZ∈KM
L∞ kH(Z) − HS (Z)kL∞ < . Indeed, this conclusion is true if kH(Z) − HS (Z)kL∞ <  for any
L∞
Z ∈ KM which, by part (ii) in Lemma 4.1 is equivalent to |H(Z) − HS (Z)| <  almost surely, for any
L∞
L∞
Z ∈ KM
. This condition is in turn true because as Z ∈ KM
, then kZt k ≤ M almost surely for all
t ∈ Z− and hence Z ∈ KM almost surely. Since HS approximates H for deterministic inputs, we have
that |H(Z) − HS (Z)| <  almost surely, as required.
L∞
Conversely, if the family T with intputs in KM
is universal in the set of continuous maps of the
∞
L
∞
type H : (KM
, k · kL∞
)
−→
L
(Ω,
R)
we
can
easily
show that T is dense in (C 0 (KM ), k · kw ). Let
w
0
L∞
H ∈ (C (KM ), k · kw ) and let HS : (KM , k · kL∞
) −→ L∞ (Ω, R) be the element that, for a given
w
 > 0, satisfies that kH − HS kL∞ = supZ∈KM
L∞ kH(Z) − HS (Z)kL∞ < . Given that, as we pointed out,
L∞
KM ⊂ KM and kzk = kzkL∞ , for the elements z ∈ KM , we have
kH − HS k = sup kH(z) − HS (z)k = sup kH(z) − HS (z)kL∞ ≤
z∈KM

6.15

z∈KM

sup kH(Z) − HS (Z)kL∞ < . 
∞

L
Z∈KM

Proof of Theorem 4.5

We first notice that the polynomial algebra A(R) is, by Theorem 3.1 and the first part of Theorem
4.4, made of fading memory reservoir filters that map into L∞ (Ω, R). Using the other hypotheses in

Universal reservoir computers using non-homogeneous state-affine systems

30

the statement we can easily conclude that the family A(R) satisfies the thesis of Theorem 3.1 and it
is hence universal in the deterministic setup. The result follows from the second part of Theorem 4.4.

Acknowledgments: We thank Philipp Harms for carefully looking at early versions of this work
and for making suggestions that have significantly improved some of our results and Herbert Jaeger
and Josef Teichmann for fruitful discussions. The authors acknowledge partial financial support of
the French ANR “BIPHOPROC” project (ANR-14-OHRI-0002-02) as well as the hospitality of the
Centre Interfacultaire Bernoulli of the Ecole Polytechnique Fédérale de Lausanne during the program
“Stochastic Dynamical Models in Mathematical Finance, Econometrics, and Actuarial Sciences” that
made possible the collaboration that lead to some of the results included in this paper. LG acknowledges
partial financial support of the Graduate School of Decision Sciences and the Young Scholar Fund AFF
of the Universität Konstanz. JPO acknowledges partial financial support coming from the Research
Commission of the Universität Sankt Gallen and the Swiss National Science Foundation (grant number
200021 175801/1).

References
[Abra 88] R. Abraham, J. E. Marsden, and T. S. Ratiu. Manifolds, Tensor Analysis, and Applications.
Vol. 75, Applied Mathematical Sciences. Springer-Verlag, 1988.
[Apos 74] T. Apostol. Mathematical Analysis. Addison Wesley, second Ed., 1974.
[Arno 57] V. I. Arnold. “On functions of three variables”. Proceedings of the USSR Academy of
Sciences, Vol. 114, pp. 679–681, 1957.
[Bai 12]

Bai Zhang, D. J. Miller, and Yue Wang. “Nonlinear system modeling with random matrices: echo state networks revisited”. IEEE Transactions on Neural Networks and Learning
Systems, Vol. 23, No. 1, pp. 175–182, jan 2012.

[Barr 93]

A. Barron. “Universal approximation bounds for superpositions of a sigmoidal function”.
IEEE Transactions on Information Theory, Vol. 39, No. 3, pp. 930–945, may 1993.

[Boll 86]

T. Bollerslev. “Generalized autoregressive conditional heteroskedasticity”. Journal of Econometrics, Vol. 31, No. 3, pp. 307–327, 1986.

[Box 76]

G. E. P. Box and G. M. Jenkins. Time Series Analysis: Forecasting and Control. Holden-Day,
1976.

[Boyd 85] S. Boyd and L. Chua. “Fading memory and the problem of approximating nonlinear operators with Volterra series”. IEEE Transactions on Circuits and Systems, Vol. 32, No. 11,
pp. 1150–1161, nov 1985.
[Broc 06]

P. J. Brockwell and R. A. Davis. Time Series: Theory and Methods. Springer-Verlag, 2006.

[Bueh 06] M. Buehner and P. Young. “A tighter bound for the echo state property”. IEEE Transactions
on Neural Networks, Vol. 17, No. 3, pp. 820–824, 2006.
[Come 06] F. Comets and T. Meyre. Calcul Stochastique et Modèles de Diffusions. Dunod, Paris, 2006.
[Coui 16]

R. Couillet, G. Wainrib, H. Sevi, and H. T. Ali. “The asymptotic performance of linear echo
state neural networks”. Journal of Machine Learning Research, Vol. 17, No. 178, pp. 1–35,
2016.

Universal reservoir computers using non-homogeneous state-affine systems

31

[Croo 07] N. Crook. “Nonlinear transient computation”. Neurocomputing, Vol. 70, pp. 1167–1176,
2007.
[Cybe 89] G. Cybenko. “Approximation by superpositions of a sigmoidal function”. Mathematics of
Control, Signals, and Systems, Vol. 2, No. 4, pp. 303–314, dec 1989.
[Damb 12] J. Dambre, D. Verstraeten, B. Schrauwen, and S. Massar. “Information processing capacity
of dynamical systems”. Scientific reports, Vol. 2, No. 514, 2012.
[Dieu 69]

J. Dieudonne. Foundations of Modern Analysis. Academic Press, 1969.

[Doya 92] K. Doya. “Bifurcations in the learning of recurrent neural networks”. In: Proceedings of
IEEE International Symposium on Circuits and Systems, pp. 2777–2780, IEEE, 1992.
[Engl 82]

R. F. Engle. “Autoregressive conditional heteroscedasticity with estimates of the variance
of United Kingdom inflation”. Econometrica, Vol. 50, No. 4, pp. 987–1007, 1982.

[Flie 76]

M. Fliess. “Un outil algebrique : les series formelles non commutatives”. In: G. Marchesini
and S. K. Mitter, Eds., Mathematical Systems Theory, pp. 122–148, Springer Verlag, 1976.

[Flie 80]

M. Fliess and D. Normand-Cyrot. “Vers une approche algébrique des systèmes non linéaires
en temps discret”. In: A. Bensoussan and J. Lions, Eds., Analysis and Optimization of
Systems. Lecture Notes in Control and Information Sciences, vol. 28, Springer Berlin Heidelberg, 1980.

[Fran 10]

C. Francq and J.-M. Zakoian. GARCH Models: Structure, Statistical Inference and Financial
Applications. Wiley, 2010.

[Galt 14]

M. N. Galtier, C. Marini, G. Wainrib, and H. Jaeger. “Relative entropy minimizing noisy
non-linear neural network to approximate stochastic processes”. Neural Networks, Vol. 56,
pp. 10–21, 2014.

[Gang 08] S. Ganguli, D. Huh, and H. Sompolinsky. “Memory traces in dynamical systems.”. Proceedings of the National Academy of Sciences of the United States of America, Vol. 105, No. 48,
pp. 18970–5, dec 2008.
[Grig 15]

L. Grigoryeva, J. Henriques, L. Larger, and J.-P. Ortega. “Optimal nonlinear information processing capacity in delay-based reservoir computers”. Scientific Reports, Vol. 5,
No. 12858, pp. 1–11, 2015.

[Grig 16a] L. Grigoryeva, J. Henriques, L. Larger, and J.-P. Ortega. “Nonlinear memory capacity of
parallel time-delay reservoir computers in the processing of multidimensional signals”. Neural
Computation, Vol. 28, pp. 1411–1451, 2016.
[Grig 16b] L. Grigoryeva, J. Henriques, and J.-P. Ortega. “Reservoir computing: information processing of stationary signals”. In: Proceedings of the 19th IEEE International Conference on
Computational Science and Engineering, pp. 496–503, 2016.
[Grig 18]

L. Grigoryeva and J.-P. Ortega. “Echo state networks are universal”. Preprint, 2018.

[Grim 01] G. Grimmett and D. Stirzaker. Probability and Random Processes. Oxford University Press,
2001.
[Herm 10] M. Hermans and B. Schrauwen. “Memory in linear recurrent neural networks in continuous
time.”. Neural networks : the official journal of the International Neural Network Society,
Vol. 23, No. 3, pp. 341–55, apr 2010.

Universal reservoir computers using non-homogeneous state-affine systems

32

[Horn 13] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press, second Ed.,
2013.
[Horn 89] K. Hornik, M. Stinchcombe, and H. White. “Multilayer feedforward networks are universal
approximators”. Neural Networks, Vol. 2, No. 5, pp. 359–366, 1989.
[Jaeg 02]

H. Jaeger. “Short term memory in echo state networks”. Fraunhofer Institute for Autonomous Intelligent Systems. Technical Report., Vol. 152, 2002.

[Jaeg 04]

H. Jaeger and H. Haas. “Harnessing Nonlinearity: Predicting Chaotic Systems and Saving
Energy in Wireless Communication”. Science, Vol. 304, No. 5667, pp. 78–80, 2004.

[Jaeg 10]

H. Jaeger. “The ’echo state’ approach to analysing and training recurrent neural networks
with an erratum note”. Tech. Rep., German National Research Center for Information
Technology, 2010.

[Jone 92]

L. K. Jones. “A simple lemma on greedy approximation in hilbert space and convergence
rates for projection pursuit regression and neural network training”. The Annals of Statistics,
Vol. 20, No. 1, pp. 608–613, 1992.

[Kolm 56] A. N. Kolmogorov. “On the representation of continuous functions of several variables as
superpositions of functions of smaller number of variables”. Soviet Math. Dokl, Vol. 108,
pp. 179–182, 1956.
[Kurk 05] V. Kurkova and M. Sanguineti. “Learning with generalization capability by kernel methods
of bounded complexity”. Journal of Complexity, Vol. 21, No. 3, pp. 350–367, 2005.
[Ledo 91]

M. Ledoux and M. Talagrand. Probability in Banach Spaces. Springer-Verlag, 1991.

[Lord 14]

G. J. Lord, C. E. Powell, and T. Shardlow. An Introduction to Computational Stochastic
PDES. Cambridge University Press, 2014.

[Luko 09] M. Lukoševičius and H. Jaeger. “Reservoir computing approaches to recurrent neural network training”. Computer Science Review, Vol. 3, No. 3, pp. 127–149, 2009.
[Maas 00] W. Maass and E. D. Sontag. “Neural Systems as Nonlinear Filters”. Neural Computation,
Vol. 12, No. 8, pp. 1743–1772, aug 2000.
[Maas 02] W. Maass, T. Natschläger, and H. Markram. “Real-time computing without stable states:
a new framework for neural computation based on perturbations”. Neural Computation,
Vol. 14, pp. 2531–2560, 2002.
[Maas 04] W. Maass, T. Natschläger, and H. Markram. “Fading memory and kernel properties of
generic cortical microcircuit models”. Journal of Physiology Paris, Vol. 98, No. 4-6 SPEC.
ISS., pp. 315–330, 2004.
[Maas 07] W. Maass, P. Joshi, and E. D. Sontag. “Computational aspects of feedback in neural circuits”. PLoS Computational Biology, Vol. 3, No. 1, p. e165, 2007.
[Maas 11] W. Maass. “Liquid state machines: motivation, theory, and applications”. In: S. S. Barry
Cooper and A. Sorbi, Eds., Computability In Context: Computation and Logic in the Real
World, Chap. 8, pp. 275–296, 2011.
[Mack 77] M. C. Mackey and L. Glass. “Oscillation and chaos in physiological control systems”. Science,
Vol. 197, pp. 287–289, 1977.

Universal reservoir computers using non-homogeneous state-affine systems

33

[Manj 13] G. Manjunath and H. Jaeger. “Echo state property linked to an input: exploring a fundamental characteristic of recurrent neural networks”. Neural Computation, Vol. 25, No. 3,
pp. 671–696, 2013.
[Matt 92] M. B. Matthews. On the UniformApproximation of Nonlinear Discrete-Time FadingMemory Systems Using Neural Network Models. PhD thesis, ETH Zürich, 1992.
[Matt 93] M. B. Matthews. “Approximating nonlinear fading-memory operators using neural network
models”. Circuits, Systems, and Signal Processing, Vol. 12, No. 2, pp. 279–307, jun 1993.
[Munk 14] J. Munkres. Topology. Pearson, second Ed., 2014.
[Perr 96]

P. C. Perryman. Approximation Theory for Deterministic and Stochastic Nonlinear Systems.
PhD thesis, University of California, Irvine, 1996.

[Perr 97]

P. Perryman and A. Stubberud. “Uniform, in-probability approximation of stochastic systems”. In: Conference Record of The Thirtieth Asilomar Conference on Signals, Systems
and Computers, pp. 146–150, IEEE Comput. Soc. Press, 1997.

[Pisi 81]

G. Pisier. “Remarques sur un résultat non publié de B. Maurey”. Séminaire d’analyse
fonctionnelle École Polytechnique, pp. 1–12, 1981.

[Rusc 98] L. Rüschendorf and W. Thomsen. “Closedness of sum spaces and the generalized schrödinger
Problem”. Theory of Probability & Its Applications, Vol. 42, No. 3, pp. 483–494, jan 1998.
[Sont 79a] E. Sontag. “Realization theory of discrete-time nonlinear systems: Part I-The bounded
case”. IEEE Transactions on Circuits and Systems, Vol. 26, No. 5, pp. 342–356, may 1979.
[Sont 79b] E. D. Sontag. “Polynomial Response Maps”. In: Lecture Notes Control in Control and
Information Sciences. Vol. 13, Springer Verlag, 1979.
[Spre 65]

D. A. Sprecher. “A representation theorem for continuous functions of several variables”.
Proceedings of the American Mathematical Society, Vol. 16, No. 2, p. 200, apr 1965.

[Spre 96]

D. A. Sprecher. “A numerical implementation of Kolmogorov’s superpositions”. Neural
Networks, Vol. 9, No. 5, pp. 765–772, 1996.

[Spre 97]

D. A. Sprecher. “A numerical implementation of Kolmogorov’s superpositions II”. Neural
Networks, Vol. 10, No. 3, pp. 447–457, 1997.

[Stub 97a] A. Stubberud and P. Perryman. “Current state of system approximation for deterministic
and stochastic systems”. In: Conference Record of The Thirtieth Asilomar Conference on
Signals, Systems and Computers, pp. 141–145, IEEE Comput. Soc. Press, 1997.
[Stub 97b] A. Stubberud and P. Perryman. “State of system approximation for stochastic systems”.
In: Proceedings of 13th International Conference on Digital Signal Processing, pp. 711–714,
IEEE, 1997.
[Suss 76]

H. J. Sussmann. “Semigroup representations, bilinear approximations of input-output maps,
and generalized inputs”. In: G. Marchesini and S. K. MItter, Eds., Mathematical Systems
Theory, pp. 172–191, Springer Verlag, 1976.

[Take 81]

F. Takens. “Detecting strange attractors in turbulence”. pp. 366–381, Springer Berlin
Heidelberg, 1981.

Universal reservoir computers using non-homogeneous state-affine systems

[Vers 07]

34

D. Verstraeten, B. Schrauwen, M. D’Haene, and D. Stroobandt. “An experimental unification
of reservoir computing methods”. Neural Networks, Vol. 20, pp. 391–403, 2007.

[Wain 16] G. Wainrib and M. N. Galtier. “A local echo state property through the largest Lyapunov
exponent”. Neural Networks, Vol. 76, pp. 39–45, apr 2016.
[Whit 04] O. White, D. Lee, and H. Sompolinsky. “Short-Term Memory in Orthogonal Neural Networks”. Physical Review Letters, Vol. 92, No. 14, p. 148102, apr 2004.
[Yild 12]

I. B. Yildiz, H. Jaeger, and S. J. Kiebel. “Re-visiting the echo state property.”. Neural
networks : the official journal of the International Neural Network Society, Vol. 35, pp. 1–9,
nov 2012.

[Zang 04] G. Zang and P. A. Iglesias. “Fading memory and stability”. Journal of the Franklin Institute,
Vol. 340, No. 6-7, pp. 489–502, 2004.

