isomorphism_. Roughly speaking, we say that two reservoir systems with the
echo state property are system isomorphic if when given the same input
sequence the two reservoir systems (asymptotically) produce the same output
sequence. This result is expressed in terms of _filters_ and _functions_ in
Theorem 6.2.2 which appears in Chapter 6.

In practice, the reservoir matrix $A$ and input vector $C$ are randomly
generated, so we are interested in random variables $A,C$ that yield an
embedding almost surely. We establish this in the following theorem. Before we
state the result, we recall the following definition: that a real-matrix-
valued random variable $X$ is non-singular if $\mathbb{P}[X\in\\{A\\}]=0$ for
all real matrices $A$.

######  Theorem 4.2.4.

If $A\in\mathbb{M}_{N\times N}(\mathbb{R})$ and $C\in\mathbb{R}^{N}$ are
randomly drawn from non-singular distributions then conditions $(C),(D)$ in
Theorem 4.2.1 hold almost surely.

We thank Friedrich Philipp for answering _this_ 111Click the word _this_ to
follow a link to the question question we posted on
https://math.stackexchange.com, which made the proof possible. The proof uses
standard techniques in random matrix theory, and proceeds in three stages.

  1. 1.

We show that a polynomial in $n$ variables, which is not identically zero, is
non-zero almost everywhere.

  2. 2.

This implies that for linearly independent polynomials
$p_{1},p_{2},\ldots,p_{n}$ the random vectors

$\displaystyle p_{1}(A)C,p_{2}(A)C,\ldots,p_{n}(A)C$

are linearly independent almost surely.

  3. 3.

Then the vectors described in $(C)$ and $(D)$ are manipulated until we can
apply item 2. to yield the result.

The proof of this result is detailed in Grigoryeva et al. (2021b) and section
4.4 of this thesis.

######  Remark 4.2.5.

The results in this chapter apply to linear reservoir maps of the form
$F(x,z)=Ax+Cz$; and we can easily extend the results to affine reservoir maps
of the form $F(x,z)=Ax+Cz+b$.

A natural question is now: can prove similar results for more general
reservoir maps like ESNs with nonlinear activations $F(x,z)=\sigma(Ax+Cz+b)$?
We believe such a result exists by the weight of numerical evidence. For now,
the answer is no. The techniques used is this present Chapter exploit the
linearity of the reservoir map, as well as the explicit form of the GS

$\displaystyle
f_{(\phi,\omega,F)}(m)=\sum^{\infty}_{k=0}A^{k}C\omega\circ\phi^{-k}(m)$

which we have not obtained for reservoir maps in general. To prove that a more
general reservoir map admits an embedding GS, a different line of attack is
required.

###  4.3 An embedding allows for learning

We have stated conditions under which a reservoir maps of the form

$\displaystyle F(x,z)=Ax+Cz$

with randomly generated $A,C$ admits a GS $f_{(\omega,\phi,F)}$ which is an
embedding. If an embedding is achieved, then we have sufficient conditions for
learning. We recall that an embedding on a compact manifold is injective and
immersive, and both of these properties have an interpretation in the context
of learning. Verzelli identified that when the GS $f_{(\omega,\phi,F)}$ is
injective the reservoir map has learned the pointwise properties of the
system, which allows pointwise approximation of target functions, such as the
next step map for forecasting. We observe in this chapter that if the GS
$f_{(\omega,\phi,F)}$ is immersive, then the reservoir map will learn deeper
properties of the system, such as the eigenvalues of the linearisation of
fixed points.

Having achieved an embedding with a linear reservoir map, we are now in a
position to approximate an arbitrary target function, for example, the next
step map used to forecast the future time series of observations. We could,
for example, train a feedforward neural to map the reservoir states
$\\{x_{k}\\}_{k=1,\ldots,\ell-1}$ onto the observations
$\\{z_{k+1}\\}_{k=1,\ldots,\ell}$. Training a feedforward neural network is a
nonlinear optimisation problem, which is undesirable in the reservoir
computing paradigm where training is usually linear regression. To avoid
nonlinear training we can pass the reservoir states
$\\{x_{k}\\}_{k=1,\ldots,\ell-1}$ through a nonlinear function
$g:\mathbb{R}^{N}\to\mathbb{R}^{T}$ (called a nonlinear kernel) and then find
$W^{*}\in\mathbb{R}^{T}$ that solves the linear least squares problem

$\displaystyle
W^{*}=\operatorname*{arg\,min}_{W\in\mathbb{R}^{T}}\sum_{k=0}^{\ell-1}\lVert
W^{\top}g(x_{k})-z_{k+1}\rVert^{2}+\lambda\lVert W\rVert^{2}.$

This is exactly the approach taken by doi:10.1063/5.0024890 and
arXiv:2106.07688 in what the authors call _next generation reservoir
computing_. The authors demonstrate empirically that a polynomial kernel $g$
is suitable for forecasting the future trajectory of chaotic dynamical
systems.

###  4.4 Novel results in detail

####  4.4.1 Existence of $C^{2}$ GS

In this section we will prove Theorems 4.2.1 and 4.2.4. The proofs closely
follow those in Grigoryeva et al. (2021b). The proofs involve calculus on
manifolds so we will start by reviewing some relevant theory of calculus on
manifolds. Recall that if $f\in C^{r}(M,\mathbb{R}^{N})$ then $Df:TM\to
T(\mathbb{R}^{N})$ is the differential of $f$, and $TM$ is the tangent bundle
of $M$, and $T(\mathbb{R}^{N})=\mathbb{R}^{N}\times\mathbb{R}^{N}$ is the
tangent bundle of $\mathbb{R}^{N}$. Furthermore, if
$\phi\in\text{Diff}^{r}(M)$ then $T\phi:TM\to TM$ is the tangent map of
$\phi$.

The differential $Df$ and tangent map $T\phi$ are generalisations of the first
derivative. Since the tangent bundle $TM$ of $M$ and the tangent bundle of
$\mathbb{R}^{N}$ are themselves manifolds, we can define the second order
differential

$\displaystyle D^{2}f:=D(Df):T(TM)\to T(T(\mathbb{R}^{N})),$

as the differential of the differential $Df$. Here $T(TM)$ is the tangent
bundle of the tangent bundle of $M$, and $T(T(\mathbb{R}^{N}))$ is the tangent
bundle of the tangent bundle of $\mathbb{R}^{N}$. Likewise, we can define the
second order tangent map

$\displaystyle T^{2}\phi:=T(T\phi):T(TM)\to T(TM)$

as the tangent map of the tangent map. We can proceed recursively to define
for each $i\in\\{1,\ldots,r\\}$ the differential and tangent map of order $i$
denoted $D^{i}f$ and $T^{i}\phi$ respectively.

We are now ready to establish a lemma stating that the GS
$f_{(\phi,\omega,F)}$ associated to the linear reservoir map exists, is
$C^{2}$, and, for an open subset of observations functions, is an embedding.

######  Lemma 4.4.1.

Let $\phi\in{\rm Diff}^{1}(M)$ be a dynamical system on the smooth manifold
$M$ (not necessarily compact) and consider the observation map $\omega\in
C^{1}(M,\mathbb{R})$. Let $F:\mathbb{R}^{N}\times\mathbb{R}\to\mathbb{R}^{N}$
be a linear state map given by $F(x,z):=Ax+Cz$ with
$A\in\mathbb{M}_{N,N}(\mathbb{R})$, $C\in\mathbb{R}^{N}$, $N\in\mathbb{N}$.

(i)

If the spectral radius of $A$ satisfies that $\rho(A)<1$ and $\omega$ maps
into a bounded subset of $\mathbb{R}$ then the GS
$f_{(\phi,\omega,F)}:M\to\mathbb{R}^{N}$ associated to $F$ exists and is
continuous.

(ii)

Additionally, let $r\in\mathbb{N}$ and suppose that $\phi\in{\rm Diff}^{r}(M)$
and that there exist constants $k_{1},\ldots,k_{r}\in\mathbb{N}$ such that
$\left\|A^{k_{i}}\right\|\left\|T^{i}\phi^{-k_{i}}\right\|_{\infty}<1$,
$\left\|T^{i}\phi^{-1}\right\|_{\infty}<\infty$ for all
$i\in\left\\{1,\ldots,r\right\\}$. Then for any $\omega\in
C^{r}(M,\mathbb{R})$ such that $\left\|D^{i}\omega\right\|_{\infty}<\infty$,
for all $i\in\left\\{1,\ldots,r\right\\}$, the map $f_{(\phi,\omega,F)}$
belongs to $C^{i}(M,\mathbb{R}^{N})$ and the higher order derivatives are
given by:

$D^{i}f_{(\phi,\omega,F)}(m)=\sum_{j=0}^{\infty}A^{j}CD^{i}\left(\omega\circ\phi^{-j}\right)(m),\mbox{
for all $i\in\left\\{1,\ldots,r\right\\}$.}$ (4.1)

(iii)

Suppose now that $M$ is compact. Under the hypotheses of points (i) and (ii)
above, the map

$\begin{array}[]{cccc}\Theta_{(\phi,F)}:&C^{r}(M,\mathbb{R})&\to&C^{r}(M,\mathbb{R}^{N})\\\
&\omega&\longmapsto&f_{(\phi,\omega,F)}\end{array}$ (4.2)

is continuous. Moreover, the subsets $\Omega_{\text{imm}}$ and
$\Omega_{\text{emb}}$ of $C^{r}(M,\mathbb{R})$ for which the corresponding GSs
are immersions and embeddings, respectively, are open.

###### Proof.

(i) This statement is obtained by combining the Weierstrass M-test and
Gelfand’s formula for the spectral radius, that is,
$\lim\limits_{k\rightarrow\infty}\left\|{A^{k}}\right\|^{1/k}=\rho(A)$. Since
by hypothesis $\rho(A)<1$, we can guarantee the existence of a number
$k_{0}\in\mathbb{N}$ such that $\left\|A^{k_{0}}\right\|<1$, for all $k\geq
k_{0}$. Consider now the series
$\sum_{j=0}^{\infty}A^{j}C\omega(\phi^{-j}(m))$ that defines
$f_{(\phi,\omega,F)}(m)$. Given that for any $j\in\mathbb{N}$ there exist
$l(j)\in\mathbb{N}$ and $i\in\left\\{0,\ldots,k_{0}-1\right\\}$ such that
$A^{j}=A^{l(j)k_{0}+i}$, we then have that,

$\left\|A^{j}C\omega(\phi^{-j}(m))\right\|\leq\left\|A^{k_{0}}\right\|^{l(j)}\left\|C\right\|K_{A}K_{\omega},$
(4.3)

with
$K_{A}=\max\left\\{1,\left\|A\right\|,\ldots,\left\|A^{k_{0}-1}\right\|\right\\}$
and $K_{\omega}\in\mathbb{R}$ a constant that satisfies
$\lVert\omega(m)\rVert\leq K_{\omega}$ for any $m\in M$ and is available by
the boundedness hypothesis on $\omega(M)$.

The inequality (4.3) and the Weierstrass M-test guarantee that the series
$\sum_{j=0}^{\infty}A^{j}C\omega(\phi^{-j}(m))$ converges absolutely and
uniformly on $M$ and that

$\displaystyle\left\|f_{(\phi,\omega,F)}(m)\right\|=\left\|\sum_{j=0}^{\infty}A^{j}C\omega(\phi^{-j}(m))\right\|$
$\displaystyle\leq\sum_{j=0}^{\infty}\left\|A^{k_{0}}\right\|^{l(j)}\left\|C\right\|K_{A}K_{\omega}$
$\displaystyle=k_{0}\sum_{l=0}^{\infty}\left\|A^{k_{0}}\right\|^{l}\left\|C\right\|K_{A}K_{\omega}=\frac{k_{0}\left\|C\right\|K_{A}K_{\omega}}{1-\left\|A^{k_{0}}\right\|}.$

Finally, since each of the summands in the series is a continuous function
then so is $f_{(\phi,\omega,F)}$.

(ii) The result that we just proved guarantees that if the differentials
$D^{i}f_{(\phi,\omega,F)}(m)$, $i\in\left\\{1,\ldots,r\right\\}$, exist then
they are given by the series
$\sum_{j=0}^{\infty}A^{j}CD^{i}\left(\omega\circ\phi^{-j}\right)(m)$ that,
using again the Weierstrass M-test and the hypotheses in the statement, will
be now shown to uniformly converge to a continuous map. Indeed, using again
the decomposition $A^{j}=A^{l(j)k_{i}+s}$ in terms of the element
$k_{i}\in\mathbb{N}$ such that
$\left\|A^{k_{i}}\right\|\left\|T^{i}\phi^{-k_{i}}\right\|_{\infty}<1$ we can
conclude that each summand of this series satisfies that

$\left\|A^{j}CD^{i}\left(\omega\circ\phi^{-j}\right)(m)\right\|\leq\left(\left\|A^{k_{i}}\right\|\left\|T^{i}\phi^{-k_{i}}\right\|_{\infty}\right)^{l(j)}\left\|C\right\|K_{A}^{i}K_{T^{i}\phi^{-1}}\left\|D^{i}\omega\right\|_{\infty},$
(4.4)

with

$\displaystyle
K_{A}^{i}:=\max\left\\{1,\left\|A\right\|,\ldots,\left\|A^{k_{i}-1}\right\|\right\\},\text{
and
}K_{T^{i}\phi^{-1}}:=\max\left\\{1,\left\|T^{i}\phi^{-1}\right\|_{\infty},\ldots,\left\|T^{i}\phi^{-1}\right\|_{\infty}^{k_{i}-1}\right\\},$

hence

$\left\|D^{i}f_{(\phi,\omega,F)}(m)\right\|=\left\|\sum_{j=0}^{\infty}A^{j}CD^{i}\left(\omega\circ\phi^{-j}\right)(m)\right\|\leq\frac{k_{i}\left\|C\right\|K_{A}^{i}K_{T^{i}\phi^{-1}}\left\|D^{i}\omega\right\|_{\infty}}{1-\left\|A^{k_{i}}\right\|\left\|T^{i}\phi^{-k_{i}}\right\|_{\infty}}.$
(4.5)

which proves the desired convergence and that
$D^{i}f_{(\phi,\omega,F)}(m)=\sum_{j=0}^{\infty}A^{j}CD^{i}\left(\omega\circ\phi^{-j}\right)(m)$.
Moreover,

(iii) We start by noting that if the map (4.2) is continuous then the subsets
$\Omega_{\text{imm}}$ and $\Omega_{\text{emb}}$ are open because by Theorems
1.1 and 1.4 in Hirsch:book the immersions and the embeddings in
$C^{r}(M,\mathbb{R}^{N})$ are open and hence $\Omega_{\text{imm}}$ and
$\Omega_{\text{emb}}$ are the preimages of those open sets by the continuous
map $\Theta_{(\phi,F)}$. We establish now the continuity of
$\Theta_{(\phi,F)}$ by showing that if the sequence
$\left\\{\omega_{n}\right\\}_{n\in\mathbb{N}}$ in $C^{r}(M,\mathbb{R})$
converges to some element $\omega\in C^{r}(M,\mathbb{R})$ then so does
$\left\\{\Theta_{(\phi,F)}(\omega_{n})\right\\}_{n\in\mathbb{N}}\subset
C^{r}(M,\mathbb{R}^{N})$ with respect to $\Theta_{(\phi,F)}(\omega)\in
C^{r}(M,\mathbb{R}^{N})$. Indeed, if $\omega_{n}\to\omega$ then, using the
notation introduced in (4.5), we have that for a given $\epsilon>0$ and for
$n$ sufficiently large

$\frac{k_{i}\left\|C\right\|K_{A}^{i}K_{T^{i}\phi^{-1}}}{1-\left\|A^{k_{i}}\right\|\left\|T^{i}\phi^{-k_{i}}\right\|_{\infty}}\left\|D^{i}\omega_{n}-D^{i}\omega\right\|_{\infty}<\epsilon/r.$

Then,

$\left\|\Theta_{(\phi,F)}(\omega_{n})-\Theta_{(\phi,F)}(\omega)\right\|_{C^{r}(M,\mathbb{R}^{N})}=\sum_{i=0}^{r}\left\|D^{i}f_{(\phi,\omega_{n},F)}-D^{i}f_{(\phi,\omega,F)}\right\|_{\infty}\\\
=\sum_{i=0}^{r}\left\|\sum_{j=0}^{\infty}A^{j}CD^{i}\left((\omega_{n}-\omega)\circ\phi^{-j}\right)(m)\right\|\leq\sum_{i=0}^{r}\frac{k_{i}\left\|C\right\|K_{A}^{i}K_{T^{i}\phi^{-1}}}{1-\left\|A^{k_{i}}\right\|\left\|T^{i}\phi^{-k_{i}}\right\|_{\infty}}\left\|D^{i}\omega_{n}-D^{i}\omega\right\|_{\infty}\\\
<\frac{\epsilon}{r}+\cdots+\frac{\epsilon}{r}=\epsilon,$

as required. ∎

####  4.4.2 Immersive GS

Next we will prove that for generic observation functions $\omega$ the GS
$f_{(\phi,\omega,F)}$ is an immersion.

######  Theorem 4.4.2.

Let $\phi\in{\rm Diff}^{2}(M)$ be a dynamical system on a compact manifold $M$
of dimension $q$ that has only finitely many periodic orbits. Let
$F:\mathbb{R}^{N}\times\mathbb{R}\to\mathbb{R}^{N}$ be a linear state map with
$N\geq 2q$ whose connectivity matrix satisfies that $\rho(A)<1$ and such that
for any observation map $\omega\in C^{2}(M,\mathbb{R})$ the corresponding
generalized synchronization $f_{(\phi,\omega,F)}\in C^{2}(M,\mathbb{R}^{N})$
and, moreover, the map $\Theta_{(\phi,F)}:C^{2}(M,\mathbb{R})\to
C^{2}(M,\mathbb{R}^{N})$ introduced in (4.2) is continuous. Suppose also that
the two following conditions hold:

(i)

For each periodic orbit $m$ of $\phi$ with period $n\in\mathbb{N}$, the
derivative $T_{m}\phi^{-n}$ has $q$ distinct eigenvalues
$\lambda_{1},\lambda_{2},\ldots,\lambda_{q}$. Let $\lambda_{{\rm max}}$ be the
eigenvalue with the highest absolute value among the eigenvalues of all those
linear maps and let $n_{{\rm min}}$ be the smallest period. Suppose that
$\lambda_{{\rm max}}\rho(A^{n_{{\rm min}}})<1$ and that for any periodic point
$m$, the vectors

$\left\\{\left(I-\lambda_{j}A^{n}\right)^{-1}\left(I-A\right)^{-1}\left(I-A^{n}\right)C\right\\}_{j\in\left\\{1,\ldots,q\right\\}},\
\mbox{ with $\lambda_{j}$ eigenvalue of $T_{m}\phi^{-n}$}$ (4.6)

form a linearly independent set.

(ii)

The vectors $\left\\{A^{j}C\right\\}_{j\in\left\\{0,1,\ldots,N-1\right\\}}$
form a linearly independent set.

Then, for generic $\omega\in C^{2}(M,\mathbb{R}^{N})$ the generalized
synchronization $f_{(\phi,\omega,F)}\in C^{2}(M,\mathbb{R})$ is an immersion.

###### Proof.

We proceed in two steps. In the first one we show that $f_{(\phi,\omega,F)}\in
C^{2}(M,\mathbb{R})$ is an immersion at periodic points and in the second one
we take care of the remaining points. We emphasize that equilibria can be seen
as periodic points with period $1$.

Step 1. Immersion at periodic points. We start this part with three
preparatory lemmas.

######  Lemma 4.4.3.

Consider a connectivity matrix that satisfies the conditions $\rho(A)<1$ and
also that $\rho(\lambda_{{\rm max}}A^{n_{{\rm min}}})<1$ as in part (i)  of
the statement of the theorem. Then, for any periodic point $m$ with period $n$
and any eigenvalue $\lambda_{j}$ of $T_{m}\phi^{-n}$, we have that
$\rho(\lambda_{j}A^{n})<1$ and

$(I-\lambda_{j}A^{n})^{-1}=\sum_{k=0}^{\infty}\lambda_{j}^{k}A^{nk}.$ (4.7)

###### Proof.

Firstly, recall that for any square matrix $B$ such that $\rho(B)<1$ then
$\left(I-B\right)^{-1}=\sum_{j=0}^{\infty}B^{j}$. Let now $m$ be a periodic
point with period $n$ and let $\lambda_{j}$ be an eigenvalue of
$T_{m}\phi^{-n}$. This implies that in order for (4.7) to hold we just need to
show that $\rho(\lambda_{j}A^{n})<1$. This is indeed true since any element in
the spectrum of $\lambda_{j}A^{n}$ can be written as $\lambda_{j}\mu_{k}^{n}$
with $\mu_{k}\in\mathbb{C}$ an eigenvalue of $A$. Moreover, let $c<1$ such
that $\left|\lambda_{j}\right|=c\left|\lambda_{{\rm max}}\right|$. Then

$\left|\lambda_{j}\mu_{k}^{n}\right|=c\left|\lambda_{{\rm
max}}\mu_{k}^{n_{{\rm min}}}\right|\left|\mu_{k}^{n-n_{{\rm min}}}\right|<1,$

as required. Notice that in the last inequality we used that
$\rho(\lambda_{{\rm max}}A^{n_{{\rm min}}})<1$ and that $\rho(A)<1$. ∎

######  Lemma 4.4.4.

In the hypotheses of the statement of the theorem, let $m\in M$ be a periodic
point of $\phi\in{\rm Diff}^{2}(M)$ with period $n\in\mathbb{N}$. Let
$\left\\{\mathbf{v}_{1},\ldots,\mathbf{v}_{p}\right\\}$ be a basis of
eigenvectors associated to the distinct eigenvalues
$\lambda_{1},\lambda_{2},\ldots,\lambda_{q}$. Suppose that the set

$\left\\{(I-\lambda_{j}A^{n})^{-1}\sum^{n-1}_{k=0}A^{k}CD(\omega\circ\phi^{-k})(m)\mathbf{v}_{j}\right\\}_{j\in\left\\{1,\ldots,q\right\\}}$
(4.8)

is linearly independent. Then $f_{(\phi,\omega,F)}$ is an immersion at the
periodic point $m$ for generic $\omega\in C^{2}(M,\mathbb{R}^{N})$.

###### Proof.

Since the eigenvalues $\lambda_{j}$ are distinct and the eigenvectors
$\mathbf{v}_{j}$ are hence linearly independent, it is enough to show that the
set
$\left\\{Df_{(\phi,\omega,F)}(m)\mathbf{v}_{j}\right\\}_{j\in\left\\{1,\ldots,q\right\\}}$
is linearly independent in order to conclude that $Df_{(\phi,\omega,F)}(m)$ is
injective. Now, by the expression (4.1):

$\displaystyle Df_{(\phi,\omega,F)}(m)\mathbf{v}_{j}$
$\displaystyle=\sum^{\infty}_{l=0}A^{l}CD(\omega\circ\phi^{-l})(m)\mathbf{v}_{j}$
$\displaystyle=\sum^{\infty}_{l=0}\sum_{k=0}^{n-1}A^{ln+k}CD(\omega\circ\phi^{-(ln+k)})(m)\mathbf{v}_{j}$
$\displaystyle=\sum^{\infty}_{l=0}\sum_{k=0}^{n-1}A^{ln+k}CD(\omega\circ\phi^{-k})(m)[T\phi^{-n}(m)]^{l}\mathbf{v}_{j}$
$\displaystyle=\sum^{\infty}_{l=0}\sum_{k=0}^{n-1}A^{ln+k}CD(\omega\circ\phi^{-k})(m)\lambda^{l}_{j}\mathbf{v}_{j}$
$\displaystyle=\sum^{\infty}_{l=0}(\lambda_{j}A^{n})^{l}\sum_{k=0}^{n-1}A^{k}CD(\omega\circ\phi^{-k})(m)\mathbf{v}_{j}$
$\displaystyle=(I-\lambda_{j}A^{n})^{-1}\sum^{n-1}_{k=0}A^{k}CD(\omega\circ\phi^{-k})(m)\mathbf{v}_{j},$

and so, since by assumption the set of vectors of the form of the RHS are
linearly independent, so are the vectors of the form of the LHS, which proves
the statement. ∎

######  Lemma 4.4.5.

Let $A$ and $B$ two square matrices of the same size such that $\det(A)=0$ and
$\det(B)\neq 0$. Then, there exists $\varepsilon>0$ such that

$\det(A-\varepsilon B)\neq 0.$

###### Proof.

Consider the singular matrix $B^{-1}A$ and let $\lambda_{0}$ be its non-zero
eigenvalue that has the smallest absolute value. Then, for any
$0<\varepsilon<|\lambda_{0}|$ we necessarily have that
$\det\left(B^{-1}A-\varepsilon I\right)\neq 0$ because otherwise $\varepsilon$
would be an eigenvalue of $B^{-1}A$ which is impossible by the minimality of
$\lambda_{0}$. This implies that $C:=B^{-1}A-\varepsilon I$ is invertible and
hence so is $BC=A-\varepsilon B$, as required.

∎

As a corollary of this lemma we can conclude that if
$\mathcal{V}:=\left\\{\mathbf{v}_{1},\ldots,\mathbf{v}_{n}\right\\}$ and
$\mathcal{W}:=\left\\{\mathbf{w}_{1},\ldots,\mathbf{w}_{n}\right\\}$ are two
sets of vectors in ${\mathbb{R}}^{n}$, then there exists $\varepsilon>0$ such
that the set
$\left\\{\mathbf{v}_{1}+\varepsilon\mathbf{w}_{1},\ldots,\mathbf{v}_{n}+\varepsilon\mathbf{w}_{n}\right\\}$
is made of linearly independent vectors. This fact is used at the end of the
proof of Step 1 of Theorem 4.4.2.

We now use this result to show that, for generic $\omega\in
C^{2}(M,\mathbb{R}^{N})$, the generalized synchronization
$f_{(\phi,\omega,F)}\in C^{2}(M,\mathbb{R})$ is an immersion at the periodic
points of $\phi$. Let $m_{1},\ldots,m_{P}\in M$ be the distinct periodic
points of $\phi$, having periods $n_{1},\ldots,n_{P}\in\mathbb{N}$,
respectively (the equilibria of $\phi$ are included in this list with periods
equal to one). The term distinct means that none of those points are in the
orbits of the others. We now choose $P$ disjoint open neighborhoods $B_{i}$
that contain each of the distinct periodic points $m_{i}$. Since there is a
finite number of periodic points, the open sets $B_{i}$ can be chosen small
enough so that, additionally, all the open sets

$\phi^{-t}(B_{i})\quad\mbox{for all $t\in\left\\{0,\ldots,n_{i}\right\\}$ and
$i\in\left\\{1,\ldots,P\right\\}$}$

are disjoint.

Now, given any of the distinct periodic points $m_{i}\in M$ on the list, we
show that $f_{(\phi,\omega,F)}$ for generic $\omega\in
C^{2}(M,\mathbb{R}^{N})$, that is, the set of observation maps $\omega$ for
which $f_{(\phi,\omega,F)}$ is an immersion at $m_{i}$ is open and dense in
$C^{2}(M,\mathbb{R}^{N})$. The openness is a consequence of the hypothesis on
the continuity of the map $\Theta_{(\phi,F)}$ and of an argument identical to
the beginning of the proof of part (iii) of Proposition 4.4.1. Regarding the
density, we show that if $f_{(\phi,\omega,F)}$ is not an immersion at $m_{i}$,
then there is a perturbation $\omega^{\prime}$ of $\omega$ in
$C^{2}(M,\mathbb{R})$ for which $f_{(\phi,\omega^{\prime},F)}$ is an immersion
at $m_{i}$. Indeed, set

$\omega^{\prime}=\omega+\sum_{l=0}^{n_{i}-1}\psi_{l}^{i}$ (4.9)

where $\psi_{l}^{i}\in C^{\infty}(M,\mathbb{R})$ are bump functions whose
supports are contained in $\phi^{-l}(B_{i})$ and, additionally, are chosen to
satisfy

$\displaystyle
D(\psi_{l}^{i}\circ\phi^{-l})(m_{i})=\varepsilon\mathbf{v}^{\top},\quad\mbox{$l\in\left\\{0,\ldots,n_{i}-1\right\\}$,}$

for some small constant $\varepsilon>0$ and $\mathbf{v}\in\mathbb{R}^{p}$ the
unique vector that solves the linear system

$\left(\begin{array}[]{c}\mathbf{v}_{1}^{\top}\\\ \vdots\\\
\mathbf{v}_{p}^{\top}\end{array}\right)\mathbf{v}=\left(\begin{array}[]{c}1\\\
\vdots\\\ 1\end{array}\right),$ (4.10)

with $\left\\{\mathbf{v}_{1},\ldots,\mathbf{v}_{p}\right\\}$ a basis of
eigenvectors of $T_{m_{i}}\phi^{-n_{i}}$. Note that by construction and for
any $l\in\left\\{0,\ldots,n_{i}-1\right\\}$,

$D(\omega^{\prime}\circ\phi^{-l})(m_{i})=D(\omega\circ\phi^{-l})(m_{i})+D(\psi_{l}^{i}\circ\phi^{-l})=D(\omega\circ\phi^{-l})(m_{i})+\varepsilon\mathbf{v}^{\top}.$
(4.11)

We now consider the vectors (4.8) in Lemma 4.4.4 with respect to the perturbed
observation map in (4.9). Indeed, by (4.11) and the way in which the vector
$\mathbf{v}$ has been constructed in (4.10):

$(I-\lambda_{j}A^{n_{i}})^{-1}\sum^{n_{i}-1}_{k=0}A^{k}CD(\omega^{\prime}\circ\phi^{-k})(m_{i})\mathbf{v}_{j}\\\
=(I-\lambda_{j}A^{n_{i}})^{-1}\sum^{n_{i}-1}_{k=0}A^{k}CD(\omega\circ\phi^{-k})(m_{i})\mathbf{v}_{j}+\varepsilon(I-\lambda_{j}A^{n_{i}})^{-1}\sum^{n_{i}-1}_{k=0}A^{k}C\mathbf{v}^{\top}\mathbf{v}_{j}\\\
=(I-\lambda_{j}A^{n_{i}})^{-1}\sum^{n_{i}-1}_{k=0}A^{k}CD(\omega\circ\phi^{-k})(m_{i})\mathbf{v}_{j}+\varepsilon(I-\lambda_{j}A^{n_{i}})^{-1}(I-A)^{-1}(I-A^{n_{i}})C.$

Given that when we vary $j\in\left\\{1,\ldots,p\right\\}$ in the previous
expression the vectors in the second summand form by hypothesis a linearly
independent set, we can use Lemma 4.4.5 to choose $\varepsilon>0$ so that the
family
$\left\\{(I-\lambda_{j}A^{n_{i}})^{-1}\sum^{n_{i}-1}_{k=0}A^{k}CD(\omega^{\prime}\circ\phi^{-k})(m_{i})\mathbf{v}_{j}\right\\}_{j\in\left\\{1,\ldots,p\right\\}}$
forms a linearly independent set and, at the same time, $\omega^{\prime}$ is
as close to $\omega$ in $C^{2}(M,\mathbb{R})$ as desired. This shows by Lemma
4.4.4 that $f_{(\phi,\omega^{\prime},F)}$ is an immersion at $m_{i}$.

The choice of the open sets $B_{i}$ implies that we can keep perturbing
$\omega$ in order to make $f_{(\phi,\omega^{\prime},F)}$ immersive at the
other periodic points without spoiling that condition for the previous ones.
This shows in particular that a perturbation of the type

$\omega^{\prime}=\omega+\sum_{i=1}^{P}\sum_{l=0}^{n_{i}-1}\psi_{l}^{i}$ (4.12)

can be constructed so that $f_{(\phi,\omega^{\prime},F)}$ is immersive at all
the periodic points of $\phi$, as required.

Before we continue, we will state the Immersion Theorem, which will be used
several times in the proofs that follow.

######  Theorem 4.4.6.

(mta, Immersion Theorem, Theorem 3.5.7) Let $M,M^{\prime}$ be smooth
manifolds, and $f\in C^{r}(M,M^{\prime})$ for $r\geq 1$. Then the following
are equivalent:

  * •

$f$ is an immersion at $m\in M$;

  * •

there is a neighbourhood $U$ of $m$ such that $f(U)$ is a submanifold of
$M^{\prime}$ and $f$ restricted to $U$ is a diffeomorphism of $U$ onto $f(U)$.

Step 2. Immersion at the remaining points. Having just proved that for generic
$\omega\in C^{2}(M,\mathbb{R}^{N})$ the generalized synchronization
$f_{(\phi,\omega,F)}\in C^{2}(M,\mathbb{R})$ is an immersion at the periodic
points of $\phi$, the Immersion Theorem (Theorem 4.4.6) guarantees that the
same holds for the open set formed by the union of certain open neighborhoods
around those points.

Now we let $\mathcal{M}\subset M$ be the compact subset of $M$ obtained by
removing that immersed open set. Our goal is now to show that
$f_{(\phi,\omega,F)}\in C^{2}(M,\mathbb{R})$ is also an immersion at
$\mathcal{M}$ for generic $\omega\in C^{2}(M,\mathbb{R}^{N})$.

The hypotheses that we imposed on $M$ in Chapter 3 imply that $M$ can be
endowed with a Riemannian metric which makes $M$ a complete metric space by
the Hopf and Rinow Theorem (see (boothby2003introduction, Theorem 7.7)). This
implies in turn that the compact subset ${\cal M}\subset M$ is also a complete
metric space which allows us to define open balls $B_{r}(m)$ of radius $r>0$
around each point $m\in{\cal M}$. Using this notation, in the next paragraphs
we show that for any $\omega\in C^{2}(M,\mathbb{R}^{N})$ and $m\in{\cal M}$ we
can find a $n(m)\in\mathbb{N}$ and a perturbation $\omega^{\prime}\in
C^{2}(M,\mathbb{R}^{N})$ as close to $\omega$ as desired such that the
restriction of $f_{(\phi,\omega^{\prime},F)}$ to $B_{2^{-n(m)}}(m)$ is an
immersion.

Indeed, take an arbitrary $m\in\mathcal{M}$ and define a collection of balls
$B_{2^{-n}}(m)$ centered at $m$ with radius $2^{-n}$, $n\in\mathbb{N}$. For a
fixed $n$ consider the infinite trajectory $\phi^{-t}(B_{2^{-n}}(m))$,
$t\in\mathbb{N}$. Choose now $n_{1}\in\mathbb{N}$ large enough so that, for
any $n>n_{1}$ the balls $\phi^{-t}(B_{2^{-n}}(m))$ are disjoint for
$t=0,\ldots,N-1$ and $B_{2^{-n}}(m)\subset U$ where $(U,h)$ is an admissible
chart of $M$. Given that $\phi\in{\rm Diff}^{2}(M)$, we note that the family
$(U_{t},h_{t})$, $t\in\mathbb{N}$, defined by $U_{t}=\phi^{-t}(U)$ and
$h_{t}:=h\circ\phi^{t}$ is made of admissible charts and that
$\phi^{-t}(B_{2^{-n}}(m))\subset U_{t}$, for all $n>n_{1}$. Let $T(n)$ denote
the largest integer such that $\phi^{-t}(B_{2^{-n}}(m))$ are disjoint for
$t=0,\ldots,T(n)-1$.

Now, for each $n>n_{1}$ and $t=0,\ldots,N-1$ we define functions $\psi_{tn}\in
C^{\infty}(M,\mathbb{R})$ that have their support included in
$\phi^{-t}(B_{2^{-n}}(m))$ and satisfy

$\frac{\partial(\psi_{tn}h_{t}^{-1})}{\partial u_{j}}=1$ (4.13)

on
$h_{t}\left(\phi^{-t}(B_{2^{-(n+1)}}(m))\right)=h\left(B_{2^{-(n+1)}}(m)\right)$.
We impose further that $\psi_{tn}=\psi_{t(n+1)}$ on
$\phi^{-t}(B_{2^{-(n+2)}}(m))$ for all $n>n_{1}$, and that there is some
$\kappa>0$ independent of $n$ and $t$ such that
$\lVert\psi_{tn}h_{t}^{-1}\rVert_{C^{1}}\leq\kappa$. These functions can be
constructed by setting

$\displaystyle\psi_{tn}(m)=\lambda_{tn}(m)\sum_{j=1}^{q}\xi_{j}(m)$

where $\xi_{j}$ is the $j$-th coordinate map for the chart $h_{t}$ and
$\lambda_{tn}\in C^{\infty}(M,\mathbb{R})$ are bump functions that have
support included in $\phi^{-t}(B_{2^{-n}}(m))$ and satisfy
$\lambda_{tn}|_{\phi^{-t}(B_{2^{-(n+1)}}(m))}=1$. Define now the perturbation
$\omega_{n}$ of $\omega$ by

$\displaystyle\omega_{n}=\omega+\sum_{t=0}^{N-1}\varepsilon_{t}\psi_{tn},$
(4.14)

where $\varepsilon_{t}$ are the components of a vector
$\boldsymbol{\varepsilon}\in\mathbb{R}^{N}$ with positive entries. By
construction, for any $m^{\prime}\in B_{2^{-n}}(m)$ and $t=0,\ldots,N-1$, we
have that

$\displaystyle\omega_{n}\phi^{-t}(m^{\prime})=\omega\phi^{-t}(m^{\prime})+\varepsilon_{t}\psi_{tn}(m^{\prime})$

and moreover by (4.13) and for any $m^{\prime}\in B_{2^{-(n+1)}}(m)$:

$\frac{\partial(\omega_{n}\phi^{-t}h^{-1})}{\partial
u_{j}}(h(m^{\prime}))=\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}(h(m^{\prime}))+\varepsilon_{t}.$ (4.15)

Let $\Phi:M\to\mathbb{R}^{N}$ be a backwards version of the Takens delay map,
that is,

$\displaystyle\Phi(m):=\left(\omega(m),\omega\circ\phi^{-1}(m),\ldots,\omega\circ\phi^{-(N-1)}(m)\right)^{\top},$

and let $\Phi_{n}:M\to\mathbb{R}^{N}$ be its perturbed version defined by

$\displaystyle\Phi_{n}(m):=\left(\omega_{n}(m),\omega_{n}\circ\phi^{-1}(m),\ldots,\omega_{n}\circ\phi^{-(N-1)}(m)\right)^{\top}.$

Using these objects, we can rewrite (4.15) in vector form as

$\frac{\partial(\Phi_{n}h^{-1})}{\partial
u_{j}}(h(m^{\prime}))=\frac{\partial(\Phi h^{-1})}{\partial
u_{j}}(h(m^{\prime}))+\boldsymbol{\varepsilon},$ (4.16)

for any $m^{\prime}\in B_{2^{-(n+1)}}(m)$ and where
$\boldsymbol{\varepsilon}\in\mathbb{R}^{N}$. Next, for any $t=N,\ldots,T(n)-1$
notice that

$\omega_{n}\phi^{-t}(m)=\omega\phi^{-t}(m).$ (4.17)

Finally, if $t\geq T(n)$ then

$\omega_{n}\phi^{-t}(m)=\omega\phi^{-t}(m)+\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\psi_{\tau
n}\phi^{-t}(m).$ (4.18)

We now consider the perturbed generalized synchronization
$f_{(\phi,\omega_{n},F)}:M\to\mathbb{R}^{N}$ given by

$\displaystyle f_{(\phi,\omega_{n},F)}$
$\displaystyle=\sum_{t=0}^{\infty}A^{t}C\omega_{n}\phi^{-t}=\sum_{t=0}^{N-1}A^{t}C\omega_{n}\phi^{-t}+\sum_{t=N}^{\infty}A^{t}C\omega_{n}\phi^{-t}=Q\Phi_{n}+\sum_{t=N}^{\infty}A^{t}C\omega_{n}\phi^{-t}$

where $Q$ is the $N\times N$ real matrix with $(t+1)$-th column $A^{t}C$. Now
we take the partial derivatives with respect to $u_{j}$ at points in
$h(B_{2^{-(n+1)}}(m))$ and observe that by (4.16), (4.17), and (4.18):

$\displaystyle\ \ \frac{\partial(f_{(\phi,\omega_{n},F)}h^{-1})}{\partial
u_{j}}$ $\displaystyle=Q\frac{\partial(\Phi_{n}h^{-1})}{\partial
u_{j}}+\sum_{t=N}^{\infty}A^{t}C\frac{\partial(\omega_{n}\phi^{-t}h^{-1})}{\partial
u_{j}}$ $\displaystyle=Q\frac{\partial(\Phi h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{\infty}_{t=N}A^{t}C\frac{\partial(\omega_{n}\phi^{-t}h^{-1})}{\partial
u_{j}}$ $\displaystyle=Q\frac{\partial(\Phi h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{T(n)-1}_{t=N}A^{t}C\frac{\partial(\omega_{n}\phi^{-t}h^{-1})}{\partial
u_{j}}+\sum^{\infty}_{t=T(n)}A^{t}C\frac{\partial(\omega_{n}\phi^{-t}h^{-1})}{\partial
u_{j}}$ $\displaystyle=Q\frac{\partial(\Phi h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{T(n)-1}_{t=N}A^{t}C\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}+\sum^{\infty}_{t=T(n)}A^{t}C\frac{\partial(\omega_{n}\phi^{-t}h^{-1})}{\partial
u_{j}}$ $\displaystyle=Q\frac{\partial(\Phi h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{T(n)-1}_{t=N}A^{t}C\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}+\sum^{\infty}_{t=T(n)}A^{t}C\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}$
$\displaystyle+\sum^{\infty}_{t=T(n)}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial u_{j}}\bigg{)}$
$\displaystyle=Q\frac{\partial(\Phi h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{\infty}_{t=N}A^{t}C\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}+\sum^{\infty}_{t=T(n)}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial u_{j}}\bigg{)}$
$\displaystyle=\sum_{t=0}^{N-1}A^{t}C\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{\infty}_{t=N}A^{t}C\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}+\sum^{\infty}_{t=T(n)}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial u_{j}}\bigg{)}$
$\displaystyle=\sum_{t=0}^{\infty}A^{t}C\frac{\partial(\omega\phi^{-t}h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{\infty}_{t=T(n)}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial u_{j}}\bigg{)}$
$\displaystyle=\frac{\partial(f_{(\phi,\omega,F)}h^{-1})}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{\infty}_{t=T(n)}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial u_{j}}\bigg{)}.$ (4.19)

In order to prove that $f_{(\phi,\omega,F)}$ is an immersion at the points in
$h(B_{2^{-(n+1)}}(m))$ for a generic observation $\omega$, we shall find an
arbitrarily small vector $\boldsymbol{\varepsilon}$ for which the vectors
corresponding to the $\boldsymbol{\varepsilon}$-perturbed observation
$\omega_{n}$

$\displaystyle\left\\{\frac{\partial\left(f_{(\phi,\omega_{n},F)}h^{-1}\right)}{\partial
u_{j}}\right\\}_{j\in\left\\{1,\ldots,q\right\\}}$

are a linearly independent family. We will proceed inductively by showing that
if we assume for some $s$ satisfying $1\leq s<q$ that the vectors

$\displaystyle\left\\{\frac{\partial\left(f_{(\phi,\omega,F)}h^{-1}\right)}{\partial
u_{j}}\right\\}_{j\in\left\\{1,\ldots,s\right\\}}$ (4.20)

are linearly independent, then we can choose an arbitrarily small vector
$\boldsymbol{\varepsilon}$ such that the family corresponding to the perturbed
observation $\omega_{n}$ defined in (4.14) satisfies that

$\displaystyle\left\\{\frac{\partial\left(f_{(\phi,\omega_{n},F)}h^{-1}\right)}{\partial
u_{j}}\right\\}_{j\in\left\\{1,\ldots,s+1\right\\}}$

is a linearly independent family. To this end, we define the map
$\Psi:\mathbb{R}^{s}\times h(U)\to\mathbb{R}^{N}$ as

$\displaystyle\Psi(\boldsymbol{\alpha},{\bf
u})=\sum^{s}_{j=1}\alpha_{j}\frac{\partial\left(f_{(\phi,\omega,F)}h^{-1}\right)}{\partial
u_{j}}-\frac{\partial\left(f_{(\phi,\omega,F)}h^{-1}\right)}{\partial
u_{s+1}}.$

The hypothesis on the statement of the theorem about $f_{(\phi,\omega,F)}\in
C^{2}(M,\mathbb{R}^{N})$ for any observation map $\omega\in
C^{2}(M,\mathbb{R})$ implies that $\Psi$ is of class $C^{1}$ and maps a
manifold of dimension $s+q$ to a manifold of dimension $N$. Since by
hypothesis $s+q<2q\leq N$, then the set
$\mathbb{R}^{N}\setminus\Psi(\mathbb{R}^{s}\times h(U))$ is dense in
$\mathbb{R}^{N}$ (see (Hirsch:book, Chapter 3, Proposition 1.2)). This implies
that we can choose an arbitrarily small vector
$\boldsymbol{\delta}\in\bigg{(}\mathbb{R}^{N}\setminus\Psi(\mathbb{R}^{s}\times
h(U))\bigg{)}$ such that if we set
$\boldsymbol{\varepsilon}:=Q^{-1}\boldsymbol{\delta}$ then we have that the
vector

$\displaystyle\frac{\partial(f_{(\phi,\omega,F)}h^{-1})}{\partial
u_{s+1}}+Q\boldsymbol{\varepsilon}$

is independent of the vectors in (4.20) when evaluated at any point in $h(U)$.
Since the linear independence is stable under small perturbations we can
choose $\boldsymbol{\varepsilon}$ small enough so that it is actually the
family

$\displaystyle\left\\{\frac{\partial\left(f_{(\phi,\omega,F)}h^{-1}\right)}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}\right\\}_{j\in\left\\{1,\ldots,s+1\right\\}}$

that is linearly independent. Now, in view of the identity (4.19) we note that
the value $n\in\mathbb{N}$ can be chosen large enough so that the residual
terms

$\displaystyle\sum^{\infty}_{t=T(n)}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial
u_{j}}\bigg{)},\quad\mbox{$j\in\left\\{1,\ldots,s+1\right\\}$,}$

are small enough so that the family

$\displaystyle\left\\{\frac{\partial\left(f_{(\phi,\omega,F)}h^{-1}\right)}{\partial
u_{j}}+Q\boldsymbol{\varepsilon}+\sum^{\infty}_{t=T(n)}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial
u_{j}}\bigg{)}\right\\}_{j\in\left\\{1,\ldots,s+1\right\\}}$ $\displaystyle=$
$\displaystyle\left\\{\frac{\partial\left(f_{(\phi,\omega_{n},F)}h^{-1}\right)}{\partial
u_{j}}\right\\}_{j\in\left\\{1,\ldots,s+1\right\\}}$

is linearly independent, as required. Notice that this equality is a
consequence of (4.19). The possibility to shrink the residual term comes from
the convergence of the series

$\displaystyle\sum^{\infty}_{t=0}A^{t}C\bigg{(}\sum^{N-1}_{\tau=0}\varepsilon_{\tau}\frac{\partial(\psi_{\tau
n}\phi^{-t}h^{-1})}{\partial
u_{j}}\bigg{)},\quad\mbox{$j\in\left\\{1,\ldots,s+1\right\\}$,}$

which is guaranteed by the hypothesis on the differentiability of
$f_{(\phi,\omega,F)}$ for any observation map $\omega\in C^{2}(M,\mathbb{R})$
and the expression (4.1). In this case the bump functions play the role of the
observations for which we assumed the existence of a uniform bound $\kappa$
over $\tau$ and $n$ such that $\lVert\psi_{\tau n}\rVert_{C^{1}}<\kappa$.

If we recursively apply this procedure, we can conclude the existence of a
small perturbation $\omega_{n}$ of $\omega$ obtained as a sequence of
perturbations of the type (4.14) for which the family

$\left\\{\frac{\partial\left(f_{(\phi,\omega_{n},F)}h^{-1}\right)}{\partial
u_{j}}\right\\}_{j\in\left\\{1,\ldots,q\right\\}}$

is linearly independent when evaluated at $m\in{\cal M}$, which proves that
$f_{(\phi,\omega_{n},F)}\in C^{2}(M,\mathbb{R}^{N})$ is an immersion at
$m\in{\cal M}$.

Finally, observe that we just showed that for any $m\in\mathcal{M}$, there
exists an $n(m)\in\mathbb{N}$ such that the restriction of the perturbation
$f_{(\phi,\omega_{n(m)},F)}$ to $B_{2^{-n(m)}}(m)$ is an immersion. We note
that the union

$\displaystyle\bigcup_{m\in\mathcal{M}}B_{2^{-n}}(m)$

is clearly an open cover of $\mathcal{M}$. Since $\mathcal{M}$ is compact, it
admits a finite subcover. The finite subcover comprises sets for which, one at
a time, we can construct an immersion using the procedure described earlier in
this proof. For each set, we ensure that the perturbation is sufficiently
small not to spoil the immersion on any other set.

This argument completes the proof of the immersion of the GS at the points of
$\mathcal{M}$ and therefore, together with the Step 1, shows that there exists
a small perturbation of $f_{(\phi,\omega_{n},F)}\in C^{2}(M,\mathbb{R}^{N})$
of $f_{(\phi,\omega,F)}$ that is an immersion at all the points in $M$, as
required. ∎

####  4.4.3 Embedding GS

Now that we have established immersivity, we can complete the proof of Theorem
4.2.1 by establishing injectivity.

###### Proof.

As in the previous theorem, we proceed in two steps.

Step 1. Injectivity around the periodic set. We start by showing that the
observations corresponding to the globally immersive generalized
synchronizations whose existence we proved in Theorem 4.4.2 can be slightly
perturbed in $C^{2}(M,\mathbb{R})$ so that the resulting GS is injective in an
open subset $V_{P}$ that includes all the periodic points of $\phi$. We start
this part of the discussion with a preparatory lemma.

######  Lemma 4.4.7.

In the hypotheses of the theorem, let $m_{1},\ldots,m_{P}\in M$ be the
distinct periodic points of $\phi$, each of which have periods
$n_{1},\ldots,n_{P}\in\mathbb{N}$, respectively. Let $\ell\in\mathbb{N}$ be
the lowest common multiple of all the periods and denote by $M_{P}$ the set of
all periodic points of $\phi$ (that is, the set that comprises
$\left\\{m_{1},\ldots,m_{P}\right\\}$ and all the corresponding orbits). Then,
the restriction $\left.f_{(\phi,\omega,F)}\right|_{M_{P}}$ of a generalized
synchronization $f_{(\phi,\omega,F)}\in C^{2}(M,\mathbb{R}^{N})$ to $M_{P}$ is
injective if and only if the map $g_{(\phi,\omega,F)}:M_{P}\to\mathbb{R}^{N}$
defined by

$\displaystyle
g_{(\phi,\omega,F)}=\sum_{k=0}^{\ell-1}A^{k}C\left(\omega\circ\phi^{-k}\right)$

is injective.

###### Proof.

Let $m_{1},m_{2}\in M_{P}$ be such that
$f_{(\phi,\omega,F)}(m_{1})=f_{(\phi,\omega,F)}(m_{2})$. This equality is
equivalent to the following expressions:

$\displaystyle\sum_{t=0}^{\infty}A^{t}C\omega\phi^{-t}(m_{1})$
$\displaystyle=\sum_{t=0}^{\infty}A^{t}C\omega\phi^{-t}(m_{2}),$
$\displaystyle\sum_{t=0}^{\infty}\sum_{k=0}^{\ell-1}A^{t\ell+k}C\omega\phi^{-(t\ell+k)}(m_{1})$
$\displaystyle=\sum_{t=0}^{\infty}\sum_{k=0}^{\ell-1}A^{t\ell+k}C\omega\phi^{-(t\ell+k)}(m_{2}),$
$\displaystyle\sum_{t=0}^{\infty}(A^{\ell})^{t}\sum_{k=0}^{\ell-1}A^{k}C\omega\phi^{-k}(m_{1})$
$\displaystyle=\sum_{t=0}^{\infty}(A^{\ell})^{t}\sum_{k=0}^{\ell-1}A^{k}C\omega\phi^{-k}(m_{2}).$

Given that $\rho(A)<1$ then $\rho(A^{\ell})<1$ necessarily and hence this
equality can be rewritten as

$(I-A^{\ell})^{-1}\sum_{k=0}^{\ell-1}A^{k}C\omega\phi^{-k}(m_{1})=(I-A^{\ell})^{-1}\sum_{k=0}^{\ell-1}A^{k}C\omega\phi^{-k}(m_{2}),$

which is equivalent to
$\sum_{k=0}^{\ell-1}A^{k}C\omega\phi^{-k}(m_{1})=\sum_{k=0}^{\ell-1}A^{k}C\omega\phi^{-k}(m_{2})$
and hence, by definition, to
$g_{(\phi,\omega,F)}(m_{1})=g_{(\phi,\omega,F)}(m_{2})$, which proves the
statement. ∎

If we now define $\Phi_{(\ell,\omega)}:M\to\mathbb{R}^{l}$ as

$\displaystyle\Phi_{(\ell,\omega)}(m):=\left(\omega(m),\omega\circ\phi^{-1}(m),\ldots,\omega\circ\phi^{-(\ell-1)}(m)\right)^{\top},$

we note that the map $g_{(\phi,\omega,F)}$ can be rewritten as
$g_{(\phi,\omega,F)}=Q\Phi_{(\ell,\omega)}$, where $Q\in\mathbb{M}_{N,\ell}$
is a matrix whose $(k+1)$th-column is set to the vector $A^{k}C$. The
hypotheses on the vectors
$\left\\{A^{j}C\right\\}_{j\in\left\\{0,1,\ldots,N-1\right\\}}$ forming a
linearly independent set and that $N>\ell$ guarantee that ${\rm rank}\,Q=N$
and hence that the associated linear map
$Q:\mathbb{R}^{\ell}\to\mathbb{R}^{N}$ is injective. With this notation we now
show that if $g_{(\phi,\omega,F)}$ is not injective in $M_{P}$ then a
perturbation $\omega^{\prime}\in C^{2}(M,\mathbb{R}^{N})$ of $\omega$ can be
chosen so that $g_{(\phi,\omega^{\prime},F)}$ is. More specifically, define

$\omega^{\prime}:=\omega+\sum_{i=1}^{P}\sum_{j=1}^{n_{i}}\varepsilon_{ij}\Psi_{ij},$
(4.21)

where $\Psi_{ij}$ are bump functions with non-intersecting supports $U_{ij}$
such that $m_{ij}:=\phi^{-(j-1)}(m_{i})\in U_{ij}$ and, moreover,
$\Psi_{ij}\left(\phi^{-(j-1)}(m_{i})\right)=\Psi_{ij}(m_{ij})=1/\mathcal{L}(i,j)$.
The symbol $\mathcal{L}(i,j)\in\mathbb{N}$ denotes the ordinal of the pair
$(i,j)$ in lexicographic order.

We now show that the constants $\varepsilon_{ij}$ can be chosen so that
$\omega^{\prime}$ is as close as we want to $\omega$ and, at the same time,
$g_{(\phi,\omega^{\prime},F)}$ is injective. Firstly, it is easy to see that,
by construction,

$\displaystyle\Phi_{(\ell,\omega^{\prime})}(m):=\Phi_{(\ell,\omega)}(m)+\sum_{i=1}^{P}\sum_{j=1}^{n_{i}}\varepsilon_{ij}\left(\Psi_{ij}(m),\Psi_{ij}\circ\phi^{-1}(m),\ldots,\Psi_{ij}\circ\phi^{-(\ell-1)}(m)\right)^{\top}.$

Second, if $m_{i_{1}j_{1}}$ and $m_{i_{2}j_{2}}$ are two different periodic
points then

$g_{(\phi,\omega^{\prime},F)}(m_{i_{1}j_{1}})-g_{(\phi,\omega^{\prime},F)}(m_{i_{2}j_{2}})=g_{(\phi,\omega,F)}(m_{i_{1}j_{1}})-g_{(\phi,\omega,F)}(m_{i_{2}j_{2}})+Q\left(\varepsilon_{i_{1}j_{1}}\mathbf{v}_{i_{1}j_{1}}-\varepsilon_{i_{2}j_{2}}\mathbf{v}_{i_{2}j_{2}}\right),$
(4.22)

where the vectors $\mathbf{v}_{i_{1}j_{1}}\in\mathbb{R}^{{\rm Card}M_{P}}$
have entries equal to zero except at the slots that are multiples of the
period of the corresponding periodic point. More specifically, if the periodic
point $m_{ij}$ has period $n_{ij}$, then

$(\mathbf{v}_{ij})_{i}:=\left\\{\begin{array}[]{l}1/\mathcal{L}(i,j)\quad\mbox{when
$i=1$ or $i-1$ is a multiple of $n_{ij}$,}\\\
0\quad\mbox{otherwise.}\end{array}\right.$ (4.23)

Using the injectivity of $Q$ and Lemma 4.4.7, we now show that we can choose
the perturbation constants $\varepsilon_{ij}$ so that the restriction of
$g_{(\phi,\omega^{\prime},F)}$ to $M_{P}$ is injective. Let

$\varepsilon_{ij}:=\epsilon\|g_{(\phi,\omega,F)}(m_{ij})\|,\quad\mbox{for some
constant $\epsilon>0$.}$ (4.24)

We now show that if $\epsilon>0$ is chosen so that

$\epsilon\max_{(i_{1},j_{1}),(i_{2},j_{2})}\left\\{\left\|Q\left(\left\|g_{(\phi,\omega,F)}(m_{i_{1}j_{1})}\right\|\mathbf{v}_{i_{1}j_{1}}-\left\|g_{(\phi,\omega,F)}(m_{i_{2}j_{2}})\right\|\mathbf{v}_{i_{2}j_{2}}\right)\right\|\right\\}\\\
<\min_{(i_{1},j_{1}),(i_{2},j_{2})}\left\\{\left\|g_{(\phi,\omega,F)}(m_{i_{1}j_{1}})-g_{(\phi,\omega,F)}(m_{i_{2}j_{2}})\right\|\right\\}$
(4.25)

then the injectivity of $g_{(\phi,\omega^{\prime},F)}\mid_{M_{P}}$ is
guaranteed. Indeed, consider first the case of two distinct periodic points
$m_{i_{1}j_{1}}$ and $m_{i_{2}j_{2}}$ for which $g_{(\phi,\omega,F)}$ fails to
be injective, that is,
$g_{(\phi,\omega,F)}(m_{i_{1}j_{1}})=g_{(\phi,\omega,F)}(m_{i_{2}j_{2}})$. In
that case, by (4.22) and (4.24) we have that

$g_{(\phi,\omega^{\prime},F)}(m_{i_{1}j_{1}})-g_{(\phi,\omega^{\prime},F)}(m_{i_{2}j_{2}})=\epsilon\left\|g_{(\phi,\omega,F)}(m_{i_{1}j_{1}})\right\|Q\left(\mathbf{v}_{i_{1}j_{1}}-\mathbf{v}_{i_{2}j_{2}}\right).$
(4.26)

Given that $\mathbf{v}_{i_{1}j_{1}}-\mathbf{v}_{i_{2}j_{2}}\neq{\bf 0}$
(notice, for instance, that
$\left(\mathbf{v}_{i_{1}j_{1}}-\mathbf{v}_{i_{2}j_{2}}\right)_{1}=1/\mathcal{L}(i_{1},j_{1})-1/\mathcal{L}(i_{2},j_{2})\neq
0$) and $Q$ is injective then
$Q\left(\mathbf{v}_{i_{1}j_{1}}-\mathbf{v}_{i_{2}j_{2}}\right)\neq{\bf 0}$ and
hence $g_{(\phi,\omega^{\prime},F)}(m_{i_{1}j_{1}})\neq
g_{(\phi,\omega^{\prime},F)}(m_{i_{2}j_{2}})$ necessarily by (4.26). In the
case $g_{(\phi,\omega,F)}(m_{i_{1}j_{1}})\neq
g_{(\phi,\omega,F)}(m_{i_{2}j_{2}})$ the same conclusion can be drawn because
the choice of $\epsilon>0$ in (4.25) guarantees that

$\left\|Q\left(\varepsilon_{i_{1}j_{1}}\mathbf{v}_{i_{1}j_{1}}-\varepsilon_{i_{2}j_{2}}\mathbf{v}_{i_{2}j_{2}}\right)\right\|<\left\|g_{(\phi,\omega,F)}(m_{i_{1}j_{1}})-g_{(\phi,\omega,F)}(m_{i_{2}j_{2}})\right\|$

which by (4.22) ensures that, again,
$g_{(\phi,\omega^{\prime},F)}(m_{i_{1}j_{1}})\neq
g_{(\phi,\omega^{\prime},F)}(m_{i_{2}j_{2}})$, as required.

We now show that if $\left.f_{(\phi,\omega,F)}\right|_{M_{P}}$ is injective
then there exists an open set $V_{P}$ such that $M_{P}\subset V_{P}$ and
$\left.f_{(\phi,\omega,F)}\right|_{\overline{V_{P}}}$ is also injective. By
the Immersion Theorem, we know that there exists $n\in\mathbb{N}$ such that
the balls $B_{2^{-n}}(m_{ij})$ do not intersect and that the restriction of
$f_{(\phi,\omega,F)}$ to each of them is a collection of injective maps. It
could still be, however, that the images of different balls intersect. The
continuity of $f_{(\phi,\omega,F)}$ and the fact that
$\left.f_{(\phi,\omega,F)}\right|_{M_{P}}$ is injective implies that $n$ can
be chosen sufficiently large so that this does not happen. Indeed, if this was
not the case for the balls around the periodic points, say, $m_{i_{1}j_{1}}$
and $m_{i_{2}j_{2}}$, then it would be possible to construct two sequences
$\\{m_{i_{1}j_{1},l}\\}_{l\in\mathbb{N}}$ and
$\\{m_{i_{2}j_{2},l}\\}_{l\in\mathbb{N}}$ with limits $m_{i_{1}j_{1}}$ and
$m_{i_{2}j_{2}}$ for which
$f_{(\phi,\omega,F)}(m_{i_{1}j_{1},l})=f_{(\phi,\omega,F)}(m_{i_{2}j_{2},l})$
for each $l\in\mathbb{N}$. By continuity this implies that
$f_{(\phi,\omega,F)}(m_{i_{1}j_{1}})=f_{(\phi,\omega,F)}(m_{i_{2}j_{2}})$
which is in contradiction with the injectivity of
$\left.f_{(\phi,\omega,F)}\right|_{M_{P}}$ and hence proves the injectivity of
$f_{(\phi,\omega,F)}$ restricted to $V_{P}=\bigcup_{ij}B_{2^{-n}}(m_{ij})$,
with $n$ chosen so that the properties of the corresponding balls designed
above are satisfied. Notice that by doubling $n$, if necessary, it is also
easy to ensure the injectivity of
$\left.f_{(\phi,\omega,F)}\right|_{\overline{V_{P}}}$.

Step 2: Global injectivity. This final step is quite involved and appeals to
several results in differential topology. We will state the results here:

######  Lemma 4.4.8.

If $M$ is a compact differentiable manifold endowed with a metric $d$ and
$f:M\to\mathbb{R}^{N}$ is an immersion, then there exists a constant $r>0$
such that for any $m\in M$ the restriction $f\rvert_{B_{r}(m)}$ of $f$ to the
open ball $B_{r}(m)\subset M$ of radius $r$ and center $m$ is injective.

###### Proof.

The Immersion Theorem ((mta, Theorem 3.5.7)) implies that each $m\in M$ has an
open neighborhood $U_{m}\subset M$ such that $f\rvert_{U_{m}}$ is injective.
The collection of sets $\\{U_{m}\\}_{m\in M}$ forms an open cover of $M$.
Then, by Lebesgue’s number lemma (Munkres:topology, Lemma 27.5), there exists
a $\delta>0$ such that every set of diameter $\delta$ is contained in some set
in the family $\\{U_{m}\\}_{m\in M}$. The lemma is proved by choosing
$r=\delta/2$. ∎

######  Definition 4.4.9.

(mta, Regular Value, Definition 3.5.3) Suppose $M$ and $M$ are smooth
manifolds and $f\in C^{r}(M,M^{\prime})$ for $r\geq 1$. A point $m^{\prime}\in
M^{\prime}$ is called a _regular value_ of $f$ if for each $m\in
f^{-1}\\{m^{\prime}\\}$, the tangent map $T_{m}f$ is surjective with split
kernel.

######  Theorem 4.4.10.

(mta, Submersion Theorem, Theorem 3.5.4) Let $M,M^{\prime}$ be smooth
manifolds and $f\in C^{\infty}(M,M^{\prime})$. Let $m^{\prime}$ be a regular
value. Then the level set

$\displaystyle f^{-1}(m^{\prime})=\\{m\in M\ |\ f(m)=m^{\prime}\\}$

is a closed submanifold of $M$.

######  Theorem 4.4.11.

(Hirsch:book, Chapter 3, Proposition 1.2) Let $M,M^{\prime}$ be smooth
manifolds with $\text{dim(M)}<\text{dim}(M^{\prime})$. If $f\in
C^{1}(M,M^{\prime})$ then $M^{\prime}\backslash f(M)$ is dense in
$M^{\prime}$.

We are now ready to prove global injectivity, and complete the proof. Since
$M$ is compact and $f_{(\phi,\omega,F)}:M\to\mathbb{R}^{N}$ is an immersion,
Lemma 4.4.8 implies the existence of a constant $r>0$ such that for any $m\in
M$ the restriction $f_{(\phi,\omega,F)}\rvert_{B_{r}(m)}$ of
$f_{(\phi,\omega,F)}$ to the open ball $B_{r}(m)$ is injective. We now define
the set $W\subset M\times M$ as follows using the open set $V_{P}$ whose
existence we proved in Step 1.

$W:=\\{(m_{1},m_{2})\in(M\times M)\setminus(V_{P}\times V_{P})\mid\
d(m_{1},m_{2})\geq r\\}.$

The set $W$ comprises pairs $(m_{1},m_{2})\in M$ whose entries satisfy one of
two conditions:

  1. 1.

Neither $m_{1}$ nor $m_{2}$ are in $V_{P}$.

  2. 2.

One of $m_{1}$ and $m_{2}$ is in $V_{P}$ and the other is not.

In view of this, the injectivity of $f_{(\phi,\omega,F)}\rvert_{V_{P}}$ proved
in the Step 1 together with Lemma 4.4.8 imply that if we show that
$f_{(\phi,\omega,F)}(m_{1})\neq f_{(\phi,\omega,F)}(m_{2})$ for all
$(m_{1},m_{2})\in W$ then $f_{(\phi,\omega,F)}$ is globally injective and the
proof is concluded.

We start the proof of this fact by first defining, for each $m\in M$, a
collection of nested balls $\\{B_{2^{-n}}(m)\mid n\in\mathbb{N}\\}$ centered
at $m$ with radius $2^{-n}$. Let $(m_{1},m_{2})\in W$, and assume from now on
without loss of generality that $m_{1}\in W\setminus V_{p}$. Let
$T(n,m_{1},m_{2})$ denote the largest integer such that the following two
properties hold. Firstly, the sets

$\displaystyle\\{B_{2^{-n}}(\phi^{-t}(m_{1}))\\}_{t=0,\ldots,T(n,m_{1},m_{2})-1}$

are disjoint and secondly

$\displaystyle B_{2^{-n}}(\phi^{-t}(m_{1}))\cap
B_{2^{-n}}(\phi^{-s}(m_{2}))=\emptyset\quad\mbox{for all}\quad
t,s\in\\{0,\ldots,T(n,m_{1},m_{2})-1\\}.$

Notice now that by the continuity of $\phi$, for each $n\in\mathbb{N}$ and
pair $(m_{1},m_{2})\in W$ there is an open neighbourhood
$U_{(m_{1},m_{2})}\subset M\times M$ of $(m_{1},m_{2})$ such that
$T(n,m_{1}^{\prime},m_{2}^{\prime})=T(n,m_{1}^{\prime\prime},m_{2}^{\prime\prime})$
for all
$(m_{1}^{\prime},m_{2}^{\prime}),(m_{1}^{\prime\prime},m_{2}^{\prime\prime})\in
U_{(m_{1},m_{2})}$. The collection $\\{U_{(m_{1},m_{2})}\ |\ (m_{1},m_{2})\in
W\\}$ covers $W$ and since it is a compact set we can extract a finite
subcover $\\{U_{a}\ |\ a\in\mathcal{A}\\}$, where $\mathcal{A}$ is a finite
set. Then we can choose one pair $(m_{1}^{a},m_{2}^{a})\in U_{a}$ for each
$a\in\mathcal{A}$ and notice that

$\displaystyle\min_{(m_{1},m_{2})\in
W}\\{T(n,m_{1},m_{2})\\}=\min_{\\{(m_{1}^{a},m_{2}^{a})\ |\ a\in
A\\}}\\{T(n,m_{1}^{a},m_{2}^{a})\\}.$

The importance of this equality is that, since $\mathcal{A}$ is a finite set,
the minimum on the right hand side is realized by a pair
$(m_{1}^{*},m_{2}^{*})\in W$. Let
$T(n)=T(n,m_{1}^{*},m_{2}^{*})=\min_{(m_{1},m_{2})\in W}T(n,m_{1},m_{2})$.
Observe that as $n\to\infty$ the families
$\\{B_{2^{-n}}(\phi^{-t}(m_{1}^{*}))\\}_{t\in\mathbb{N}}$ and
$\\{B_{2^{-n}}(\phi^{-t}(m_{2}^{*}))\\}_{t\in\mathbb{N}}$ converge to
$\\{\phi^{-t}(m_{1}^{*})\\}_{t\in\mathbb{N}}$ and
$\\{\phi^{-t}(m_{2}^{*})\\}_{t\in\mathbb{N}}$ respectively. The point
$m_{1}^{*}$ is not periodic so the infinite orbit
$\\{\phi^{-t}(m_{1}^{*})\\}_{t\in\mathbb{N}}$ of singletons is disjoint, and
furthermore does not intersect any point in
$\\{\phi^{-t}(m_{2}^{*})\\}_{t\in\mathbb{N}}$. This allows us to conclude that
$T(n)\to\infty$ as $n\to\infty$.

The fact that we just proved guarantees the existence of a $\nu\in\mathbb{N}$
such that $T(\nu)=N$. Thus for all pairs $(m_{1},m_{2})\in W$, the collection

$\displaystyle\\{B_{2^{-\nu}}(\phi^{-t}(m_{1}))\\}_{t=0,\ldots,N-1}$

is disjoint and

$\displaystyle B_{2^{-n}}(\phi^{-t}(m_{1}))\cap
B_{2^{-n}}(\phi^{-s}(m_{2}))=\emptyset\quad\mbox{for all}\quad
t,s\in\\{0,\ldots,N-1\\}.$

Now for any $n>\nu$ the collection

$\displaystyle\mathcal{C}_{n}=\\{B_{2^{-(n+1)}}(m)\ |\ m\in M\\}$

forms on open cover of $M$ from which we can extract a finite subcover
$\\{B_{i}\ |\ i\in J_{n}\\}$ for $J$ a finite set with cardinality
$\ell(n)\in\mathbb{N}$. Now define a partition of unity $\\{\lambda_{i}\ |\
i\in J_{n}\\}$ subordinate to $\\{B_{i}\ |\ i\in J_{n}\\}$. We impose on this
partition of unity the special property that for each $m\in M$ there exists an
$i\in J_{n}$ such that $\lambda_{i}(m)\geq 1/2$. Now we define the perturbed
observation function

$\displaystyle\omega_{n}=\omega+\sum^{\ell(n)}_{i=1}\epsilon_{i}\lambda_{i}$

where $\epsilon_{i}\in\mathbb{R}$ is the $i$th component of a vector
$\boldsymbol{\epsilon}\in\mathbb{R}^{\ell(n)}$ with positive entries. Then we
define $\Psi_{n}:M\times M\times\mathbb{R}^{\ell(n)}\to\mathbb{R}^{N}$ by

$\Psi_{n}(m_{1},m_{2},\epsilon)=f_{(\phi,\omega_{n},F)}(m_{1})-f_{(\phi,\omega_{n},F)}(m_{2}).$
(4.27)

Let $\Delta=\\{(m,m)\in M\times M\mid m\in M\\}$ be the diagonal set. Given an
arbitrary open neighborhood $\mathcal{N}\subset C^{1}(M,\mathbb{R})$ of the
observation function $\omega\in C^{2}(M,\mathbb{R})$ our goal is to find
$\boldsymbol{\epsilon}\in\mathbb{R}^{\ell(n)}$ such that
$\omega_{n}\in\mathcal{N}$ and that for all $(m_{1},m_{2})\in(M\times
M)\setminus\Delta$ we have that
$\Psi_{n}(m_{1},m_{2},\boldsymbol{\epsilon})\neq{\bf 0}$.

First of all, we observe that for any pair $(m_{1},m_{2})\in(M\times
M)\setminus W$ either $d(m_{1},m_{2})<r$ or both $m_{1},m_{2}\in V_{P}$. In
the former case, $\Psi_{n}(m_{1},m_{2},{\bf 0})\neq{\bf 0}$ unless
$(m_{1},m_{2})\in\Delta$ by Lemma 4.4.8, and in the latter case,
$\Psi_{n}(m_{1},m_{2},{\bf 0})\neq{\bf 0}$ unless $(m_{1},m_{2})\in\Delta$
because $f_{(\phi,\omega,F)}\rvert_{V_{P}}$ is injective by the Step 1. Now
$\Psi_{n}$ is continuous so there is an open neighbourhood $U_{{\bf
0}}\subset\mathbb{R}^{\ell(n)}$ of ${\bf 0}\in\mathbb{R}^{\ell(n)}$ such that
for all $\boldsymbol{\epsilon}\in U_{{\bf 0}}$ we have
$\Psi_{n}(m_{1},m_{2},\boldsymbol{\epsilon})\neq{\bf 0}$ for all
$(m_{1},m_{2})\in(M\times M)\setminus W$ unless $(m_{1},m_{2})\in\Delta$. So
all that remains is to find $\boldsymbol{\epsilon}\in U_{{\bf
0}}\subset\mathbb{R}^{\ell(n)}$ such that
$\Psi_{n}(m_{1},m_{2},\boldsymbol{\epsilon})\neq 0$ for all $(m_{1},m_{2})\in
W$.

We start by noting that if ${\bf 0}\in\mathbb{R}^{N}$ is not in the image of
$\Psi_{n}\rvert_{W\times\\{{\bf 0}\\}}$ then we are done so we shall assume
the opposite. In that case we proceed by showing that
$\Psi_{n}\rvert_{W\times\\{{\bf 0}\\}}$ is a submersion. If that is the case,
then for some open set $X\subset(M\times M\times\mathbb{R}^{\ell(n)})$
containing $W\times\\{{\bf 0}\\}$ then the restriction $\Psi_{n}\rvert_{X}$ is
also a submersion. Then by the Submersion Theorem 4.4.10 the inverse image
$\Psi_{n}\lvert_{X}^{-1}\left({\bf 0}\right)$ is a closed submanifold of
dimension $2q+\ell(n)-N$ of the open submanifold $X\subset M\times
M\times\mathbb{R}^{\ell}$.

Moreover if $\pi:M\times M\times\mathbb{R}^{\ell(n)}\to\mathbb{R}^{\ell(n)}$
is the canonical projection defined by
$\pi(m_{1},m_{2},\boldsymbol{\epsilon}):=\boldsymbol{\epsilon}$, in these
circumstances the complement
$\mathbb{R}^{\ell(n)}\setminus\pi\left(\Psi_{n}\rvert_{X}^{-1}({\bf
0})\right)$ is a dense subset of $\mathbb{R}^{\ell(n)}$. Indeed, since $\pi$
is a continuously differentiable map, then so is its restriction
$\pi\rvert_{\Psi_{n}\lvert_{X}^{-1}\left({\bf
0}\right)\times\mathbb{R}^{\ell}}:\Psi_{n}\lvert_{X}^{-1}\left({\bf
0}\right)\to\mathbb{R}^{\ell}$ which by Theorem 4.4.11 guarantees the density
of $\mathbb{R}^{\ell(n)}\setminus\pi\left(\Psi_{n}\rvert_{X}^{-1}({\bf
0})\right)$. This implies that we can choose
$\boldsymbol{\epsilon}\in\left(\mathbb{R}^{\ell(n)}\setminus\pi\left(\Psi_{n}\rvert_{X}^{-1}({\bf
0})\right)\right)$ as small as we want so that $\boldsymbol{\epsilon}\in
U_{{\bf 0}}$ and $\omega_{n}\in\mathcal{N}$. We fix this $\epsilon$ and see
that for any $(m_{1},m_{2})\in W$ the map
$\Psi_{n}(m_{1},m_{2},\boldsymbol{\epsilon})\neq 0$, as required.
Consequently, all that remains to be done is to find $n$ sufficiently large so
that $\Psi_{n}\rvert_{W\times\\{{\bf 0}\\}}$ is a submersion, and then the
proof will be complete.

We start by observing that by (4.27)

$\omega_{n}\circ\phi^{-t}=\omega\circ\phi^{-t}+\sum_{i=1}^{\ell(n)}\epsilon_{i}\lambda_{i}\circ\phi^{-t}$

hence

$\frac{\partial(\omega_{n}\circ\phi^{-t})}{\partial\epsilon_{j}}=\lambda_{j}\circ\phi^{-t}.$

Now we consider an arbitrary $(m_{1},m_{2})\in W$ assuming once again without
loss of generality that $m_{1}\in M\setminus V_{p}.$ For each point in the
orbit $\\{\phi^{-t}(m_{1})\\}_{t=0,\ldots,T(n)-1}$ there exists a $j(t)\in
J_{n}$ such that $\lambda_{j(t)}\left(\phi^{-t}(m_{1})\right)\geq 1/2$ by the
special property that we imposed earlier on the partition of unity
$\\{\lambda_{i}\ |\ i\in J_{n}\\}$. Now the support of $\lambda_{j(t)}$ is a
ball $B_{j(t)}$ of radius $2^{-(n+1)}$ which contains $\phi^{-t}(m_{1})$.
Hence the ball $B_{j(t)}\subset B_{2^{-n}}(\phi^{-t}(m_{1}))$. Now since the
sets in the family $\\{B_{2^{-n}}(\phi^{-t}(m_{1}))\\}_{t=0,\ldots,T(n)-1}$
are disjoint then so are $\\{B_{j(t)}\\}_{t=0,\ldots,T(n)-1}$. Furthermore,
since $B_{2^{-n}}(\phi^{-t}(m_{1}))\cap
B_{2^{-n}}(\phi^{-s}(m_{2}))=\emptyset$ for all $t,s\in\\{0,\ldots,T(n)-1\\}$
hence $\lambda_{j(t)}(\phi^{-t}(m_{2}))=0$ for $t\in\\{0,\ldots,T(n)-1\\}$.
Thus

$\displaystyle\frac{\partial(\omega_{n}\circ\phi^{-t})}{\partial\epsilon_{j(t)}}(m_{2})=0.$

Now,

$\displaystyle\Psi_{n}(m_{1},m_{2},\epsilon)$
$\displaystyle=\sum_{t=0}^{T(n)-1}A^{t}C(\omega_{n}(\phi^{-t}(m_{1}))-\omega_{n}(\phi^{-t}(m_{2})))$
$\displaystyle+\sum_{t=T(n)}^{\infty}A^{t}C(\omega_{n}(\phi^{-t}(m_{1}))-\omega_{n}(\phi^{-t}(m_{2})))$

hence for $t=0,\ldots,T(n)-1$

$\displaystyle\frac{\partial\Psi_{n}}{\partial\epsilon_{j(t)}}(m_{1},m_{2},\epsilon)$
$\displaystyle=A^{t}C(\lambda_{j(t)}(\phi^{-t}(m_{1})))$
$\displaystyle+\sum_{t=T(n)}^{\infty}A^{t}C(\lambda_{j(t)}(\phi^{-t}(m_{1}))-\lambda_{j(t)}(\phi^{-t}(m_{2}))).$

By assumption $\\{A^{t}C\\}_{t=0,...,N-1}$ are linearly independent, hence the
vectors

$\displaystyle\\{A^{t}C(\lambda_{j(t)}(\phi^{-t}(m_{1})))\\}_{t\in\\{0,\ldots,T(n)-1\\}}$

necessarily span $\mathbb{R}^{N}$ because since $n>\nu$ then $T(n)\geq N$.
Crucially, for any $n$ the property $\lambda_{j(t)}(\phi^{-t}(m_{1}))\geq 1/2$
holds and therefore, the residual term

$\displaystyle\sum_{t=T(n)}^{\infty}A^{t}C(\lambda_{j(t)}\phi^{-t}(m_{1})-\lambda_{j(t)}\phi^{-t}(m_{2}))$

may only spoil the spanning property of the vectors
$\\{A^{t}C(\lambda_{j(t)}\phi^{-t}(m_{1}))\\}_{t=0,\ldots,N-1}$ if it is
sufficiently large. Since by hypothesis $\rho(A)<1$, the residual term
converges uniformly over $(m_{1},m_{2})\in W$ to $0$ as $n$ grows. We choose
consequently $n$ large enough so that for all $(m_{1},m_{2})\in W$ the
residual term is too small to spoil the spanning property of
$\\{A^{t}C(\lambda_{j(t)}\phi^{-t}(m_{1}))\\}_{t\in\\{0,\ldots,N-1\\}}$. With
this choice of $n$ we have that $\Psi_{n}\rvert_{W\times\\{0\\}}$ is a
submersion and the proof is complete. ∎

####  4.4.4 An embedding almost surely

In this subsection we will prove Theorem 4.2.4.

###### Proof.

First we will establish two lemmas about random matrices.

######  Lemma 4.4.12.

Let $X_{1},\ldots,X_{n}$ be independent real-valued non-singular random
variables and let $p$ be a non-constant polynomial in $n$ complex variables.
Then

$\displaystyle\mathbb{P}\left(p(X_{1},\ldots,X_{n})=0\right)=0.$

###### Proof.

Define $\mu_{j}(\cdot):=\mathbb{P}(X_{j}\in\cdot),$ $j=1,\ldots,n$, and let
$Z=\\{\mathbf{x}\in\mathbb{C}^{n}\mid\ p(\mathbf{x})=0\\}$ be the set of
complex roots of the polynomial $p$. Then, since $X_{1},\ldots,X_{n}$ are
independent we have that

$\displaystyle\mathbb{P}\left(p(X_{1},\ldots,X_{n})=0\right)=\mathbb{P}\left((X_{1},\ldots,X_{n})\in
Z\right)=(\mu_{1}\ldots\mu_{n})(Z).$

We now proceed by induction over $n$. For $n=1$ we have that
$\mathbb{P}\left(p(X_{1})=0\right)=\mu_{1}(Z)=0$ since $Z$ is finite and
$X_{1}$ is non-singular. Let the claim be true for $n-1$. For fixed
$x_{1}\in\mathbb{C}$ set
$p_{x_{1}}(x_{2},\ldots,x_{n}):=p(x_{1},\ldots,x_{n})$ and let

$\displaystyle Z_{x_{1}}:=\\{(x_{2},\ldots,x_{n})\in\mathbb{C}^{n-1}\mid\
p_{x_{1}}(x_{2},\ldots,x_{n})=0\\}.$

The set $F:=\\{x_{1}\in\mathbb{R}\mid\ p_{x_{1}}\equiv 0\\}$ is a finite set,
so

$\mathbb{P}\left(p(X_{1},\ldots,X_{n})=0\right)=\int_{\mathbb{C}}(\mu_{2}\ldots\mu_{n})(Z_{x_{1}})d\mu_{1}(x_{1})=\int_{\mathbb{C}-F}(\mu_{2}\ldots\mu_{n})(Z_{x_{1}})d\mu_{1}(x_{1})=0,$

since we assumed that $X_{1}$ is non-singular and
$(\mu_{2},\ldots,\mu_{n})(Z_{x_{1}})=0$ for $x_{1}\notin F$ by the induction
hypothesis. ∎

######  Lemma 4.4.13.

Let $N\in\mathbb{R}^{N}$, let $A$ be a real $N\times N$ matrix, and let $C$ be
a random vector in $\mathbb{R}^{N}$. Assume the entries of $A$ and $C$ have
been drawn using independent non-singular real valued random variables.
Moreover, let $p_{1},\ldots,p_{n}\in\mathbb{C}[x]$ be linearly independent
polynomials in one variable of degree at most $n-1$. Then

$\displaystyle\mathbb{P}(\det\left(p_{1}(A)C,p_{2}(A)C,\cdots,p_{n}(A)C\right)=0)=0.$

Equivalently, the vectors $p_{1}(A)C,p_{2}(A)C,\ldots,p_{n}(A)C$ are linearly
independent almost surely.

###### Proof.

The expression $\det\left(p_{1}(A)C,\cdots,p_{n}(A)C\right)$ is a polynomial
$p$ in the $n^{2}+n$ variables $a_{ij}$ and $b_{j}$,
$i,j\in\left\\{1,\ldots,n\right\\}$ that constitute the entries of $A$ and
$C$, respectively, and which in turn are by hypothesis non-singular random
variables. As long as the polynomial $p$ is not identically zero, the result
follows directly from the Lemma 4.4.12. So all that remains is to show that
$p$ is not identically zero, that is, that there exist particular choices of
$A$ and $C$ such that $\det\left(p_{1}(A)C,\cdots,p_{n}(A)C\right)$ is non-
zero. So, we choose $C=(1,\ldots,1)^{\top}$ and
$A=\text{diag}(a_{1},\ldots,a_{n})$ with distinct real numbers
$a_{1},\ldots,a_{n}$. We expand the polynomials $p_{j}$ in terms of their
coefficients $\gamma_{j1},\ldots,\gamma_{jn}$ so

$\displaystyle p_{j}(x)=\sum_{k=0}^{n-1}\gamma_{jk}x^{k}.$

The vectors $\gamma_{j}=(\gamma_{j1},\ldots,\gamma_{jn})^{\top}$,
$j\in\left\\{1,\ldots,n\right\\}$, are by hypothesis linearly independent. We
now show that with these choices, the vectors
$p_{1}(A)C,p_{2}(A)C,\ldots,p_{n}(A)C$ are linearly independent and hence
$\det\left(p_{1}(A)C,p_{2}(A)C,\cdots,p_{n}(A)C\right)\neq 0$, as required.
Indeed, let $c_{1},\ldots,c_{n}\in\mathbb{R}$ and suppose that
$\sum_{j=1}^{n}c_{j}p_{j}(A)C={\bf 0}$. Additionally, we can write

$\displaystyle\sum_{j=1}^{n}c_{j}p_{j}(A)C=\sum_{j=1}^{n}c_{j}\sum_{k=0}^{n-1}\gamma_{kj}A^{k}C=\sum_{k=0}^{n-1}\bigg{(}\sum^{n}_{j=1}c_{j}\gamma_{jk}\bigg{)}\begin{bmatrix}a_{1}^{k}\\\
a_{2}^{k}\\\ \vdots\\\ a_{n}^{k}\end{bmatrix}=Vx$

where

$V=\left(\begin{array}[]{ccccc}1&a_{1}&a_{1}^{2}&\ldots&a_{1}^{n-1}\\\
1&a_{2}&a_{2}^{2}&\ldots&a_{2}^{n-1}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&a_{n}&a_{n}^{2}&\ldots&a_{n}^{n-1}\end{array}\right)\quad\mbox{and}\quad
x=\sum^{n}_{j=1}c_{j}\gamma_{j}.$

Since the diagonal entries of $A$ are all different and the determinant of the
Vandermonde matrix $V$ is given by

$\det(V)=\prod_{1\leq i<j\leq n}\left(a_{i}-a_{j}\right)$

we can conclude that $V$ is invertible and hence the identity
$\sum_{j=1}^{n}c_{j}p_{j}(A)C=Vx={\bf 0}$ implies that $x={\bf 0}$. By the
linear independence of the vectors $\gamma_{1},\ldots,\gamma_{n}$ we have that
$c_{1},\ldots,c_{n}=0$ necessarily. It follows that the vectors
$p_{1}(A)C,p_{2}(A)C,\ldots,p_{n}(A)C$ are linearly independent, as required.
∎

Now we may complete the proof of Theorem 4.2.4. The vectors
$C,AC,A^{2}C,\ldots,A^{N-1}C$ are linearly independent if and only if

$\displaystyle\text{det}\left(C,AC,A^{2}C,\cdots,A^{N-1}C\right)=0$

which, in the notation of Lemma 4.4.13, can be written as

$\displaystyle\text{det}\left(p_{0}(A)C,p_{1}(A)C,p_{2}(A)C,\ldots,p_{N-1}(A)C\right)=0$

using the linearly independent polynomials $p_{j}(A):=A^{j}$,
$j\in\left\\{0,\ldots,N-1\right\\}$. Part (i) of the statement hence follows
directly from Lemma 4.4.13. Now we turn our attention to part (ii). First of
all, $\lambda_{j}$ is an eigenvalue of $A$ if and only if $\lambda_{j}$ is a
root of the characteristic polynomial of $A$. This event has probability $0$
by Lemma 4.4.12 and hence $1,\lambda_{1},\ldots,\lambda_{q}\notin\sigma(A)$
almost surely. On this event, the inverses $(I-\lambda_{j}A)^{-1}$ and
$(I-A)^{-1}$ exist. Furthermore, the product

$\displaystyle\prod_{i=1}^{q}(I-\lambda_{i}A)$

is an invertible matrix. Therefore, the vectors

$\displaystyle(I-\lambda_{j}A)^{-1}(I-A)^{-1}(I-A^{N})C,\quad\mbox{with
$j=1,...,m$,}$

are linearly independent if and only if

$\displaystyle\prod_{i=1}^{q}(I-\lambda_{i}A)(I-\lambda_{j}A)^{-1}(I-A)^{-1}(I-A^{N})C,\quad\mbox{with
$j=1,...,m$,}$ (4.28)

are linearly independent. We can now rewrite the vectors in (4.28) as

$\displaystyle\prod_{i=1}^{q}(I-\lambda_{i}A)(I-\lambda_{j}A)^{-1}(I-A)^{-1}(I-A^{N})C$
$\displaystyle=\prod_{i\neq j}^{q}(I-\lambda_{i}A)(I-A)^{-1}(I-A^{N})C$
$\displaystyle=\prod_{i\neq j}^{q}(I-\lambda_{i}A)\sum_{k=0}^{N-1}A^{k}C,$

where we used the relation

$(I-A^{N})=(I-A)\sum_{k=0}^{N-1}A^{k}\quad\mbox{and hence
that}\quad(I-A)^{-1}(I-A^{N})=\sum_{k=0}^{N-1}A^{k}.$

Now, if we are able to show that the family

$\displaystyle p_{j}(x)=\prod_{i\neq
j}^{q}(1-\lambda_{i}x)\sum_{k=0}^{N-1}x^{k},\quad\mbox{with }\quad
j\in\left\\{1,\ldots,m\right\\}$

is linearly independent, then we can conclude by Lemma 4.4.13 that the vectors
(4.28) are linearly independent almost surely, which would complete the proof.
This is indeed the case because if $\mu_{1},\ldots,\mu_{n}\in\mathbb{R}$ are
such that

$\sum_{j=1}^{n}\mu_{j}p_{j}(x)=0\quad\mbox{then}\quad\left(\sum_{k=0}^{N-1}x^{k}\right)\left(\sum_{j=1}^{n}\mu_{j}\prod_{i\neq
j}^{q}(1-\lambda_{i}x)\right)=0.$

Given that the polynomial $\sum_{k=0}^{N-1}x^{k}$ is non-zero, the previous
equality is equivalent to $\sum_{j=1}^{n}\mu_{j}\prod_{i\neq
j}^{m}(1-\lambda_{i}x)=0$ which, evaluated at $x=1/\lambda_{k}$, implies that

$0=\sum_{j=1}^{n}\mu_{j}\prod_{i\neq
j}^{q}\left(1-\lambda_{i}\frac{1}{\lambda_{k}}\right)=\mu_{k}\prod_{i\neq
k}^{q}\left(1-\lambda_{i}\frac{1}{\lambda_{k}}\right).$

Given that, by hypothesis, the values
$\lambda_{1},\ldots,\lambda_{q}\in\mathbb{C}$ are all different, we can
conclude that $\prod_{i\neq
k}^{q}\left(1-\frac{\lambda_{i}}{\lambda_{k}}\right)\neq 0$ and hence
$\mu_{k}=0$, necessarily. Since procedure can be repeated to obtain that
$\mu_{1},\ldots,\mu_{n}=0$, the result follows. ∎

After all this work, the proofs are complete. In summary: we have shown that
reservoir maps of the form

$\displaystyle F(x,z)=Ax+Cz+b$

with randomly generated weights $A,C$ and biases $b$ admit a GS
$f_{(\phi,\omega,F)}$ when driven by observations of a discrete time dynamical
system $(M,\phi)$. If the dynamical system $(M,\phi)$ is well behaved at the
fixed points, then for generic observation functions $\omega\in
C^{2}(M,\mathbb{R})$, the GS $f_{(\phi,\omega,F)}$ is an embedding almost
surely.

##  Chapter 5 Universal Approximation

We saw in Chapter 1 that an ESN does a good job predicting the future
trajectory of the Lorenz system, whose evolution is nonlinear. Furthermore,
there is a large literature attesting to the performance of ESNs when tasked
with learning highly nonlinear relationships between datasets and targets
(Tanaka et al., 2019). This suggests that ESNs may have some sort of universal
approximation property. There is recent literature analysing the universal
approximation of ESNs and reservoir maps more generally - with different
authors taking different approaches. One strand of work developed in
GRIGORYEVA2018495, GONON2020132721, Gonon2020, and GONON202110 presents
universal approximation results in terms of filters and functionals (which are
presented in this thesis in Chapter 6). This builds upon the work by
Matthews1993 who establishes the universal approximation of fading memory
systems supported by neural networks. Many of these results hold for arbitrary
input sequences, without any reference to the process that generated them.
This is in contrast to the results that will appear in this chapter, which
will hold for input sequences generated by an ergodic and determinstic
dynamical system. Many of the results presented here also hold for stationary
and ergodic random processes - and this is explored in Chapter 6. The
presentation of this present chapter closely follows
embedding_and_approximation_theorems and HART2021132882.

###  5.1 Universal Approximation Theorems

Many (perhaps all) of the major approximation results for Echo State Networks
and similar reservoir maps are built upon Hornik’s (1990) universal
approximation theorem for feedforward neural networks. The result states,
under mild assumptions on the activation function $\sigma$, that feedforward
neural networks are dense in the set of differentiable functions. To make this
formal, we’ll first introduce the mild assumption on $\sigma$.

######  Definition 5.1.1.

($\ell$-finite) Let $\ell\in\mathbb{N}_{0}$. Then we say an $\ell$-times
differentiable scalar function $\sigma\in C^{\ell}(\mathbb{R})$ is
$\ell$-finite if

$\displaystyle
0<\int_{\mathbb{R}}\bigg{|}\frac{d^{\ell}\sigma}{dx^{\ell}}\bigg{|}dx<\infty.$

######  Theorem 5.1.2.

(Universal Approximation Theorem, HORNIK1990551) Let $K\subset\mathbb{R}^{n}$
be a compact subset. If the activation function $\sigma$ is $\ell$-finite,
$W_{1},\ldots W_{N}\in\mathbb{R}$ and $C_{1},\ldots,C_{N}\in\mathbb{R}^{n}$,
and $b_{1},\ldots,b_{N}\in\mathbb{R}$ then, for all $0\leq r\leq\ell$, the set
of functions $g:K\to\mathbb{R}$ of the form

$\displaystyle g(x)=\sum_{j=1}^{N}W_{j}\sigma(C_{j}^{\top}x+b_{j})$

are dense in $C^{r}(K,\mathbb{R})$.

There are many other universal approximation theorems found throughout the
literature (Cybenko1989; NIPS2017_32cbf687) which typically show that neural
networks (of some variety) equipped with an activation function (that
satisfies mild conditions) are dense in some set of functions (with certain
regularity conditions) between topological spaces (that satisfy reasonable
conditions - usually subsets of $\mathbb{R}^{n}$). There are many novel
results (Gonon2020; arXiv:1910.03344; arXiv:2006.02341; arXiv:2101.05390;
Gonon2021) which determine approximation bounds for the number of neurons
required to approximate a sufficiently regular function. The bounds are often
explicit up to a constant, which is sometimes computed exactly. Throughout
this thesis we do not work with approximation bounds. This simplifies the
presentation considerably, but comes at the cost of leaving us with no idea
how many neurons are required for a given task.

For the results that follow we use Hornik’s seminal result because it allows
the pointwise approximation of a function $g$ in addition to its derivatives
up to any order. This smooth approximation is of crucial importance for the
topological results to come; but it is over-engineered for others. The first
result we will present states that, if the internal weights $C_{j}$ and biases
$b_{j}$ are randomly generated, there exists a choice of outer weights $W_{j}$
so that the network $g$ will approximate the target function as closely as is
required. This result and preliminary lemmas appear in
embedding_and_approximation_theorems. A variant of the result with
approximation bounds appears in Gonon2020.

######  Lemma 5.1.3.

Let $(X_{j})_{j\in\mathbb{N}}$ be a sequence of i.i.d. random variables and
$S_{1},\ldots,S_{\ell}$ be a list of $\ell$ events, and suppose that for each
$i$ (and for any $j$ since they are i.i.d.) there exists $\theta_{i}$ such
that $\mathbb{P}(X_{j}\in S_{i})=\theta_{i}>0$. Then for all $\alpha\in(0,1)$
there exists $N\in\mathbb{N}$ such that

$\displaystyle\mathbb{P}\big{(}\exists\text{ injective
}\phi:\\{1,\ldots,\ell\\}\to\\{1,\ldots,N\\}:X_{\phi(i)}\in S_{i},\ \ \forall\
i\in\\{1,\ldots,\ell\\}\big{)}>\alpha.$

###### Proof.

First, fix $\alpha\in(0,1)$. Then define the set $\\{n_{0},\ldots,n_{\ell}\\}$
as follows. Set $n_{0}=0$ and for any $i\in\\{1,...,\ell\\}$ let

$\displaystyle
n_{i}-n_{i-1}:=\text{ceil}\bigg{(}\frac{\log(1-\alpha^{1/\ell})}{\log(1-\theta_{i})}\bigg{)}+1.$

Finally, set $N=n_{\ell}$. Then we can calculate that

$\displaystyle\mathbb{P}\big{(}\exists\text{ injective }\phi:X_{\phi(i)}\in
S_{i}\ \forall i\in\\{1,\ldots,\ell\\}\big{)}$ $\displaystyle>$
$\displaystyle\mathbb{P}\big{(}\forall\ i\in\\{1,\ldots,\ell\\}\ \exists\
j\in\\{1+n_{i-1},\ldots,n_{i}\\}:X_{j}\in S_{i}\big{)}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{\ell}\mathbb{P}\big{(}\exists
j\in\\{1+n_{i-1},\ldots,n_{i}\\}:X_{j}\in S_{i}\big{)}$ $\displaystyle=$
$\displaystyle\prod_{i=1}^{\ell}1-\mathbb{P}\big{(}X_{j}\notin S_{i}\ \forall
j\in\\{1+n_{i-1},\ldots,n_{i}\\}\big{)}$ $\displaystyle\geq$
$\displaystyle\prod_{i=1}^{\ell}1-(1-\theta_{i})^{n_{i}-n_{i-1}}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{\ell}1-(1-\theta_{i})^{\text{ceil}\big{(}\log(1-\alpha^{1/\ell})/\log(1-\theta_{i})\big{)}+1}$
$\displaystyle>$
$\displaystyle\prod_{i=1}^{\ell}1-(1-\theta_{i})^{\big{(}\log(1-\alpha^{1/\ell})/\log(1-\theta_{i})\big{)}}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{\ell}1-\exp\bigg{(}\frac{\log(1-\alpha^{1/\ell})}{\log(1-\theta_{i})}\log(1-\theta_{i})\bigg{)}$
$\displaystyle=$
$\displaystyle\prod_{i=1}^{\ell}1-(1-\alpha^{1/\ell})=\prod_{i=1}^{\ell}\alpha^{1/\ell}=\alpha.$

∎

######  Theorem 5.1.4.

(Random Universal Approximation Theorem) Let $K\subset\mathbb{R}^{n}$ be a
compact subset and $f\in C^{\ell}(K,\mathbb{R})$. Let $\sigma\in
C^{\ell}(\mathbb{R})$ be $\ell$-finite, and let
$(b_{j}\in\mathbb{R})_{j\in\mathbb{N}}$,
$(C_{j}\in\mathbb{R}^{n})_{j\in\mathbb{N}}$ be sequences of i.i.d. random
variables with full support. Then for any $0\leq r\leq\ell$, and
$\alpha\in(0,1)$ and $\epsilon>0$ there exists some natural number
$N\in\mathbb{N}$ such that, with probability greater than $\alpha$, there
exist real numbers $W_{1},\ldots,W_{N}\in\mathbb{R}$ such that the _random
neural network_ $g:K\to\mathbb{R}$ defined by

$\displaystyle g(x)=\sum_{j=1}^{N}W_{j}\sigma(C_{j}^{\top}x+b_{j})$

satisfies

$\displaystyle\lVert f-g\rVert_{C^{r}}<\epsilon.$

###### Proof.

First, fix $r\geq 0$. Then by the Universal Approximation Theorem we know that
for any $\epsilon>0$ there exists a neural network $\hat{g}:K\to\mathbb{R}$
with $N^{\prime}$ neurons defined by

$\displaystyle\hat{g}(x)=\sum_{i=1}^{N^{\prime}}\hat{W}_{i}\sigma(\hat{C}_{i}^{\top}x+\hat{b}_{i})$

such that

$\displaystyle\lVert f-\hat{g}\rVert_{C^{r}}<\frac{\epsilon}{2}.$ (5.1)

Now, consider two sequences of i.i.d. random variables
$(b_{j})_{j\in\mathbb{N}}$ and $(C_{j})_{j\in\mathbb{N}}$ with full support,
and let $X_{j}:=(b_{j},C_{j})$. Fix $\epsilon>0$ and define a collection of
$N^{\prime}$ events $S_{1},...,S_{N^{\prime}}$ by

$\displaystyle
S_{i}:=\bigg{\\{}(b,C)\in\mathbb{R}\times\mathbb{R}^{n}:\lVert\sigma(\hat{C}_{i}^{\top}\cdot+\hat{b}_{i})-\sigma(C^{\top}\cdot+b)\rVert_{C^{r}}<\frac{\epsilon}{2N^{\prime}\max_{k}(\hat{W}_{k})}\bigg{\\}},$

where the weights $\hat{W}_{k}$ are given by the form of the network
$\hat{g}$. Observe that each of the $S_{i}$ have strictly positive measure, so
there exists $\theta_{i}>0$ such that $\mathbb{P}(X_{j}\in
S_{i})>\theta_{i}>0\ \forall j\in\mathbb{N}$. Hence it follows by Lemma 5.1.3
that for all $\alpha\in(0,1)$ there exists $N\in\mathbb{N}$ such that

$\displaystyle\mathbb{P}\big{(}\exists\text{ injective
}\phi:\\{1,\ldots,N^{\prime}\\}\to\\{1,\ldots,N\\}:X_{\phi(i)}\in S_{i}\
\forall i\in\\{1,\ldots,N^{\prime}\\}\big{)}>\alpha.$

Now, assuming the event

$\displaystyle\exists\text{ injective
}\phi:\\{1,\ldots,N^{\prime}\\}\to\\{1,\ldots,N\\}:X_{\phi(i)}\in S_{i}\
\forall i\in\\{1,\ldots,N^{\prime}\\}$

occurs, we define

$\displaystyle W_{j}:=\begin{cases}\hat{W}_{i}\text{ if }\phi(i)=j\\\ 0\text{
otherwise }\end{cases}$

for all $j\in\\{1,\ldots,N\\}$, and define the _random neural network_
$g:K\to\mathbb{R}$ by

$\displaystyle g(x)=\sum^{N}_{j=1}W_{j}\sigma(C_{j}^{\top}x+b_{j}).$

Now observe that

$\displaystyle\lVert\hat{g}-g\rVert_{C^{1}}$ $\displaystyle=$
$\displaystyle\bigg{\lVert}\sum_{i=1}^{N^{\prime}}\hat{W}_{i}\sigma(\hat{C}_{i}^{\top}\cdot+\hat{b}_{i})-\sum_{j=1}^{N}W_{j}\sigma(C^{\top}_{j}\cdot+b_{j})\bigg{\rVert}_{C^{r}}$
$\displaystyle=$
$\displaystyle\bigg{\lVert}\sum_{i=1}^{N^{\prime}}\hat{W}_{i}\big{(}\sigma(\hat{C}_{i}^{\top}\cdot+\hat{b}_{i})-\sigma\big{(}C_{\phi(i)}^{\top}\cdot+b_{\phi(i)}\big{)}\big{)}\bigg{\rVert}_{C^{r}}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{N^{\prime}}\hat{W}_{i}\bigg{\lVert}\big{(}\sigma(\hat{C}_{i}^{\top}\cdot+\hat{b}_{i})-\sigma\big{(}C_{\phi(i)}^{\top}\cdot+b_{\phi(i)}\big{)}\big{)}\bigg{\rVert}_{C^{r}}$
$\displaystyle<$
$\displaystyle\sum_{i=1}^{N^{\prime}}\frac{\hat{W}_{i}\epsilon}{2N^{\prime}\max_{k}(\hat{W}_{k})}<\frac{\epsilon}{2}.$

Combining this with (5.1) and using the triangle inequality we obtain

$\displaystyle\lVert f-g\rVert_{C^{1}}\leq\lVert
f-\hat{g}\rVert_{C^{r}}+\lVert\hat{g}-g\rVert_{C^{r}}<\frac{\epsilon}{2}+\frac{\epsilon}{2}=\epsilon,$

which completes the proof. ∎

The above result states that if we randomly generate the internal weights of a
feedforward neural network with sufficiently many neurons, then there exists a
choice of outer weights $W\in\mathbb{R}^{N}$ that will yield a sufficiently
good approximation. This existence result is non constructive in the sense
that

  1. 1.

We do not know how many neurons $N$ are required for a given error $\epsilon$
or for a given probability $\alpha$.

  2. 2.

We do not know how to choose the output weights $W\in\mathbb{R}^{N}$.

Gonon2020 have made significant progress on item $1.$, so in what follows, we
will focus on items $2.$ In particular, we will consider an input sequence
arising from the scalar observations of an ergodic dynamical system evolving
on a manifold $M$. We will prove that for $W\in\mathbb{R}^{N}$ obtained by
linear regression, as in Chapter 1, the approximation can be made arbitrarily
good by increasing the number of neurons $N\in\mathbb{N}$ and data points
$\ell\in\mathbb{N}$. The presentation in this chapter closely follows
HART2021132882. The results rely on ergodic theory - which we will introduce
next.

###  5.2 Ergodic Theory

We can view an ergodic process, whether it is deterministic or random, as a
process where the time average of some feature through phase space converges
toward the spatial average of that feature throughout the phase space, almost
surely.

For example, one could imagine a room that is heated to some constant,
spatially inhomogeneous temperature. Perhaps the top of the room is warmer
than the bottom as a consequence of heat rising, and one side, perhaps with
single glazed windows, is cooler than the other. Nevertheless, the room has a
well defined, constant, spatial average temperature. Now, we can view, under
idealised assumptions, the average temperature of the room as proportional to
root mean square velocity of the particles the room. If the particle dynamics
are ergodic, we may observe a single arbitrary particle and track its velocity
as it traverses the room. We expect the particle to explore the whole room,
moving with greater velocity in the warm areas, and lower velocity in cool
areas, such that the particle’s root mean square velocity over time converges
toward the spatial temperature average of the room. This convergence of the
_time average_ of the particle’s velocity to the _space average_ over all
particles in the room is the crucial property of ergodic systems that we will
exploit. In this chapter we are interested in deterministic ergodic systems,
and in Chapter 6 we will extend the results the stationary and ergodic random
processes.

We require that the underlying dynamical system is ergodic so that minimising
the mean square differences between observations and targets closely
approximates the mapping between the observation space and target space. The
ergodicity ensures that that training data generated from a trajectory
initialised at almost any point $m_{0}\in M$ will represent all dynamics on
$M$. To make this formal, we will introduce the definition of ergodicity and
the celebrated Ergodic Theorem.

######  Definition 5.2.1.

($\mu$-Generic Point) Suppose $\phi:M\to M$ is a measure preserving map with
respect to the measure space $(M,\Sigma,\mu)$. Then $m_{0}\in M$ is called a
$\mu$-generic point if the orbit of $m_{0}$ is uniformly distributed over $M$
according to the measure $\mu$.

######  Remark 5.2.2.

A $\mu$-generic point is not to be confused with a generic property defined in
Definition 4.1.4. The overlap in terminology is indeed annoying.

######  Proposition 5.2.3.

Suppose $\phi:M\to M$ is a measure preserving map with respect to the
probability space $(M,\Sigma,\mu)$ and $s\in L^{1}(\mu)$. Suppose $m_{0}$ is a
$\mu$-generic point in $M$ then

$\displaystyle\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}s\circ\phi^{k}(m_{0})=\int_{M}s\
d\mu.$

######  Definition 5.2.4.

(Ergodic) Let $\phi:M\to M$ be a measure preserving transformation on the
probability space $(M,\Sigma,\mu)$. Then $\phi$ is ergodic if for every
$\sigma\in\Sigma$ with $\phi^{-1}(\sigma)=\sigma$ either $\mu(\sigma)=0$ or
$\mu(\sigma)=1$.

######  Theorem 5.2.5.

(Ergodic Theorem (Birkhoff656)) Suppose $\phi:M\to M$ is ergodic with respect
to the probability space $(M,\Sigma,\mu)$ and $s\in L^{1}(\mu)$. Then
$\mu$-almost all $m_{0}\in M$ are generic hence for $\mu$-almost all $m_{0}\in
M$

$\displaystyle\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}s\circ\phi^{k}(m_{0})=\int_{M}s\
d\mu.$ (5.2)

The left hand side of (5.2) is called the _time average_ taken from the
initial point $m_{0}\in M$, and the right hand side is called the _space
average_. The Ergodic Theorem then states that the time average taken from
almost all initial points equals the space average.

###  5.3 A Training Theorem for Echo State Networks

####  5.3.1 Regularised Least Squares Regression

Suppose we have have an ergodic dynamical system $\phi:M\to M$, and we observe
the dynamics via an observation map $g:M\to\mathbb{R}^{P}$ for some fixed
$P\in\mathbb{N}$ and target map $u:M\to\mathbb{R}$. A trajectory originating
from a $\mu$-generic point $m_{0}\in M$ will ergodically explore the space $M$
and yield a sequence of observations $g\circ\phi^{k}(m_{0})$ and targets
$u\circ\phi^{k}(m_{0})$ for $k=0,1,2,...,\ell$.

Suppose we compute the vectors $W_{\ell}\in\mathbb{R}^{P}$ minimising the
regularised least squares difference between the mapping of the observations
$W^{\top}g\circ\phi^{k}(m_{0})$ and the targets $u\circ\phi^{k}(m_{0})$. We
prove in the next lemma that as the number of data points $\ell$ grows large,
the least squares solution $W_{\ell}$ minimises the ergodic average difference
between the mapping on the observations $W^{\top}g\circ\phi^{k}(m_{0})$ and
the targets $u\circ\phi^{k}(m_{0})$.

######  Lemma 5.3.1.

Let $(M,\Sigma)$ be a measurable space, and suppose that $\phi:M\to M$ is
ergodic with invariant measure $\mu$. Let $m_{0}$ be a $\mu$-generic point in
$M$. Let $g\in L^{2}(\mu)(M,\mathbb{R}^{P})$ be an observation function and
suppose that $u\in L^{2}(\mu)(M,\mathbb{R})$ is a target function we wish to
approximate.

Let $\Lambda\in\mathbb{M}_{P\times P}(\mathbb{R})$. Define the sequence
$(W_{\ell})_{\ell\in\mathbb{N}}$ such that, for each $\ell\in\mathbb{N}$, the
vector $W_{\ell}\in\mathbb{R}^{P}$ is the unique minimiser of the regularised
least squares difference

$\displaystyle\frac{1}{\ell}\bigg{(}\sum_{k=0}^{\ell-1}\rVert
W^{\top}g\circ\phi^{k}(m_{0})-u\circ\phi^{k}(m_{0})\lVert^{2}+\lVert\Lambda
W\rVert^{2}\bigg{)}.$

Then, the sequence $(W_{\ell})_{\ell\in\mathbb{N}}$ converges to

$\displaystyle W^{*}$ $\displaystyle=\bigg{(}\int_{M}g(m)g(m)^{\top}\
d\mu(m)+\Lambda\Lambda^{\top}\bigg{)}^{-1}\int_{M}u(m)g(m)\ d\mu(m)$

which is the unique minimiser (over $W\in\mathbb{R}^{P}$) of

$\displaystyle\lVert W^{\top}g-u\rVert_{L^{2}(\mu)}^{2}+\lVert\Lambda
W\rVert^{2}.$

###### Proof.

Consider the map $\Psi:\mathbb{R}^{P}\to\mathbb{R}$ defined by

$\displaystyle\Psi(W)$ $\displaystyle=\lVert
W^{\top}g-u\rVert_{L^{2}(\mu)}^{2}+\lVert\Lambda W\rVert^{2}=\int_{M}\lVert
W^{\top}g(m)-u(m)\rVert^{2}\ d\mu(m)+\lVert\Lambda W\rVert^{2}.$

The minimiser of $\Psi$ satisfies $D\Psi=0$ where $D$ is the derivative
operator, so we consider

$\displaystyle 0$ $\displaystyle=(D\Psi)(W)$
$\displaystyle=D\bigg{(}\int_{M}\lVert W^{\top}g(m)-u(m)\rVert^{2}\
d\mu(m)+\lVert\Lambda W\rVert^{2}\bigg{)}$ $\displaystyle=\int_{M}D\lVert
W^{\top}g(m)-u(m)\rVert^{2}\ d\mu(m)+D\lVert\Lambda W\rVert^{2}$
$\displaystyle=\int_{M}2(W^{\top}g(m)-u(m))g(m)^{\top}\
d\mu(m)+2W^{\top}\Lambda\Lambda^{\top}$
$\displaystyle=\int_{M}(W^{\top}g(m)-u(m))g(m)^{\top}\
d\mu(m)+W^{\top}\Lambda\Lambda^{\top}$
$\displaystyle=W^{\top}\int_{M}g(m)g(m)^{\top}\
d\mu(m)-\int_{M}u(m)g(m)^{\top}\ d\mu(m)+W^{\top}\Lambda\Lambda^{\top}$
$\displaystyle=W^{\top}\bigg{(}\int_{M}g(m)g(m)^{\top}\
d\mu(m)+\Lambda\Lambda^{\top}\bigg{)}-\int_{M}u(m)g(m)^{\top}\ d\mu(m),$

which upon rearrangement yields

$\displaystyle W$ $\displaystyle=\bigg{(}\int_{M}g(m)g(m)^{\top}\
d\mu(m)+\Lambda\Lambda^{\top}\bigg{)}^{-1}\int_{M}u(m)g(m)\ d\mu(m).$

Since this is the unique solution to $0=D\Psi(W)$, this stationary point is
unique, and we will denote it $W^{*}$. We can see it is a minimum because the
Hessian $H\Psi$ is positive definite. Next, define the map

$\displaystyle\Phi:\\{y\in C^{1}(\mathbb{R}^{P},\mathbb{R})\ |\ y\text{ is
strictly convex}\\}\to\mathbb{R}^{P}$

as the mapping on the strictly convex $C^{1}$ functions that returns their
unique minimum. We can see that $\Phi$ is continuous with respect to the
$C^{1}$ topology and Euclidean topology on $\mathbb{R}$ respectively. We
consider the family of functions $y_{\ell}\in\\{y\in
C^{1}(\mathbb{R}^{P},\mathbb{R})\ |\ y\text{ is strictly convex}\\}$ defined
by

$\displaystyle y_{\ell}(W)=\frac{1}{\ell}\bigg{(}\sum_{k=0}^{\ell-1}\rVert
W^{\top}g\circ\phi^{k}(m_{0})-u\circ\phi^{k}(m_{0})\lVert^{2}+\lVert\Lambda
W\rVert^{2}\bigg{)},$

so that by definition $W_{\ell}=\Phi(y_{\ell}(W))$ and hence

$\displaystyle\lim_{\ell\to\infty}W_{\ell}$
$\displaystyle=\lim_{\ell\to\infty}\Phi(y_{\ell}(W))$
$\displaystyle=\Phi\bigg{(}\lim_{\ell\to\infty}y_{\ell}(W)\bigg{)}$
$\displaystyle=\Phi\bigg{(}\lVert
W^{\top}g-u\rVert_{L^{2}(\mu)}^{2}+\lVert\Lambda W\rVert^{2}\bigg{)}=W^{*}$

where we have used, respectively, continuity of $\Phi$ and the Ergodic
Theorem. ∎

######  Remark 5.3.2.

The expression

$\displaystyle W^{*}$ $\displaystyle=\bigg{(}\int_{M}g(m)g(m)^{\top}\
d\mu(m)+\Lambda\Lambda^{\top}\bigg{)}^{-1}\int_{M}u(m)g(m)\ d\mu(m)$

is reminiscent of the Gauss normal equations for least squares regression.

####  5.3.2 Linear Universal Approximators

In order to approximate the arbitrary dynamics of $\phi$ via the observation
function $\omega$ using state space systems, we require that the state space
maps $F$ possess some sort of universal approximation property. Thus, we will
define a class of _linear universal approximators_ with respect to an
arbitrary complete norm $\lVert\cdot\rVert$. Every class of linear universal
approximators contains maps, which after composition with another suitable
map, forms a state map.

######  Definition 5.3.3.

Let $\mathcal{F}$ be a sequence of maps
$\\{F_{P}\\}:\mathbb{R}^{N}\times\mathbb{R}^{d}\to\mathbb{R}^{P}$. Let
$C\subset\mathbb{R}^{N}$ and $K\subset\mathbb{R}^{d}$ be vectors and let
$\Omega(C\times K,\mathbb{R})$ be a Banach space of real valued functions on
$C\times K$, with norm denoted $\lVert\cdot\rVert_{\Omega}$. If, for any
$g\in\Omega(C\times K,\mathbb{R})$ and any $\epsilon>0$ there exists an
$P_{0}\in\mathbb{N}$ such that for any $P>P_{0}$ there exists a
$W\in\mathbb{R}^{P}$ such that

$\displaystyle\rVert W^{\top}F_{P}-g\lVert_{\Omega}<\epsilon$

then we say that $\mathcal{F}$ is a class of _linear universal approximators_
on $\Omega(C\times K,\mathbb{R})$

A widely used class of linear universal approximators is the class of Echo
State Networks with randomly initialised internal weights, as shown by the
following result.

######  Theorem 5.3.4.

Let $\mathcal{F}$ denote the sequence of maps
$\\{F_{P}\\}:\mathbb{R}^{N}\times\mathbb{R}^{d}\to\mathbb{R}^{P}$ defined by

$\displaystyle F_{P}(x,z)=\sigma(Ax+Cz+b)$

where

  * •

$\sigma\in C^{1}(\mathbb{R})$ is $1$-finite

  * •

$A$ is a $P\times N$ random matrix, where $P>N$ and the first $N$ rows of $A$
form an $N\times N$ random submatrix with 2-norm less than 1 almost surely.
The $j^{\mathrm{th}}$ row of $A$ (where $j>N$), denoted $A_{j}$, is a random
variable with full support on $(\mathbb{R}^{N})^{\top}$

  * •

$C$ is a $P\times d$ random matrix with $j^{\mathrm{th}}$ row $C_{j}$, a
random variable with full support on $(\mathbb{R}^{d})^{\top}$

  * •

$b$ is a random $P$-vector with $j\mathrm{th}$ entry $b_{j}$, a random
variable with full support on $\mathbb{R}$.

Let $C\times K$ be an arbitrary compact subset of
$\mathbb{R}^{N}\times\mathbb{R}^{d}$. Then, almost surely, $\mathcal{F}$ is a
class of linear universal approximators on $L^{2}(C\times K,\mathbb{R})$.

###### Proof.

Fix $g\in L^{2}(C\times K,\mathbb{R})$ and $\epsilon>0$. Then for any
$\alpha\in(0,1)$, it follows from the Random Universal Approximation (Theorem
5.1.4) that there exists a $P_{0}\in\mathbb{N}$ such that for any $T>T_{0}$
there exists a $W\in\mathbb{R}^{P}$ such that with probability at least
$\alpha$,

$\displaystyle\rVert W^{\top}F_{P}-g\lVert_{L^{2}}<\epsilon,$

hence $\mathcal{F}$ is a class of linear universal approximators. Since
$\mathcal{F}$ is a class of linear universal approximators for any
$\alpha\in(0,1)$, $\mathcal{F}$ is almost surely a class of linear universal
approximators. ∎

To construct such an ESN in practice, we create a reservoir map
$F:\mathbb{R}^{P}\times\mathbb{R}^{d}\to\mathbb{R}^{P}$ by defining

$\displaystyle F(x,z)=\sigma\big{(}[A,0]x+Cz+b\big{)}$

where $[A,0]$ is the $P\times P$ matrix where the first $N$ columns form the
matrix $A$ and the remaining $P-N$ columns are 0. Suppose we truncate at $N$
the state vectors $x\in\mathbb{R}^{P}$ by applying the canonical projection
$\pi:\mathbb{R}^{P}\to\mathbb{R}^{N}$ onto the first $N$ coordinates, ignoring
the remainder, and denote the truncation $\pi(x)=\bar{x}\in\mathbb{R}^{N}$.
The dynamics of the truncated vectors $\bar{x}$ are given by the (state
contracting) state space system $\pi\circ
F_{P}:\mathbb{R}^{N}\times\mathbb{R}^{d}\to\mathbb{R}^{N}$, which is also an
ESN and is defined by

$\displaystyle\pi\circ
F_{P}(\bar{x},z)=\sigma(\bar{A}\bar{x}+\bar{C}z+\bar{b}).$

Here, the $N\times N$ reservoir matrix $\bar{A}$ is created by truncating at
$N$ the rows and columns of $A$. The $N\times d$ input matrix $\bar{C}$ is
created by truncating at $N$ the rows of $C$. The $N$-vector $\bar{b}$ is
created by truncating at $N$ the entries of $b$. We conclude that Echo State
Networks with (appropriately chosen) randomly generated internal weights are a
class of linear universal approximators that each give rise to a state
synchronisation map.

We demanded that the $P\times P$ reservoir matrix take the form $[A,0]$,
whereas in practice, the reservoir matrix does not have this structure. We
imposed this condition to simplify the proofs, but we believe, based on
numerical evidence in the literature, that this choice of shape is not
necessary.

There is one more technical lemma we will include here before presenting the
main theorem (Theorem 5.3.6) of this section. Recall that topological spaces
have a natural Borel sigma algebra and are therefore measurable spaces. On
such spaces we can integrate real valued functions. If $A$ and $B$ are
homeomorphic topological spaces, then integration on $A$ is essentially the
same as integration on $B$. We use this observation in Theorem 5.3.6 to move
between integration on the topological space $M$ to integration on the image
$f(M)$. This demands the highly non-trivial assumption that the GS $f$ is a
homeomorphism. The observation is made formal in the following lemma.

######  Lemma 5.3.5.

(Change of variables) Let $A,B$ be homeomorphic topological spaces and suppose
$y\in\text{Hom}(A,B)$. The topologies on $A,B$ induce Borel sigma algebras
$\mathscr{A},\mathscr{B}$ on $A,B$ respectively. Let $\mu_{A}$ be a measure on
$A$ and $\mu_{B}$ a measure on $B$ (called the pushforward measure) defined by
$\mu_{B}(b)=\mu_{A}(y^{-1}(b))$ for all $b\in\mathscr{B}$. Then for any
$\mu_{B}$-measurable function $g:B\to\mathbb{R}$ it follows that

$\displaystyle\int_{A}g\circ y\ d\mu_{A}=\int_{B}g\ d\mu_{B}.$

###### Proof.

This is a special case of Theorem 3.6.1 in Bogachev. ∎

####  5.3.3 Linear Universal Approximators Trained by Least Squares

Before we finally plunge into the statement and proof of the main theorem, we
will describe the result in words. Suppose we have an ergodic dynamical system
$\phi:M\to M$, which we observe via the function $\omega:M\to\mathbb{R}^{d}$
and that our goal is to approximate a target function $u:M\to\mathbb{R}$.
Suppose we have at our disposal a class $\mathcal{F}$ of linear universal
approximating state maps. For example, $\mathcal{F}$ could be a collection of
arbitrarily high dimensional ESNs. Make the additional (and non trivial)
assumption that the state maps give rise to a GS that is homeomorphic onto its
image. Suppose then that the state map $F$ is driven with observations of a
trajectory $z_{k}=\omega\circ\phi^{k}(m_{0})$ originating from a $\mu$-generic
point $m_{0}$. This creates a sequence of reservoir states $x_{k}$ that
satisfy

$\displaystyle x_{k+1}=F(x_{k},z_{k}).$

We also have a sequence of scalar targets $u\circ\phi^{k}(m_{0})$, which are
called _labels_ in the supervised learning parlance.

Suppose we use regularised least squares regression to minimise the difference
between the linear mapping on the reservoir states $W^{\top}x_{k}$ (which are
effectively our observations) and the targets $u\circ\phi^{k}(m_{0})$. Then we
can conclude that the ergodic average difference between the mapping on the
data and the target map $u$ can be made smaller than the arbitrary threshold
$\epsilon$. This requires that the trajectory length $\ell$ and state map
dimension $P$ are sufficiently large, while ensuring the regularisation
parameter $\lambda>0$ is sufficiently small.

Lastly, before stating the theorem (Theorem 5.3.6), we remark that a notable
weakness of the result is its non-constructive nature; the actual values for
$\ell$, $P$ and $\lambda$ are not computed in terms of $\epsilon$.

In the remainder of this subsection we state and prove the theorem itself.

######  Theorem 5.3.6.

Let $M$ be a topological space, and suppose that $\phi\in\text{Hom}(M)$ is
ergodic with invariant measure $\mu$. Let $m_{0}$ be a $\mu$-generic point in
$M$. Let $\omega\in C^{0}(M,\mathbb{R}^{d})$ be the observation function and
suppose that $u\in L^{2}(\mu)(M,\mathbb{R})$ is the target function we wish to
approximate.

Suppose that $\mathcal{F}=\\{F_{P}\\}_{P\in\mathbb{N}}$ is a class of linear
universal approximators on $L^{2}(C\times K,\mathbb{R})$ on every compact
$C\subset\mathbb{R}^{N},K\subset\mathbb{R}^{d}$. Let
$(s_{P})_{P\in\mathbb{N}}:\mathbb{R}^{P}\to\mathbb{R}^{N}$ be a sequence of
maps. Suppose (for each large enough $P$) that the reservoir map $s_{P}\circ
F_{P}:\mathbb{R}^{N}\times\mathbb{R}^{d}\to\mathbb{R}^{N}$ admits a GS
$f\in\text{Hom}(M,f(M))$. For each $P,\ell\in\mathbb{N}$, let
$\Lambda\in\mathbb{M}_{P\times P}(\mathbb{R})$, let $\lambda>0$, and let
$W_{\ell}\in\mathbb{R}^{P}$ be the vector obtained by minimising the
regularised least squares difference

$\displaystyle\sum_{k=0}^{\ell-1}\rVert
W^{\top}F_{P}(f\circ\phi^{k-1}(m_{0}),\omega\circ\phi^{k}(m_{0}))-u\circ\phi^{k}(m_{0})\lVert^{2}+\lambda\lVert\Lambda
W\rVert^{2}.$

Then, for any $\epsilon>0$, there exists $\lambda^{*}>0$ and
$\ell_{0},P_{0}\in\mathbb{N}$ such that for all $\lambda\in(0,\lambda^{*})$
and $\ell>\ell_{0},P>P_{0}$

$\displaystyle\lVert
W_{\ell}^{\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}<\epsilon.$

###### Proof.

Let $y:M\to y(M)\subset\mathbb{R}^{N}\times\mathbb{R}^{d}$ be defined by

$\displaystyle y(m)=(f\circ\phi^{-1}(m),\omega(m))\quad\forall\,m\in M$

and note that $F_{P}(f\circ\phi^{-1},\omega)=F_{P}\circ y$ and that
$y\in\text{Hom}(M,y(M))$ because $f\in\text{Hom}(M,f(M))$. Now fix
$\epsilon>0$. Let $\mu^{\prime}$ be a measure defined on
$y(M)\subset\mathbb{R}^{N}\times\mathbb{R}^{d}$ by
$\mu^{\prime}(\sigma)=\mu(y^{-1}(\sigma))$ for all measurable subsets $\sigma$
of $f(M)$. Using the assumption that $\mathcal{F}$ is a class of linear
universal approximators, we can choose $P_{0}$ sufficiently large that for any
$P>P_{0}$ there exists $\bar{W}\in\mathbb{R}^{P}$ such that

$\displaystyle\lVert\bar{W}^{\top}F_{P}-u\circ
y^{-1}\rVert_{L^{2}(\mu^{\prime})}^{2}<\frac{\epsilon}{3},$

hence (by lemma 5.3.5)

$\displaystyle\lVert\bar{W}^{\top}F_{P}\circ
y-u\rVert_{L^{2}(\mu)}^{2}=\lVert\bar{W}^{\top}F_{P}-u\circ
y^{-1}\rVert_{L^{2}(\mu^{\prime})}^{2}<\frac{\epsilon}{3}.$

Now let

$\displaystyle\lambda^{*}=\frac{\epsilon}{3\lVert\bar{W}\rVert^{2}}$

and fix $\lambda\in(0,\lambda^{*})$. Define the sequence
$(W_{\ell})_{\ell\in\mathbb{N}}$ such that, for each $\ell\in\mathbb{N}$, the
vector $W_{\ell}\in\mathbb{R}^{P}$ is the unique minimiser of the regularised
least squares difference

$\displaystyle\frac{1}{\ell}\bigg{(}\sum_{k=0}^{\ell-1}\rVert
W^{\top}F_{P}(f\circ\phi^{k-1}(m_{0}),\omega\circ\phi^{k}(m_{0}))-u\circ\phi^{k}(m_{0})\lVert^{2}+\lambda\lVert\Lambda
W\rVert^{2}\bigg{)}.$

By lemma 5.3.1, $(W_{\ell})_{\ell\in\mathbb{N}}$ converges as $\ell\to\infty$
to $W^{*}$ which minimises

$\displaystyle\lVert
W^{\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}+\lambda\lVert\Lambda
W\rVert^{2}.$

Now we choose $\ell_{0}$ such that for all $\ell>\ell_{0}$

$\displaystyle\rVert
W_{\ell}^{\top}F_{P}(f\circ\phi^{-1},\omega)-W^{*\top}F_{P}(f\circ\phi^{-1},\omega)\lVert_{L^{2}(\mu)}^{2}<\frac{\epsilon}{3}.$

Now the proof proceeds directly

$\displaystyle\lVert
W_{\ell}^{\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}$
$\displaystyle=$ $\displaystyle\lVert
W_{\ell}^{\top}F_{P}(f\circ\phi^{-1},\omega)-W^{*\top}F_{P}(f\circ\phi^{-1},\omega)+W^{*\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}$
$\displaystyle\leq$ $\displaystyle\lVert
W_{\ell}^{\top}F_{P}(f\circ\phi^{-1},\omega)-W^{*\top}F_{P}(f\circ\phi^{-1},\omega)\rVert_{L^{2}(\mu)}^{2}+\lVert
W^{*\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}$
$\displaystyle<$ $\displaystyle\frac{\epsilon}{3}+\lVert
W^{*\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}$
$\displaystyle\leq$ $\displaystyle\frac{\epsilon}{3}+\lVert
W^{*\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}+\lambda\lVert\Lambda
W^{*}\rVert^{2}$ $\displaystyle\leq$
$\displaystyle\frac{\epsilon}{3}+\lVert\bar{W}^{\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}+\lambda\lVert\Lambda\bar{W}\rVert^{2}$
$\displaystyle<$
$\displaystyle\frac{\epsilon}{3}+\frac{\epsilon}{3}+\lVert\bar{W}^{\top}F_{P}(f\circ\phi^{-1},\omega)-u\rVert_{L^{2}(\mu)}^{2}$
$\displaystyle=$
$\displaystyle\frac{\epsilon}{3}+\frac{\epsilon}{3}+\lVert\bar{W}^{\top}F_{P}\circ
y-u\rVert_{L^{2}(\mu)}^{2}$ $\displaystyle<$
$\displaystyle\frac{\epsilon}{3}+\frac{\epsilon}{3}+\frac{\epsilon}{3}=\epsilon.$

∎

####  5.3.4 Convergence rate of the time average to the space average

Theorem 5.3.6 guarantees, under appropriate conditions, that with sufficiently
many neurons $P$ and a sufficiently many training data $\ell$ we can obtain an
arbitrarily good $L^{2}(\mu)$ approximation of a target function $u$. It is
natural to wonder how many training data are required to achieve a given
$L^{2}(\mu)$ approximation. To answer this, we turn our attention to the
convergence rate of the time average to the space average

$\displaystyle\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}s\circ\phi^{k}(m_{0})=\int_{M}s\
d\mu$ (5.2)

as the timespan over which training data is collected grows. We want a uniform
estimate for the rate of convergence for $s$ over all ergodic maps $\phi$.
Unfortunately, no such estimate exists. Kachurovskii1996 presents negative
results that (in the author’s words) _leave no hope that estimates of the rate
of convergence depending only on the averaged function $s$ can be obtained in
ergodic theorems_. The negative results presented by Kachurovskii1996 prove
that the amount of training data required is strictly dependant on the
dynamical system.

Though we cannot say exactly how many data points we need for a good
$L^{2}(\mu)$ approximation, the central limit theorem for ergodic dynamical
systems suggests that for an initial point chosen uniformly at random over the
invariant measure of $\phi$, the difference between the sum of random
variables that is the finite time average and the space average converges in
distribution to normal distribution with mean zero and standard deviation
$1/\sqrt{\ell}$. This is made precise by the central limit theorem for ergodic
dynamical systems. Before we state the theorem, we recall the definition of
Hölder continuity.

######  Definition 5.3.7.

(Hölder continuous) Let $(M,d)$ be a metric space. A map $s:M\to\mathbb{R}$ is
called _Hölder continuous_ if there exist constants $p\in(0,1]$ and $K>0$ such
that

$\displaystyle\lVert s(m)-s(m^{\prime})\rVert\leq Kd(m,m^{\prime})^{p}$

for all $m,m^{\prime}\in M$.

######  Theorem 5.3.8.

(Central limit theorem for ergodic dynamical systems) Let $\phi:M\to M$ be
ergodic with respect to the probability space $(M,\Sigma,\mu)$. Let $X_{0}$ be
a uniform random variable with respect to the space $(M,\Sigma,\mu)$. Let
$s\in L^{1}(\mu)(M,\mathbb{R})$ be Hölder continuous and denote the space
average of $s$ by

$\displaystyle\mathbb{E}[s]:=\int_{M}s\ d\mu.$

Let the random variables $X_{j}:=\phi^{j}(X_{0})$ for $j=0,\ldots,\ell-1$, and
denote the partial sum $S_{\ell}:=s(X_{0})+\cdots+s(X_{\ell-1})$. Then, for
some $\beta>0$, the partial sum $S_{\ell}$ satisfies the central limit
theorem:

$\displaystyle\lim_{\ell\to\infty}\mu\bigg{(}\bigg{\\{}\frac{S_{\ell}-\ell\mathbb{E}[s]}{\sqrt{\ell}}\leq
z\bigg{\\}}\bigg{)}=\frac{1}{\sqrt{2\pi}\beta}\int_{-\infty}^{z}\mathrm{e}^{-\frac{\tau^{2}}{2\beta^{2}}}\
d\tau$

almost surely, or in other words $(S_{\ell}-\ell\mathbb{E}[s])/\sqrt{\ell}$
converges in law to $\mathcal{N}(0,\beta^{2})$.

###### Proof.

ErgodicTheory2010. ∎

To see the connection between the central limit theorem and the work in this
paper, we observe first of all that the CLT holds in higher dimensions. Then
we consider the map $s$ that returns the matrix–vector pair

$\displaystyle s(m_{0})$
$\displaystyle=\bigg{(}\big{[}f(m_{0})f^{\top}(m_{0})+\Lambda\Lambda^{\top}\big{]},f(m_{0})u(m_{0})\bigg{)}$
$\displaystyle=:(B_{0},v_{0}),$

and define a sequence of pairs $(B_{\ell},v_{\ell})_{\ell\in\mathbb{N}}$ with
$\ell$th pair

$\displaystyle(B_{\ell},v_{\ell}):=\frac{1}{\ell}\sum_{k=0}^{\ell-1}s\circ\phi^{k}(m_{0}).$

Then it follows that

$\displaystyle W_{\ell}=B_{\ell}^{-1}v_{\ell}$

is the linear readout layer obtained by regularised least squares regression
using $\ell$ data points. Furthermore, it follows from the central limit
theorem that for random initial points $m_{0}$ (distributed uniformly with
respect to the invariant measure $\mu$) the sequence
$(B_{\ell},v_{\ell})_{\ell\in\mathbb{N}}$ converges in law to a (multivariate)
normal distribution, with standard deviation converging to 0 with order
$1/\sqrt{\ell}$, and mean $(B,v)$ which satisfies

$\displaystyle W^{*}=B^{-1}v.$

We note that the convergence of $(B_{\ell},v_{\ell})_{\ell\in\mathbb{N}}$ to
$(B,v)$ with order $1/\sqrt{\ell}$ does not necessarily imply that
$(W_{\ell})_{\ell\in\mathbb{N}}$ converges to $W^{*}$ at the same rate.

###  5.4 The Lorenz attractor is stably mixing

We have shown that we can approximate, in the $L^{2}(\mu)$ sense, any target
function on an ergodic dynamical system using an ESN and Tikhonov least
squares. This partially explains the success enjoyed by Jaeger2001, 1556081,
416607, 4118282, 5645205, Pathak2017, Lokse2017, YEO2019671, Ashesh_2019,
Vlac_2019, and embedding_and_approximation_theorems. Many authors including
Ashesh_2019 successfully predict the future observations of the Lorenz system,
while Pathak2017, Vlac_2019, and embedding_and_approximation_theorems
additionally recover invariants including Lyapunov exponents, fixed point
eigenvalues and homology groups. The authors are successful in their numerical
experiments because the Lorenz attractor is _mixing_ which implies it is
ergodic, suggesting the conditions Theorem 5.3.6 hold and we can $L^{2}(\mu)$
approximate target functions on the Lorenz attractor.

The proof by Tucker2002 that the Lorenz attractor is mixing was a tremendous
achievement, and resolved Smale’s $14^{\mathrm{th}}$ problem

_‘Is the dynamics of the ordinary differential equations of Lorenz (1963) that
of the geometric Lorenz attractor of Williams, Guckenheimer and Yorke? ’_
(Smale1998).

Tucker’s proof built upon the works of 1977DoSSR.234..336A,
Structural_stability_of_Lorenz_attractors, pesin_1992, PMIHES_1979__50__73_0,
and TUCKER19991197. The ideas discussed in these papers go far beyond the
scope of this thesis, and I will restrict attention to simpler results about
mixing dynamical systems that are directly relevant to the results presented
here.

######  Definition 5.4.1.

(Mixing) Let $\phi:M\to M$ be a measure preserving transformation on the
measure space $(M,\Sigma,\mu)$ with $\mu(M)=1$. Then $\phi$ is mixing if for
any $A,B\in\Sigma$

$\displaystyle\lim_{\ell\to\infty}\mu\big{(}A\cap\phi^{-\ell}(B)\big{)}=\mu(A)\mu(B).$

######  Lemma 5.4.2.

(Mixing implies ergodic) Let $\phi:M\to M$ be a measure preserving
transformation on the measure space $(M,\Sigma,\mu)$ with $\mu(M)=1$. Suppose
$\phi$ is mixing, then $\phi$ is ergodic.

###### Proof.

Suppose $\phi$ is mixing and $A,B\in\Sigma$. Then

$\displaystyle\lim_{\ell\to\infty}\mu\big{(}A\cap\phi^{-\ell}(B)\big{)}$
$\displaystyle=\mu(A)\mu(B)$
$\displaystyle\implies\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}\mu\big{(}A\cap\phi^{-k}(B)\big{)}$
$\displaystyle=\mu(A)\mu(B)$
$\displaystyle\implies\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}\mu\big{(}A\cap\phi^{-k}(A)\big{)}$
$\displaystyle=\mu(A)^{2},$ (5.3)

where we have set $A=B$ to derive the last line. Now suppose that $A$ is
$\phi$-invariant, i.e. $A=\phi^{-1}(A)$. Then the left-hand side of (5.3) is
precisely $\mu(A)$, and hence (5.3) reduces to the statement that
$\mu(A)=\mu(A)^{2}$ hence $\mu(A)=1$ or $\mu(A)=0$, so any invariant set has
either full or zero measure, and so $\phi$ is ergodic. ∎

######  Definition 5.4.3.

(Stably mixing) Let $\phi:M\to M$ be a measure preserving transformation on
the measure space $(M,\Sigma,\mu)$ with $\mu(M)=1$. Then $\phi$ is stably
mixing if sufficiently small $C^{1}$ perturbations of $\phi$ are mixing.

######  Theorem 5.4.4.

The doi:10.1175/1520-0469(1963)020<0130:DNF>2.0.CO;2 system

$\begin{array}[]{ll}\dot{\xi}&=\sigma(\upsilon-\xi)\\\
\dot{\upsilon}&=\xi(\rho-\zeta)-\upsilon\\\
\dot{\zeta}&=\xi\upsilon-\beta\zeta\end{array}$ (5.4)

with parameters $\sigma=10$, $\beta=8/3$, $\rho=28$ admits a robust attractor
that is stably mixing.

###### Proof.

Luzzatto2005 ∎

Since the Lorenz attractor is stably mixing, so is any sufficiently good
$C^{1}$ approximation to the evolution operator $\phi$, obtained by numerical
methods. Consequently, a numerically approximated Lorenz system is ergodic, by
Lemma 5.4.2. Thus, we expect that an ESN, trained using least squares fitting,
with Tikhonov regularisation, on a sequence of observations of a numerically
integrated trajectory of the Lorenz attractor will $L^{2}(\mu)$–approximate
arbitrary target functions on the attractor.

###  5.5 Online Learning

Most ESN practitioners estimate the minimiser $W^{*}$ by collecting a long
trajectory of reservoir states $x_{k}$, then solve the regularised least
squares problem to find $W_{\ell}$ using their favourite numerical algebra
package. This is an example of _offline learning_ because the learning happens
after the training is collected. Offline learning requires that the entire set
of reservoir states $x_{k}$ are stored in memory, and subject to large matrix
computations.

An alternative approach is _online learning_ , where learning occurs
dynamically as new data as comes in. Online learning methods typically do not
require that the entire training trajectory is stored in memory, nor do they
require large (memory intensive!) matrix operations. This gives them an
obvious advantage over offline methods.

Furthermore, online learning algorithms are a more a realistic model of
biological neural networks - because the connection strength between
biological neurons varies in real time in response to stimulus. Indeed,
biologically speaking, offline learning is completely implausible, as this
would entail the states of a biological brain being stored somewhere
‘external’. Operations would be applied to these externally stored neuronal
states, and the results then be transmitted back into the brain. With this
motivation, we will study the online learning algorithm

$\displaystyle W_{k+1}$
$\displaystyle=(1-\alpha_{k}\lambda)W_{k}-\alpha_{k}g\circ\phi^{k}(m_{0})(W^{\top}_{k}g\circ\phi^{k}(m_{0})-u\circ\phi^{k}(m_{0}))$
(5.5)

with $(\alpha_{k})_{k\in\mathbb{N}}$ a strictly positive real sequence, and
remaining terms defined in lemma 5.3.1. The algorithm is essentially
stochastic gradient descent and is discussed in numerous works including
Adaptive_Algorithms, 10.1007/978-3-540-72927-3_23, Borkar2009, and Chen2019.
The behavior of the sequence $(\alpha_{k})_{k\in\mathbb{N}}$ often called the
_learning rate_ or _learning parameter_. If
$(\alpha_{k})_{k\in\mathbb{N}}=\alpha>0$ is a constant sequence, then we call
$\alpha$ the learning parameter. In the case that
$(\alpha_{k})_{k\in\mathbb{N}}$ converges to 0 rapidly, the convergence is
called a fast learning rate, and slow convergence is called a slow learning
rate. If $(\alpha_{k})_{k\in\mathbb{N}}$ diverges then something like the
opposite of learning is achieved.

In what follows we will show that if $(\alpha_{k})_{k\in\mathbb{N}}=\alpha>0$
is a constant sequence, then the algorithm does not converge in general, but
in the limit as $k\to\infty$ the algorithm returns $W^{*}$ _on average_ (in
the ergodic sense). Furthermore, we establish a bound on the _variance_ of the
weights $W_{k}$ as $k\to\infty$. Next we show that if $\alpha_{k}=1/k$ then
algorithm (5.5) converges to $W^{*}$. We will proceed with preliminary results
in the case where $(\alpha_{k})_{k\in\mathbb{N}}$ is a constant sequence.

####  5.5.1 Fixed learning parameter $\alpha$

######  Lemma 5.5.1.

Let $V\subset\mathbb{R}^{P}$ be a bounded set, $\lambda>0$ be the
regularisation parameter, and

$\displaystyle 0<\alpha<\frac{1}{\lambda+\sup_{v\in V}\lVert v\rVert^{2}}.$

Then the reservoir map
$F:\mathbb{R}^{P}\times(V\times\mathbb{R})\to\mathbb{R}^{P}$ defined by

$\displaystyle F(W;v,z)$ $\displaystyle=(1-\alpha\lambda)W-\alpha
v(W^{\top}v-z)$

is state contracting.

###### Proof.

First, note that upon rearrangement

$\displaystyle F(W;v,z)=[I-\alpha(vv^{\top}+\lambda I)]W+\alpha vz.$

Then we can see that

$\displaystyle\lVert F(W;v,z)-F(Y;v,z)\rVert=$
$\displaystyle\lVert[I-\alpha(vv^{\top}+\lambda I)](W-Y)\rVert$
$\displaystyle\leq$ $\displaystyle\rho[I-\alpha(vv^{\top}+\lambda I)]\ \lVert
W-Y\rVert$

where $\rho[\cdot]$ denotes the spectral radius. Now the matrix
$[vv^{\top}+\lambda I]$ has exactly 2 distinct eigenvalues, $\lambda$ and
$\lambda+\lVert v\rVert^{2}$. Therefore, the matrix $\alpha[vv^{\top}+\lambda
I]$ has exactly 2 eigenvalues $\alpha\lambda$ and $\alpha(\lambda+\lVert
v\rVert^{2})$. Both of these lie in $(0,1)$ by construction, so
$\rho[I-\alpha(vv^{\top}+\lambda I)]\in(0,1)$ and we are done. ∎

######  Theorem 5.5.2.

Let $(M,\Sigma)$ be a measurable space, and suppose that $\phi:M\to M$ is
ergodic with invariant measure $\mu$. Let $m_{0}$ be a $\mu$-generic point in
$M$. Let $g\in C^{0}(M,\mathbb{R}^{P})$ be an observation function and suppose
that $u\in L^{2}(\mu)(M,\mathbb{R})$ is a target function we wish to
approximate. Suppose that

$\displaystyle 0<\alpha<\frac{1}{\lambda+\sup_{m\in M}\lVert g(m)\rVert^{2}}.$

Then there exists a unique GS $h\in C^{0}(M,\mathbb{R}^{P})$, such that for
generic initial $m_{0}\in M$ and initial $W_{0}\in\mathbb{R}^{P}$ the
iteration (5.5) converges to $h\circ\phi^{k}(m_{0})$ as $k\to\infty$.
Furthermore the GS $h$ satisfies

$\displaystyle\int_{M}[gg^{\top}+\lambda I](W^{*}-h)\ d\mu=0$

and

$\displaystyle\lVert
W^{*}-h\rVert_{L^{2}(\mu)}\leq\frac{\lVert[gg^{\top}+\lambda
I]W^{*}-gu\rVert_{L^{2}(\mu)}}{\lambda}.$

###### Proof.

From Theorem 3.5.5 and Lemma 5.5.1 it follows that for generic initial states
$m_{0}\in M$ and $W_{0}\in\mathbb{R}^{P}$ the iteration (5.5) converges to
$h\circ\phi^{k}(m_{0})$ as $k\to\infty$. Furthermore, in the limit
$k\to\infty$ we have

$\displaystyle h\circ\phi$ $\displaystyle=(1-\alpha\lambda)h-\alpha
g(h^{\top}g-u),$

which upon rearrangement yields

$\displaystyle h\circ\phi$ $\displaystyle=h-\alpha[(gg^{\top}+\lambda
I)]h+\alpha gu.$

Then integrating both sides we have

$\displaystyle\int_{M}h\circ\phi\ d\mu$ $\displaystyle=\int_{M}h\
d\mu-\alpha\int_{M}[gg^{\top}+\lambda I]h\ d\mu+\alpha\int_{M}gu\ d\mu$

so, using the $\phi$-invariance of the measure $\mu$, we have

$\displaystyle\int_{M}h\ d\mu$ $\displaystyle=\int_{M}h\
d\mu-\alpha\int_{M}[gg^{\top}+\lambda I]h\ d\mu+\alpha\int_{M}gu\ d\mu$

hence

$\displaystyle\int_{M}[gg^{\top}+\lambda I]h\ d\mu=\int_{M}gu\ d\mu.$

We now recall from Lemma 5.3.1 that

$\displaystyle\int_{M}gu\ d\mu=\int_{M}[gg^{\top}+\lambda I]W^{*}\ d\mu$

so

$\displaystyle\int_{M}[gg^{\top}+\lambda I]h\ d\mu=\int_{M}[gg^{\top}+\lambda
I]W^{*}\ d\mu$

hence

$\displaystyle 0$ $\displaystyle=\int_{M}[gg^{\top}+\lambda I](h-W^{*})\
d\mu.$

Now we recall

$\displaystyle h\circ\phi$ $\displaystyle=(1-\alpha\lambda)h-\alpha
g(h^{\top}g-u),$

which upon rearrangement yields

$\displaystyle h\circ\phi-W^{*}$ $\displaystyle=(I-\alpha[gg^{\top}+\lambda
I])(h-W^{*})-\alpha([gg^{\top}+\lambda I]W^{*}-gu)$

hence

$\displaystyle\lVert h-W^{*}\rVert_{L^{2}(\mu)}$ $\displaystyle=\lVert
h\circ\phi-W^{*}\rVert_{L^{2}(\mu)}$
$\displaystyle=\lVert(I-\alpha[gg^{\top}+\lambda
I])(h-W^{*})+\alpha([gg^{\top}+\lambda I]W^{*}-gu)\lVert_{L^{2}(\mu)}$
$\displaystyle\leq\lVert(I-\alpha[gg^{\top}+\lambda
I])(h-W^{*})\rVert_{L^{2}(\mu)}+\alpha\rVert[gg^{\top}+\lambda
I]W^{*}-gu\lVert_{L^{2}(\mu)}$
$\displaystyle\leq\rho(I-\alpha[gg^{\top}+\lambda
I])\lVert(h-W^{*})\rVert_{L^{2}(\mu)}+\alpha\rVert[gg^{\top}+\lambda
I]W^{*}-gu\lVert_{L^{2}(\mu)}.$

where $\rho(\cdot)$ is the spectral radius. Now the eigenvalues of
$\alpha[gg^{\top}+\lambda I]$ are $\alpha\lambda$ and $\alpha(\lambda+\lVert
g\rVert^{2})$ which both lie in $(0,1)$ by construction, so

$\displaystyle\rho(I-\alpha[gg^{\top}+\lambda I])=1-\alpha\lambda.$

Therefore we have

$\displaystyle\lVert h-W^{*}\rVert_{L^{2}(\mu)}$
$\displaystyle\leq\lVert(1-\alpha\lambda)(h-W^{*})\rVert_{L^{2}(\mu)}+\alpha\rVert[gg^{\top}+\lambda
I]W^{*}-gu\lVert_{L^{2}(\mu)}$
$\displaystyle=(1-\alpha\lambda)\lVert(h-W^{*})\rVert_{L^{2}(\mu)}+\alpha\rVert[gg^{\top}+\lambda
I]W^{*}-gu\lVert_{L^{2}(\mu)}.$

We consider the first and last lines together and then rearrange to yield

$\displaystyle\lVert
W^{*}-h\rVert_{L^{2}(\mu)}\leq\frac{\lVert[gg^{\top}+\lambda
I]W^{*}-gu\rVert_{L^{2}(\mu)}}{\lambda}.$

∎

We showed in theorem 5.5.2 that if $(\alpha_{k})_{k\in\mathbb{N}}$ is a
sufficiently small constant sequence, algorithm (5.5) converges to $W^{*}$ in
some ergodic average sense. We will show next that if we replace all
observations $g\circ\phi^{k}(m_{0})$ and targets $u\circ\phi^{k}(m_{0})$ with
the ergodic averages $\int_{M}g\ d\mu$ and $\int_{M}u\ d\mu$ then algorithm
(5.5) converges to $W^{*}$.

######  Theorem 5.5.3.

Let $(M,\Sigma)$ be a measurable space, and suppose that $\phi:M\to M$ is
ergodic with invariant measure $\mu$. Let $m_{0}$ be a $\mu$-generic point in
$M$. Let $g\in C^{0}(M,\mathbb{R}^{P})$ be an observation function and suppose
that $u\in L^{2}(\mu)(M,\mathbb{R})$ is a target function we wish to
approximate. Let $\lambda>0$ and choose $\alpha>0$ such that

$\displaystyle\rho\bigg{(}I-\alpha\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{)}\in(0,1).$

Then the map $\Phi:\mathbb{R}^{P}\to\mathbb{R}^{P}$ defined by

$\displaystyle\Phi(W)=W-\alpha\bigg{[}\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{]}W+\alpha\int_{M}gu\ d\mu$

is contracting, and admits a unique fixed point

$\displaystyle W^{*}=\bigg{[}\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{]}^{-1}\int_{M}gu\ d\mu.$

###### Proof.

The proof that $\Phi$ is contracting proceeds directly

$\displaystyle\lVert\Phi(W_{1})-\Phi(W_{2})\rVert$
$\displaystyle=\bigg{\lVert}\bigg{[}I-\alpha\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{]}(W_{1}-W_{2})\bigg{\rVert}$
$\displaystyle\leq\bigg{\lVert}I-\alpha\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{\rVert}_{2}\lVert W_{1}-W_{2}\rVert$
$\displaystyle=\rho\bigg{(}I-\alpha\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{)}\lVert W_{1}-W_{2}\rVert$ $\displaystyle=c\lVert
W_{1}-W_{2}\rVert$

where

$\displaystyle c:=\rho\bigg{(}I-\alpha\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{)}\in(0,1).$

We have shown that $\Phi$ is contracting, and therefore admits a unique fixed
point $W^{*}$ which satisfies

$\displaystyle W^{*}=\Phi(W^{*})=W^{*}-\alpha\bigg{[}\int_{M}gg^{\top}+\lambda
I\ d\mu\bigg{]}W^{*}+\alpha\int_{M}gu\ d\mu$

which is easily rearranged to

$\displaystyle W^{*}=\bigg{[}\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{]}^{-1}\int_{M}gu\ d\mu.$

∎

We can view theorem 5.5.3 as a result for the discrete time dynamical system
given by the proposed iterative scheme (5.5) for $W$. This result has a
continuous time analogue which we present next.

######  Theorem 5.5.4.

Let $(M,\Sigma)$ be a measurable space, and suppose that $\phi:M\to M$ is
ergodic with invariant measure $\mu$. Let $m_{0}$ be a $\mu$-generic point in
$M$. Let $g\in C^{0}(M,\mathbb{R}^{P})$ be an observation function and suppose
that $u\in L^{2}(\mu)(M,\mathbb{R})$ is a target function we wish to
approximate. Let $\lambda>0$.

Then the ODE

$\displaystyle\dot{W}=-\bigg{[}\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{]}W+\int_{M}gu\ d\mu$

has a globally asymptotic fixed point

$\displaystyle W^{*}=\bigg{[}\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{]}^{-1}\int_{M}gu\ d\mu.$

###### Proof.

The matrix $-\bigg{[}\int_{M}gg^{\top}+\lambda I\ d\mu\bigg{]}$ is symmetric
negative definite. The eigenvalues are therefore all real and strictly
negative. The fixed point $W^{*}$ is therefore a globally asymptotic fixed
point. ∎

####  5.5.2 Learning rate $\alpha_{k}=1/k$

If the learning rate in the iteration (5.5) is
$(\alpha_{k})_{k\in\mathbb{N}}=1/k$ then the algorithm converges to exactly
$W^{*}$. Roughly speaking, this is because the choice of learning rate
$(\alpha_{k})_{k\in\mathbb{N}}=1/k$ is not too fast or too slow. If we choose
a learning rate that is too fast, then the algorithm converges before enough
training data has been collected to a non-optimal $W\in\mathbb{R}^{P}$. On the
other hand if the learning rate is too slow, the continued influence of the
data prevents the algorithm from converging at all. The formal version of this
result follows almost immediately from a theorem by Gyorfi1980 which we
present here.

######  Theorem 5.5.5.

(Gyorfi1980) Let $\mathcal{H}$ be a real Hilbert space with norm
$\lVert\cdot\rVert_{\mathcal{H}}$. Let $B:\mathcal{H}\to\mathcal{H}$ be an
invertible, bounded, linear, symmetric and positive operator. Let
$(B_{k})_{k\in\mathbb{N}}:\mathcal{H}\to\mathcal{H}$ be a sequence of bounded
linear operators and $(v_{k}\in\mathcal{H})_{k\in\mathbb{N}}$ a sequence in
$\mathcal{H}$ such that

$\displaystyle\bigg{\lVert}\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}B_{k}-B\bigg{\rVert}_{\mathcal{H}}=0,\qquad\bigg{\lVert}\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}v_{k}-v\bigg{\rVert}_{\mathcal{H}}=0$

for some $v\in\mathcal{H}$. Then for any initial $W_{0}\in\mathcal{H}$ the
sequence

$\displaystyle W_{k+1}=W_{k}-\frac{1}{k}(B_{k}W_{k}-v_{k})$

converges to

$\displaystyle W^{*}=B^{-1}v.$

######  Corollary 5.5.6.

Let $(M,\Sigma)$ be a measurable space, and suppose that $\phi:M\to M$ is
ergodic with invariant measure $\mu$. Let $m_{0}$ be a $\mu$-generic point in
$M$. Let $g\in C^{0}(M,\mathbb{R}^{P})$ be an observation function and suppose
that $u\in L^{2}(\mu)(M,\mathbb{R})$ is a target function we wish to
approximate. Then, for any initial $W_{0}$, the iteration (5.5) with
$\alpha_{k}=1/k$

$\displaystyle W_{k+1}$
$\displaystyle=(1-\alpha_{k}\lambda)W_{k}-\alpha_{k}g\circ\phi^{k}(m_{0})(W^{\top}_{k}g\circ\phi^{k}(m_{0})-u\circ\phi^{k}(m_{0}))$

converges to

$\displaystyle W^{*}=\bigg{[}\int_{M}gg^{\top}+\lambda I\
d\mu\bigg{]}^{-1}\int_{M}gu\ d\mu.$

###### Proof.

Let

$\displaystyle B:=\bigg{[}\int_{M}gg^{\top}+\lambda I\ d\mu\bigg{]},\qquad
v:=\int_{M}gu\ d\mu,$

and

$\displaystyle
B_{k}:=\bigg{[}g\circ\phi^{k}(m_{0})(g\circ\phi^{k}(m_{0}))^{\top}+\lambda
I\bigg{]},\qquad v_{k}:=g\circ\phi^{k}(m_{0})u\circ\phi^{k}(m_{0}),$

and notice that

$\displaystyle\bigg{\lVert}\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}B_{k}-B\bigg{\rVert}_{\mathbb{R}^{P}}=0,\qquad\text{and}\qquad\bigg{\lVert}\lim_{\ell\to\infty}\frac{1}{\ell}\sum_{k=0}^{\ell-1}v_{k}-v\bigg{\rVert}_{\mathbb{R}^{P}}=0,$

by the ergodic theorem. Then the iteration (5.5) can be written as

$\displaystyle W_{k+1}$
$\displaystyle=W_{k}+\alpha_{k}\bigg{(}\bigg{[}g\circ\phi^{k}(m_{0})(g\circ\phi^{k}(m_{0}))^{\top}+\lambda
I\bigg{]}W_{k}-g\circ\phi^{k}(m_{0})u\circ\phi^{k}(m_{0})\bigg{)}$
$\displaystyle=W_{k}+\frac{1}{k}(B_{k}W_{k}-v_{k})$

which converges to

$\displaystyle W^{*}=B^{-1}v=\bigg{[}\int_{M}gg^{\top}+I\lambda\
d\mu\bigg{]}^{-1}\int_{M}gu\ d\mu$

by Theorem 5.5.5. ∎

In summary: the online learning algorithm (iteration (5.5)) discussed in
section 5.5 updates the weights $W_{k}$ at each time step $k$ according to the
reservoir state $x_{k}$ and observation $z_{k}$ made at time $k$. This is in
contrast to offline methods, like the SVD, where every past reservoir state
$x_{k}$ is stored in memory, and the estimate for $W^{*}$ is computed using a
single matrix computation involving every past reservoir state. In machine
learning problems, offline methods are typically more time-efficient than
online methods, while online methods demand much less memory.

###  5.6 Value Functions and Control

In the preceding section we have shown that whether we use online or offline
methods we can find a $W^{*}$ such that $W^{*\top}g$ is a good approximation
to the target function $u$. If $f$ is the GS associated to a reservoir map, we
can choose $g=f$. Alternatively we could choose $g=f-\gamma f\circ\phi$ where
$\gamma\in[0,1)$. To understand the significance of this, we consider the (so
called) value function $V:M\to\mathbb{R}$ defined by

$\displaystyle V:$ $\displaystyle=\sum_{k=0}^{\infty}\gamma^{k}u\circ\phi^{k}$

which returns the present value of a collection of future observations, with a
discount factor $\gamma$ which indicates that future observations further away
in time are valued less than observations nearer in the future. The value
function satisfies the following functional relationship

$\displaystyle V$
$\displaystyle=\sum_{k=0}^{\infty}\gamma^{k}u\circ\phi^{k}=u+\sum_{k=1}^{\infty}\gamma^{k}u\circ\phi^{k}=u+\sum_{k=0}^{\infty}\gamma^{k+1}u\circ\phi^{k+1}$
$\displaystyle=u+\gamma\sum_{k=0}^{\infty}\gamma^{k}u\circ\phi^{k+1}=u+\gamma\bigg{(}\sum_{k=0}^{\infty}\gamma^{k}u\circ\phi^{k}\bigg{)}\circ\phi=u+\gamma
V\circ\phi.$

Hence, the vector $W$, which we call $W^{*}$, that minimises the following

$\displaystyle\lVert W^{\top}g-u\rVert_{L^{2}(\mu)}^{2}+\lambda\lVert
W\rVert^{2}=$ $\displaystyle\lVert W^{\top}(f-\gamma
f\circ\phi)-u\rVert_{L^{2}(\mu)}^{2}+\lambda\lVert W\rVert^{2}$
$\displaystyle=$ $\displaystyle\lVert W^{\top}f-(\gamma
W^{\top}f\circ\phi+u)\rVert_{L^{2}(\mu)}^{2}+\lambda\lVert W\rVert^{2}$

results in a function $W^{*\top}f$ which is a good approximation to the value
function $V$. This value function $V$ is intimately related to infinite
horizon, discrete time control theory. We do not develop the deterministic
theory further here, but in Chapter 6 we develop a stochastic analogue to
control theory more detail.

###  5.7 Biological interpretation

In this section we are interested in finding the learning paradigm that best
describes the information processing of neurons in biological organisms. The
offline process is a completely implausible model, as this would entail the
states of a biological brain, represented by the reservoir states $x_{k}$
being stored somewhere _external to the brain_. These externally stored states
would be subject to computations and the resulting weights $W^{*}$ then would
be transmitted back into the brain.

The online process on the hand seems much more plausible. The connection
weights, which are the components of $W_{k}$, represent the connections
strength between the reservoir neurons and an output neuron, which might
influence motor function or some other physiological output
(izhikevich2007dynamical). The weights $W_{k}$ change gradually in response to
connected neurons firing more or less frequently. This is consistent with the
Hebbian learning maxim that _neurons that fire together wire together_
(lowel1992selection). The states of the brain are represented by the reservoir
states $x$, which influence the output weights $W$ connecting the brain $A$ to
the output neuron $u$.

This interpretation is highly speculative - and quite vague - and would