# Analysis of the Geometric Structure of Neural Networks and Neural ODEs via
Morse Functions

Christian Kuehn 1,2 & Sara-Viola Kuntz 1,2 0000-0002-7063-6173
0009-0000-4611-9742

( 1Technical University of Munich, School of Computation, Information and
Technology,
Department of Mathematics, Boltzmannstraße 3, 85748 Garching, Germany
2Munich Data Science Institute, Walther-von-Dyck-Straße 10, 85748 Garching,
Germany
May 15, 2024 )

###### Abstract

Besides classical feed-forward neural networks, also neural ordinary
differential equations (neural ODEs) gained particular interest in recent
years. Neural ODEs can be interpreted as an infinite depth limit of feed-
forward or residual neural networks. We study the input-output dynamics of
finite and infinite depth neural networks with scalar output. In the finite
depth case, the input is a state associated to a finite number of nodes, which
maps under multiple non-linear transformations to the state of one output
node. In analogy, a neural ODE maps a linear transformation of the input to a
linear transformation of its time-$T$ map. We show that depending on the
specific structure of the network, the input-output map has different
properties regarding the existence and regularity of critical points. These
properties can be characterized via Morse functions, which are scalar
functions, where every critical point is non-degenerate. We prove that
critical points cannot exist, if the dimension of the hidden layer is
monotonically decreasing or the dimension of the phase space is smaller or
equal to the input dimension. In the case that critical points exist, we
classify their regularity depending on the specific architecture of the
network. We show that each critical point is non-degenerate, if for finite
depth neural networks the underlying graph has no bottleneck, and if for
neural ODEs, the linear transformations used have full rank. For each type of
architecture, the proven properties are comparable in the finite and in the
infinite depth case. The established theorems allow us to formulate results on
universal embedding, i.e. on the exact representation of maps by neural
networks and neural ODEs. Our dynamical systems viewpoint on the geometric
structure of the input-output map provides a fundamental understanding, why
certain architectures perform better than others.

Keywords: neural networks, neural ODEs, Morse functions, universal embedding

MSC2020: 34A34, 58K05, 58K45, 68T07

††✉<EMAIL_ADDRESS>(Christian Kuehn)
✉<EMAIL_ADDRESS>(Sara-Viola Kuntz, corresponding author)

###### Contents

  1. 1 Introduction
  2. 2 Overview and Results
    1. 2.1 Classification of Critical Points
    2. 2.2 Universal Embedding Property
  3. 3 Feed-Forward Neural Networks
    1. 3.1 Special Architectures
    2. 3.2 Equivalent Neural Network Architectures
    3. 3.3 Existence of Critical Points
    4. 3.4 Regularity of Critical Points
    5. 3.5 Analysis of Bottleneck Architectures
  4. 4 Neural ODEs
    1. 4.1 Special Architectures
    2. 4.2 Existence of Critical Points
    3. 4.3 Regularity of Critical Points
  5. 5 Conclusion and Outlook

##  1 Introduction

Neural Networks are powerful computational models inspired by the
functionality of the human brain. A classical neural network consists of
interconnected neurons, represented by nodes and weighted edges of a graph.
Through the learning process, the weighted connections between the nodes are
adapted, such that the output of the neural network better predicts the data
[1]. Often, the nodes of a neural network are organized in layers and the
information is fed forward from layer to layer. In the easiest case, the feed-
forward neural network architecture is a perceptron, studied already by
Rosenblatt in 1957 [23].

A classical feed-forward neural network is structured in layers
$h_{l}\in\mathbb{R}^{n_{l}}$, $l\in\\{0,1,\ldots,L\\}$ with width $n_{l}$,
where $h_{0}$ is called the input layer and $h_{L}$ the output layer. The
layers $h_{1},h_{2},\ldots,h_{L-1}$ in between are called hidden layers. The
neural network is a map $\Phi:h_{0}\mapsto h_{L}$. We study feed-forward
neural networks with the iterative update rule

$h_{l}=f_{l}(h_{l-1},\theta_{l})\coloneqq\widetilde{W}_{l}\sigma_{l}(W_{l}h_{l-1}+b_{l})+\tilde{b}_{l}=\widetilde{W}_{l}\sigma_{l}(s_{l})+\tilde{b}_{l}$
(1.1)

for $l\in\\{1,\ldots,L\\}$, where $W_{l}$, $\widetilde{W}_{l}$ are weight
matrices and $b_{l}$, $\tilde{b}_{l}$ are biases of appropriate dimensions. We
abbreviate all parameters by
$\theta_{l}\coloneqq(W_{l},\widetilde{W}_{l},b_{l},\tilde{b}_{l})$. The
function $\sigma_{l}$ is a component-wise applied non-linear activation
function such as $\tanh$, soft-plus, sigmoid or (normal, leaky or parametric)
ReLU. The update rule (1.1) includes both the case of an outer nonlinearity if
$\widetilde{W}_{l}=\text{Id}$, $\tilde{b}_{l}=0$ and the case of an inner
nonlinearity if $W_{l}=\text{Id}$ and $b_{l}=0$.

Besides classical feed-forward neural networks with finite depth $L<\infty$,
we aim to study neural ODEs, which can be interpreted as an infinite network
limit of residual neural networks (ResNets) [2, 9, 15, 27]. ResNets are feed-
forward neural networks with the specific property, that the function $f_{l}$
of the update rule (1.1) is of the form

$h_{l}=f_{l}(h_{l-1},\theta_{l})=h_{l-1}+f_{\text{ResNet}}(h_{l-1},\theta_{l}).$
(1.2)

If $n_{l}=n$ for all $l\in\\{1,\ldots,L\\}$, the ResNet update rule (1.2) can
be obtained as an Euler discretization of the ordinary differential equation
(ODE)

$\frac{\mathrm{d}h}{\mathrm{d}t}=f_{\textup{ODE}}(h(t),\theta(t)),\qquad
h(0)=h_{0},$ (1.3)

on the time interval $[0,T]$ with step size $\delta=T/L$ and
$f_{\textup{ODE}}(\cdot,\cdot)=\frac{1}{\delta}f_{\textup{ResNet}}(\cdot,\cdot)$.
Hereby the function $h$ can be interpreted as the hidden states and the
function $\theta$ as the weights. The output of the neural ODE, which
corresponds to the output layer $h_{L}$ of the neural network is the time-$T$
map $h_{h_{0}}(T)$ (cf. [7]) of (1.3). The smaller the step size $\delta$,
i.e., the larger the depth $L$ of the neural network, the better the Euler
approximation becomes for fixed $T$. In this work, we drop the dependency on
the parameter function $\theta$ and show our results for neural ODEs based on
general non-autonomous initial value problems of the form

$\frac{\mathrm{d}h}{\mathrm{d}t}=\tilde{f}(h(t),t),\qquad h(0)=h_{0}.$ (1.4)

To be flexible with respect to the input and output dimensions of the neural
ODE, we study architectures defined by
$\Phi:x\mapsto\widetilde{L}(h_{L(x)}(T))$, where $L$ and $\widetilde{L}$ are
linear transformations applied before and after the initial value problem. The
initial value problem (1.4) is a classical ODE studied in many contexts, the
main difference in machine learning is that the focus lies on input-output
relations over finite time-scales.

An important and common research area for feed-forward neural networks and
neural ODEs is expressivity. For classical feed-forward neural network and
ResNets, various universal approximation theorems exist [11, 12, 17, 21, 24],
stating that by increasing the width and depth or the number of parameters,
any continuous function can be approximated arbitrarily well. For neural ODEs,
initial explorations in the topic of universal approximation have been made in
[12, 28]. In [15], different neural ODE architectures are systematically
studied with respect to the property of universal embedding. The restriction
to this exact representation problem allows the mathematical arguments to gain
clarity. As for feed-forward neural networks, the general observation is that
also for neural ODEs, the expressivity mainly depends on the dimension of the
phase space. The main distinction is, if the dimension of the initial value
problem (1.4) is smaller or larger compared to the dimension of the input
data. The neural ODE architectures are then called non-augmented or augmented,
respectively.

As first observed in [15], the universal embedding features of neural ODEs are
related to the property of being a Morse function. A Morse function is a
scalar function, where every critical point is non-degenerate [10, 19], i.e.
the determinant of the Hessian matrix at critical points is non-zero. For
scalar feed-forward neural networks with smooth and monotonically increasing
activation functions, it is claimed in [13], that neural networks without
bottlenecks are almost surely Morse functions. A neural network has a
bottleneck, if there exist three layers, where the middle layer has strictly
smaller dimension than the first and the third layer. We build upon the
initial explorations of [13] and [15] as a starting point to systematically
study the property of being a Morse function depending on the architecture for
both feed-forward neural networks and neural ODEs. To that purpose, we define
in both cases, what a non-augmented, an augmented and an architecture with a
bottleneck is. Depending on the type of architecture, we prove comparable
results about the input-output map of feed-forward neural networks and neural
ODEs. For non-augmented architectures, we can prove in both cases via rank
arguments, an explicit calculation of the network gradient and the usage of
linear variational equations in the continuous case, that no critical points
can exist. In the augmented and in the bottleneck case, it is possible that
the input-output map has critical points. Using differential geometry and
Morse theory for augmented feed-forward neural networks and augmented neural
ODEs, we are able to prove that generically, i.e. except for a set of measure
zero with respect to the Lebesgue measure in the weight space, every critical
point is non-degenerate. For finite depth neural networks with a bottleneck,
critical points can be degenerate or non-degenerate. We derive conditions
classifying the regularity of the critical points depending on the specific
weights chosen. For neural ODEs with a bottleneck, where the linear
transformations used do not have full rank, we prove that every critical point
is degenerate. Furthermore we explain, why also the results obtained for
bottleneck architectures are comparable in the finite and in the infinite
depth case.

It is important to study the property of being a Morse function, as for
sufficiently smooth functions, it is a generic property to be a Morse
function. Hence, to represent general data, it is often a good idea to aim for
neural network architectures, which also have the property of being
generically a Morse function. Furthermore, examples of non-degenerate critical
points are extreme points, which can be global properties. If the data to
approximate has a global extreme point, also the chosen neural network
architecture should have the possibility to have a non-degenerate critical
point, such that a good approximation or an exact representation is possible.

In Section 2, we introduce Morse functions and collect our main theorems in
Table 1 to compare the results established for feed-forward neural networks
and neural ODEs depending on the specific architecture. The analysis of
classical feed-forward neural networks is situated in Section 3, whereas the
analysis of neural ODEs can be found in Section 4.

We start in Section 3 by introducing the different architectures non-
augmented, augmented and bottleneck in Section 3.1. We continue in Section 3.2
with developing a theory for equivalent neural network architectures. If a
weight matrix has not full rank, the size of the network can be decreased
without changing the output, but with a possible change in the network
architecture. The goal of this section is to derive a normal form of a feed-
forward neural network, where all weight matrices have full rank. The normal
form of the neural network is then analyzed in Section 3.3 with respect to the
property of having critical points and in Section 3.4, the regularity of these
critical points is studied. We show, that non-augmented neural networks have
no critical points, and that it is a generic property of augmented neural
networks to be a Morse function. As feed-forward neural networks with a
bottleneck show the most complex behavior, we devote Section 3.5 to the
analysis of bottleneck architectures.

In analogy to Section 3, we start Section 4 with Section 4.1 to introduce the
different neural ODE architectures non-augmented, augmented and bottleneck. We
analyze in Section 4.2 the existence of critical points in neural ODE
architectures and study the regularity of the critical points in Section 4.3.
As for feed-forward neural networks we show, that non-augmented neural ODEs
have no critical points, and that it is a generic property of augmented neural
ODEs to be a Morse function. Furthermore we prove, that every critical point
of a neural ODE with a bottleneck is degenerate, and explain why this result
is comparable to the analysis of feed-forward neural networks with
bottlenecks.

##  2 Overview and Results

In this work, we aim to compare feed-forward neural networks and neural ODEs
with respect to the existence and the regularity of critical points. These two
properties can be characterized via Morse functions. One aspect of this work
is to fully rigorously prove and fundamentally generalize results indicated by
Kurochkin [16] about the relationship between Morse functions and feed-forward
neural networks.

###  2.1 Classification of Critical Points

To characterize the existence and regularity of critical points, we use Morse
functions, which are defined in the following.

######  Definition 2.1 (Morse function [10, 19]).

A map $\Phi\in C^{2}(\mathcal{X},\mathbb{R})$ with
$\mathcal{X}\subset\mathbb{R}^{n}$ open is called a Morse function if all
critical points of $\Phi$ are non-degenerate, i.e., for every critical point
$p\in\mathcal{X}$ defined by a zero gradient $\nabla\Phi(p)=0$, the Hessian
matrix $H_{\Phi}(p)$ is non-singular.

Morse functions are generic in the space $C^{k}(\mathcal{X},\mathbb{R})$,
$\mathcal{X}\subset\mathbb{R}^{n}$ open, of $k$ times continuously
differentiable scalar functions $\Phi:\mathcal{X}\rightarrow\mathbb{R}$, as
the following theorem shows.

######  Theorem 2.2 ([15]).

Let $\mathcal{X}\subset\mathbb{R}^{n}$ be open and bounded. For
$k\in\mathbb{N}_{0}$, the vector space

$C^{k}(\mkern 1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern
1.5mu,\mathbb{R})\coloneqq\left\\{\Phi\in
C^{k}(\mathcal{X},\mathbb{R})\textup{ and }\Phi^{(i)}\textup{ is continuously
continuable on }\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern 1.5mu\textup{ for
all }i\leq k\right\\},$

endowed with the $C^{k}$-norm

$\left\lVert\Phi\right\rVert_{C^{k}(\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern
1.5mu)}\coloneqq\sum_{|s|\leq
k}\left\lVert\partial^{s}\Phi\right\rVert_{\infty}$

is a Banach space. Hereby $\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern 1.5mu$ denotes the
closure of $\mathcal{X}$ and $\left\lVert
f\right\rVert_{\infty}\coloneqq\sup_{x\in\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern 1.5mu}|f(x)|$ the
supremum norm of a continuous function $f:\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern
1.5mu\rightarrow\mathbb{R}$. If additionally $k\geq n+1\geq 2$, the set of
Morse functions

$M\coloneqq\left\\{\Phi\in C^{k}(\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern
1.5mu,\mathbb{R}):\Phi\big{|}_{\mathcal{X}}\textup{ is a Morse
function}\right\\}$

is dense in $\left(C^{k}(\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern
1.5mu,\mathbb{R}),\left\lVert\cdot\right\rVert_{C^{k}(\mkern
1.5mu\overline{\mkern-1.5mu\mathcal{X}\mkern-1.5mu}\mkern 1.5mu)}\right)$.

The definition of a Morse function motivates us to subdivide the space
$C^{k}(\mathcal{X},\mathbb{R})$, $\mathcal{X}\subset\mathbb{R}^{n}$ open, into
three disjoint subsets.

######  Definition 2.3.

For $k\in\mathbb{N}_{\geq 1}$, the following subspaces of
$C^{k}(\mathcal{X},\mathbb{R})$, $\mathcal{X}\subset\mathbb{R}^{n}$ open, are
defined:

  * •

The set of functions without critical points:

$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})\coloneqq\left\\{\Phi\in
C^{k}(\mathcal{X},\mathbb{R})\;\lvert\;\nabla\Phi(x)\neq 0\;\forall
x\right\\}.$

By definition, these functions are Morse functions.

  * •

For $k\geq 2$, the set of functions, which have at least one critical point
and where each critical point is non-degenerate:

$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})\coloneqq\left\\{\Phi\in
C^{k}(\mathcal{X},\mathbb{R})\;\lvert\;\left(\exists\,p:\nabla\Phi(p)=0\right)\;\wedge\;\left(\nabla\Phi(q)=0\;\Rightarrow\;H_{\Phi}(q)\textup{
is non-singular}\right)\right\\}.$

By definition, these functions are Morse functions.

  * •

For $k\geq 2$, the set of functions which have at least one degenerate
critical point:

$(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})\coloneqq\left\\{\Phi\in
C^{k}(\mathcal{X},\mathbb{R})\;\lvert\;\exists\,p:\left(\nabla\Phi(p)=0\;\wedge\;H_{\Phi}(p)\textup{
is singular}\right)\right\\}.$

By definition, these functions are not Morse functions.

Clearly, it holds for $k\geq 2$ that the three defined subspaces are non-empty
and that they are a disjoint subdivision of $C^{k}(\mathcal{X},\mathbb{R})$,
i.e. it holds
$C^{k}(\mathcal{X},\mathbb{R})=(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})\,\dot{\cup}\,(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})\,\dot{\cup}\,(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})$.

|  Feed-Forward Neural Network |  Neural ODE
---|---|---
General |  Architecture $\Xi^{k}(\mathcal{X},\mathbb{R})$, $k\geq 0$:  • Fully connected feed-forward neural network with update rule (3.1) • All activation functions $\sigma_{l}$ are applied component-wise, are strictly monotone in each component and $[\sigma_{l}]_{i}\in C^{k}(\mathbb{R},\mathbb{R})$ • The first layer is the input $h_{0}=x\in\mathcal{X}\subset\mathbb{R}^{n}$, the last layer is the output $h_{L}\in\mathbb{R}$ • We assume the generic case, that all weight matrices have full rank (cf. Lemma 3.6) |  Architecture $\textup{NODE}^{k}(\mathcal{X},\mathbb{R})$, $k\geq 0$:  • The scalar neural ODE is defined by (4.1), based on the time-$T$ map of an initial value problem in $\mathbb{R}^{m}$ and two linear layers $L$, $\widetilde{L}$ • The ODE has initial condition $L(x)$, $x\in\mathcal{X}\subset\mathbb{R}^{n}$ and a vector field $f\in C^{k,0}(\mathbb{R}^{m}\times[0,T],\mathbb{R}^{m})$ • The output of the neural ODE is $\widetilde{L}$ applied to the time-$T$ map of the initial value problem.
Non-Augmented |  Special Architecture $\Xi^{k}_{\textup{N}}(\mathcal{X},\mathbb{R})$:  • The width of all layers is less or equal to $n$ and monotonically decreasing from layer to layer |  Special Architecture $\textup{NODE}^{k}_{\textup{N}}(\mathcal{X},\mathbb{R})$:  • It holds $n\geq m$ • The weight matrices of $L$, $\widetilde{L}$ have full rank
|  Properties for $k\geq 1$:  • The feed-forward neural network is of class $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$, see Theorem 3.18 |  Properties for $k\geq 1$:  • The scalar neural ODE is of class $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$, see Theorem 4.12
Augmented |  Special Architecture $\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})$:  • The layer of maximal width has at least $n+1$ nodes, before this layer the width is monotonically increasing and after this layer the width is monotonically decreasing from layer to layer |  Special Architecture $\textup{NODE}^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})$:  • It holds $n<m$ • The weight matrices of $L$, $\widetilde{L}$ have full rank
|  Properties for $k\geq 2$:  • For all set of weights, except for a zero set w.r.t. the Lebesgue measure, the network is of class $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$ or $(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$, see Theorem 3.25 |  Properties for $k\geq 2$:  • For all set of weights, except for a zero set w.r.t. the Lebesgue measure, the neural ODE is of class $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$ or $(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$, see Theorem 4.16
Bottleneck |  Special Architecture $\Xi^{k}_{\textup{B}}(\mathcal{X},\mathbb{R})$:  • There exist three layers $g_{i}$, $g_{j}$, $g_{l}$ with $i<j<l$, such that the width of $g_{j}$ is strictly smaller than the width of $g_{i}$ and $g_{l}$ each |  Special Architecture $\textup{NODE}^{k}_{\textup{B}}(\mathcal{X},\mathbb{R})$:  • At least one of the weight matrices of $L$, $\widetilde{L}$ has not full rank
|  Properties for $k\geq 2$:  • The network can be of all classes, for a detailed classification depending on the type of bottleneck, see Theorem 3.28 |  Properties for $k\geq 2$:  • The scalar neural ODE is of class $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$ or $(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})$, see Theorem 4.19

Table 1: Comparison of the main results for generic feed-forward neural
networks and neural ODEs.

The existence of critical points and their regularity is studied in Section 3
for feed-forward neural networks and in Section 4 for neural ODEs. The main
results regarding the classification of feed-forward neural networks and
neural ODEs into the classes $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$,
$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$ and
$(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})$ are collected in Table 1. The
special architectures non-augmented, augmented and bottleneck are defined in
detail Section 3.1 for feed-forward neural networks and in Section 4.1 for
neural ODEs, but the most important properties of the different architectures
are sketched in Table 1. For feed-forward neural networks we assume the
generic case, that all weight matrices have full rank. In Section 3.2 we show,
how neural networks with not full rank matrices can be transformed in
equivalent neural networks with full rank matrices, which we call the normal
form of the neural network. For non-augmented architectures, Table 1 shows,
that the network is in the finite and in the infinite width case of class
$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$, hence no critical points exist.
In the case of an augmented architecture it is for feed-forward neural
networks and for neural ODEs possible, that critical points exist. Yet, in
this case the critical points are generically non-degenerate, such that the
output is a Morse function of class
$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$ or
$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$. For feed-forward neural networks
with a bottleneck, the output can be of all classes
$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$,
$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$ and
$(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})$, whereas neural ODEs with a
bottleneck can only be of class $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$
or $(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})$. Remark 4.20 explains, why
also in the bottleneck case the established theorems are comparable.

The overall result of our full classification in Table 1 is that classical
feed-forward neural networks and neural ODEs have comparable properties
regarding the existence and regularity of critical points. Furthermore, we can
prove, which cases may occur depending on the architecture. This provides a
precise mathematical link between the underlying structure of the neural
network or neural ODE, and the geometry of the function it represents, i.e.,
whether it is a Morse function or not.

###  2.2 Universal Embedding Property

A desirable property of neural network architectures is universal
approximation, i.e. the property to represent every function of a given
function space arbitrarily well. In an abstract context, universal
approximation can be defined as follows.

######  Definition 2.4 ([13]).

A neural network $\Phi_{\theta}:\mathcal{X}\rightarrow\mathcal{Y}$ with
parameters $\theta$, topological space $\mathcal{X}$ and metric space
$\mathcal{Y}$ has the universal approximation property w.r.t. the space
$C^{k}(\mathcal{X},\mathcal{Y})$, $k\geq 0$, if for every $\varepsilon>0$ and
for each function $\Psi\in C^{k}(\mathcal{X},\mathcal{Y})$, there exists a
choice of parameters $\theta$, such that
$\textup{dist}_{\mathcal{Y}}(\Phi_{\theta}(x),\Psi(x))<\varepsilon$ for all
$x\in\mathcal{X}$.

The parameters $\theta$ are all possible weights and biases, for feed-forward
neural networks additionally the activation functions and for neural ODEs the
vector field. The property of universal approximation can depend on the metric
of the space $\mathcal{Y}$. For classical feed-forward neural networks like
perceptrons, ResNets and RNNs, various universal approximation theorems exist
[11, 12, 17, 21, 24]. These theorems state, given a suitable activation
function, that by increasing the width or depth of the neural network and the
number of parameters, any function $\Psi\in C^{k}(\mathcal{X},\mathcal{Y})$,
$k\geq 0$ can be approximated arbitrarily well. A common property of the
universal approximation theorems is, that the neural network architecture is
augmented.

Even though the established universal approximation theorems are extremely
powerful, they do not explain why architectures without augmentation or with
obstructions like bottlenecks have no universal approximation property. If we
ask for an exact representation instead of an approximation, we can directly
use the results established in this work to make statements about the
universal embedding property of feed-forward neural networks and neural ODEs.

######  Definition 2.5.

A neural network $\Phi_{\theta}:\mathcal{X}\rightarrow\mathcal{Y}$ with
parameters $\theta$ and topological spaces $\mathcal{X}$ and $\mathcal{Y}$ has
the universal embedding property w.r.t. the space
$C^{k}(\mathcal{X},\mathcal{Y})$, $k\geq 0$, if for every function $\Psi\in
C^{k}(\mathcal{X},\mathcal{Y})$, there exists a choice of parameters $\theta$,
such that $\Phi_{\theta}(x)=\Psi(x)$ for all $x\in\mathcal{X}$.

As the subsets $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$,
$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$ and
$(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})$ are all non-empty subsets of
$C^{k}(\mathcal{X},\mathbb{R})$, it follows directly from Table 1, that non-
augmented and bottleneck neural ODEs cannot have the universal embedding
property with respect to the space $C^{k}(\mathcal{X},\mathbb{R})$, $k\geq 2$.
In particular this means, that non-degenerate critical points, such as extreme
points, can only be represented by augmented neural ODEs. In Theorem 4.15 in
Section 4.2 we show via an explicit construction, that augmented neural ODEs
have the universal embedding property. To exactly represent any given map
$\Psi:\mathcal{X}\rightarrow\mathbb{R}$, $\mathcal{X}\subset\mathbb{R}^{n}$,
the phase space needs to be augmented by at least one additional dimension.

For feed-forward neural networks, we can also directly conclude from Table 1,
that non-augmented feed-forward neural networks with full rank weight matrices
cannot have the universal embedding property. In the augmented case, the
situation is more complicated, as Theorem 3.25 only holds for all weights
except for a zero set with respect to the Lebesgue measure in the weight
space. As for large classes of augmented feed-forward neural networks there
exist already various universal approximation theorems, and we do not treat
the question, if universal embedding can be proven in that case. If the neural
network has a bottleneck, all classes
$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$,
$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$ and
$(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R})$ are possible. In Theorem 3.28, we
distinguish four different cases of bottlenecks. In the cases (a) and (b) we
assume that the first bottleneck is non-augmented and prove, that the input-
output map cannot be of class $(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$,
such that the neural network cannot have the universal embedding property. In
the other two cases the first bottleneck is augmented and we formulate a
condition distinguishing in case (c) neural networks with a bottleneck, which
show similar behavior like augmented neural networks and in case (d) neural
networks with a bottleneck, which cannot be of class
$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$. Only in case (c) it is possible
that a universal approximation theorem as for augmented feed-forward neural
networks exists. Overall, our analysis shows, which geometric obstructions,
such as the non-existence or the degeneracy of critical points, prevent neural
network architectures to have the universal embedding property.

##  3 Feed-Forward Neural Networks

Figure 3.1: Structure of a classical feed-forward neural network with update
rule (3.1) in standard notation $(l\in\\{0,\ldots,L\\})$ and in common
notation $(j\in\\{0,\ldots,2L\\})$ for main and intermediate layers,
visualized in dark and light gray respectively.

A classical feed-forward neural network is structured in main layers $h_{l}$,
$l\in\\{0,1,.\ldots,L\\}$, $L\geq 1$ with width $n_{l}$, i.e.
$h_{l}\in\mathbb{R}^{n_{l}}$. The network is initialized by input data
$h_{0}=x\in\mathcal{X}$, $\mathcal{X}\subset\mathbb{R}^{n}$ open with
$n\coloneqq n_{0}$ and the layers are for $l\in\\{1,\ldots,L\\}$ iteratively
updated by

$h_{l}=\widetilde{W}_{l}\sigma_{l}(W_{l}h_{l-1}+b_{l})+\tilde{b}_{l}=\widetilde{W}_{l}\sigma_{l}(s_{l})+\tilde{b}_{l},$
(3.1)

where $\widetilde{W}_{l}\in\mathbb{R}^{n_{l}\times m_{l}}$ and
$W_{l}\in\mathbb{R}^{m_{l}\times n_{l-1}}$ are weight matrices,
$b_{l}\in\mathbb{R}^{m_{l}}$ and $\tilde{b}_{l}\in\mathbb{R}^{n_{l}}$ are
biases and $\sigma_{l}:\mathbb{R}^{m_{l}}\rightarrow\mathbb{R}^{m_{l}}$ is a
component-wise applied activation function, i.e.
$\sigma_{l}=([\sigma_{l}]_{1},\ldots,[\sigma_{l}]_{m_{l}})^{\top}$ with
$[\sigma_{l}]_{i}:\mathbb{R}\rightarrow\mathbb{R}$ for
$i\in\\{1,\ldots,m_{l}\\}$. $m_{l}$ is the dimension of the intermediate
layers $s_{l}\coloneqq W_{l}h_{l-1}+b_{l}$, $l\in\\{1,\ldots,L\\}$ to which
the activation function $\sigma$ is applied. For an easier notation, we
additionally enumerate the main and intermediate layers together by
$g_{j}\in\mathbb{R}^{d_{j}}$, $j\in\\{0,\ldots,2L\\}$, where
$g_{2l}=h_{l}\in\mathbb{R}^{d_{2l}}=\mathbb{R}^{n_{l}}$ for
$l\in\\{0,\ldots,L\\}$ and
$g_{2l-1}=s_{l}\in\mathbb{R}^{d_{2l-1}}=\mathbb{R}^{m_{l}}$ for
$l\in\\{1,\ldots,L\\}$. Additionally we enumerate the weight matrices together
by $V_{j}\in\mathbb{R}^{d_{j}\times d_{j-1}}$, $j\in\\{1,\ldots,2L\\}$, such
that
$(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})=(V_{1},\ldots,V_{2L})$
with $W_{l}=V_{2l-1}$ and $\widetilde{W}_{l}=V_{2l}$ for
$l\in\\{1,\ldots,L\\}$. The output of the neural network is the last layer
$h_{L}$. The structure of the neural network is visualized in Figure 3.1. The
general neural network update rule (3.1) contains feed-forward neural networks
with an outer nonlinearity

$h_{l}=\sigma_{l}(W_{l}h_{l-1}+b_{l})$

by choosing $m_{l}=n_{l}$, $\widetilde{W}_{l}=\textup{Id}_{n_{l}}$ and
$\tilde{b}_{l}=0$ for $l\in\\{1,\ldots,L\\}$ and feed-forward neural networks
with an inner nonlinearity

$h_{l}=\widetilde{W}_{l}\sigma_{l}(h_{l-1})+\tilde{b}_{l}$

by choosing $m_{l}=n_{l-1}$, $W_{l}=\textup{Id}_{n_{l-1}}$ and $b_{l}=0$ for
$l\in\\{1,\ldots,L\\}$. Both architectures, with outer and inner nonlinearity,
as well as their combination with update rule (3.1) are well-known in machine
learning theory [5]. The distinction between the different types of
nonlinearities also exists in classical neural field models of mathematical
neuroscience: the class of Wilson-Cowan models has outer nonlinearities and
the class of Amari models has inner nonlinearities [4].

In the main theorems of this work we assume, that all components of
$\sigma_{l}$ are continuous and strictly monotone on $\mathbb{R}$, i.e.
$[\sigma_{l}]_{i}^{\prime}>0$ or $[\sigma_{l}]_{i}^{\prime}<0$ on $\mathbb{R}$
in the case that $[\sigma_{l}]_{i}$ is differentiable,
$i\in\\{1,\ldots,m_{l}\\}$. As we restrict our analysis to single components
of the output, we can without loss of generality assume that the output
$h_{L}\in\mathbb{R}$ is one-dimensional, i.e. $n_{L}=1$. Hence, the neural
network mapping $h_{0}$ to $h_{L}$ is a function
$\Phi:\mathcal{X}\rightarrow\mathbb{R}$.

######  Lemma 3.1.

Let $\Phi:\mathcal{X}\rightarrow\mathbb{R}$,
$\mathcal{X}\subset\mathbb{R}^{n}$ be a classical feed-forward neural network
with update rule (3.1). If the activation functions fulfill for
$l\in\\{1,\ldots,L\\}$, $i\in\\{1,\ldots,m_{l}\\}$ that $[\sigma_{l}]_{i}\in
C^{k}(\mathbb{R},\mathbb{R})$ with $k\geq 0$, then $\Phi\in
C^{k}(\mathcal{X},\mathbb{R})$.

###### Proof.

As a composition of $k$ times continuously differentiable functions, the chain
rule implies that also $\Phi$ is $k$ times continuously differentiable. ∎

######  Definition 3.2.

For $k\geq 0$, the set of all classical feed-forward neural networks
$\Phi:\mathcal{X}\rightarrow\mathbb{R}$, $\mathcal{X}\subset\mathbb{R}^{n}$
open with update rule (3.1) and component-wise applied strictly monotone
activation functions $[\sigma_{l}]_{i}\in C^{k}(\mathbb{R},\mathbb{R})$,
$l\in\\{1,\ldots,L\\}$, $i\in\\{1,\ldots,m_{l}\\}$ is denoted by
$\Xi^{k}(\mathcal{X},\mathbb{R})\subset C^{k}(\mathcal{X},\mathbb{R})$.

The set of neural networks $\Xi^{k}(\mathcal{X},\mathbb{R})$ we study in this
work is larger than the feed-forward neural networks considered in the work by
Kurochkin [16], where the analysis is restricted to outer nonlinearities with
strictly monotonically increasing activation functions. For most of the
upcoming theorems we provide for illustration purposes low-dimensional
examples. If explicit calculations of gradients and Hessian matrices are
needed in the examples, we work with the soft-plus action function
$\sigma(x)=\ln(1+\exp(x))$, which has as first derivative the sigmoid function
$\sigma^{\prime}(x)=\frac{1}{1+\exp(-x)}$.

###  3.1 Special Architectures

In the following, we subdivide the set of all classical feed-forward neural
networks $\Xi^{k}(\mathcal{X},\mathbb{R})$ introduced in Definition 3.2 in
three different classes: non-augmented neural networks, augmented neural
networks and neural networks with a bottleneck.

#### Non-Augmented

We call a classical feed-forward neural network
$\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$ non-augmented, if it holds for the
widths of the layers that $d_{j}\leq n$ for $j\in\\{0,\ldots,2L\\}$. The space
is non-augmented, as all layers have a width smaller or equal to the width $n$
of the layer $h_{0}$, which corresponds to the input data
$x\in\mathcal{X}\subset\mathbb{R}^{n}$. Additionally we require, that the
widths of the layers are monotonically decreasing from layer to layer, i.e.
$d_{j-1}\geq d_{j}$ for $j\in\\{1,\ldots,2L\\}$. The subset of non-augmented
neural networks is denoted by

$\Xi^{k}_{\textup{N}}(\mathcal{X},\mathbb{R})\coloneqq\left\\{\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R}):\Phi\textup{
is non-augmented}\right\\}.$

#### Augmented

We call a classical feed-forward neural network
$\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$ augmented, if the first layer of
maximal width $g_{l^{\ast}}$ has at least $n+1$ nodes, i.e. $d_{l^{\ast}}\geq
n+1$ and $d_{l^{\ast}-1}<d_{l^{\ast}}$. The space is augmented, as there
exists a layer with width larger than the dimension of the input data
$x\in\mathbb{R}^{n}$. Furthermore we require, that between layer $g_{0}$ and
$g_{l^{\ast}}$, the width of the layers is monotonically increasing, i.e.
$d_{j-1}\leq d_{j}$ for $0<j\leq l^{\ast}$ and between layer $g_{l^{\ast}}$
and $g_{2L}$, the width of the layers is monotonically decreasing, i.e.
$d_{j-1}\geq d_{j}$ for $l^{\ast}<j\leq 2L$. The subset of augmented neural
networks is denoted by

$\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})\coloneqq\left\\{\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R}):\Phi\textup{
is augmented}\right\\}.$

#### Bottleneck

We say that a classical feed-forward neural network
$\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$ has a bottleneck in layer
$g_{j^{\ast}}$, if there exists three layers $g_{i^{\ast}}$, $g_{j^{\ast}}$
and $g_{l^{\ast}}$ with $0\leq i^{\ast}<j^{\ast}<l^{\ast}\leq 2L$, such that
$d_{i^{\ast}}>d_{j^{\ast}}$ and $d_{j^{\ast}}<d_{l^{\ast}}$. Typical neural
network architectures which have a bottleneck are auto-encoders, where the
dimension is first reduced to extract specific features and then augmented
again to the dimension of the initial data. The subset of non-augmented neural
networks is denoted by

$\Xi^{k}_{\textup{B}}(\mathcal{X},\mathbb{R})\coloneqq\left\\{\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R}):\Phi\textup{
has a bottleneck}\right\\}.$

The three different types of feed-forward neural networks are visualized in
Figure 3.2. In the following we show that these three types of architectures
build a disjoint subdivision of all classical feed-forward neural networks.

(a) Structure of a non-augmented neural network
$\Phi\in\Xi_{\textup{N}}^{k}(\mathcal{X},\mathbb{R})$.

(b) Structure of an augmented neural network
$\Phi\in\Xi_{\textup{A}}^{k}(\mathcal{X},\mathbb{R})$.

(c) Structure of a neural network with a bottleneck
$\Phi\in\Xi_{\textup{B}}^{k}(\mathcal{X},\mathbb{R})$.

Figure 3.2: The three different types of architectures non-augmented,
augmented and bottleneck for classical feed-forward neural networks
$\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$.

######  Proposition 3.3.

The subdivision of classical feed-forward neural networks
$\Xi^{k}(\mathcal{X},\mathbb{R})$ in non-aug-mented neural networks
$\Xi^{k}_{\textup{N}}(\mathcal{X},\mathbb{R})$, augmented neural networks
$\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})$ and neural networks with a
bottleneck $\Xi^{k}_{\textup{B}}(\mathcal{X},\mathbb{R})$, is a complete
partition in three disjoint sub-classes of feed-forward neural networks, i.e.

$\Xi^{k}(\mathcal{X},\mathbb{R})=\Xi^{k}_{\textup{N}}(\mathcal{X},\mathbb{R})\;\dot{\cup}\;\,\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})\;\dot{\cup}\;\,\Xi^{k}_{\textup{B}}(\mathcal{X},\mathbb{R}).$

###### Proof.

We define the three index sets

$\displaystyle\mathcal{A}_{<}$
$\displaystyle\coloneqq\left\\{j\in\\{1,\ldots,2L\\}:d_{j-1}<d_{j}\right\\},$
$\displaystyle\mathcal{A}_{=}$
$\displaystyle\coloneqq\left\\{j\in\\{1,\ldots,2L\\}:d_{j-1}=d_{j}\right\\},$
$\displaystyle\mathcal{A}_{>}$
$\displaystyle\coloneqq\left\\{j\in\\{1,\ldots,2L\\}:d_{j-1}>d_{j}\right\\},$

which are a disjoint subdivision of all indices, i.e.
$\mathcal{A}_{<}\,\dot{\cup}\,\mathcal{A}_{=}\,\dot{\cup}\,\mathcal{A}_{>}=\\{1,...,2L\\}$.
We distinguish now different cases depending on the partition of the indices
in the sets $\mathcal{A}_{<}$, $\mathcal{A}_{=}$ and $\mathcal{A}_{>}$.

  * •

Case 1: $\mathcal{A}_{<}=\varnothing$. In this case it holds $d_{j-1}\geq
d_{j}$ for all $j\in\\{1,\ldots,2L\\}$. As $d_{0}=n$ this implies that
$d_{j}\leq n$ for all $j\in\\{0,\ldots,2L\\}$. By definition, the feed-forward
neural network is non-augmented.

  * •

Case 2: $\mathcal{A}_{<}\neq\varnothing$. As the set $\mathcal{A}_{<}$ is
finite, there exists a maximal element
$l^{\ast}=\max\\{j:j\in\mathcal{A}_{<}\\}$.

  * •

Case 2.1: $\mathcal{A}_{<}\neq\varnothing$ and
$\\{1,\ldots,l^{\ast}\\}\subset\left(\mathcal{A}_{<}\cup\mathcal{A}_{=}\right)$.
In this case it holds $d_{j-1}\leq d_{j}$ for $0<j\leq l^{\ast}$. This implies
$d_{l^{\ast}}>d_{l^{\ast}-1}\geq\ldots\geq d_{0}=n$, hence $d_{l^{\ast}}\geq
n+1$. As $l^{\ast}=\max\\{j:j\in\mathcal{A}_{<}\\}$ it holds
$\\{l^{\ast}+1,\ldots,2L\\}\subset\left(\mathcal{A}_{=}\cup\mathcal{A}_{>}\right)$.
Consequently $d_{j-1}\geq d_{j}$ for $l^{\ast}<j\leq 2L$. By definition, the
feed-forward neural network is augmented.

  * •

Case 2.2: $\mathcal{A}_{<}\neq\varnothing$ and
$\\{1,\ldots,l^{\ast}\\}\not\subset\left(\mathcal{A}_{<}\cup\mathcal{A}_{=}\right)$.
Define now the index $j^{\ast}$ as the maximal element of
$\\{1,\ldots,l^{\ast}\\}$ which is not contained in
$\mathcal{A}_{<}\cup\mathcal{A}_{=}$:
$j^{\ast}=\max\\{j\in\\{1,\ldots,l^{\ast}\\}:j\in\mathcal{A}_{>}\\}$. It holds
$j^{\ast}<l^{\ast}$ as $l^{\ast}\in\mathcal{A}_{<}$. For $i^{\ast}=j^{\ast}-1$
it holds $0\leq i^{\ast}<j^{\ast}<l^{\ast}\leq 2L$ and
$d_{i^{\ast}}=d_{j^{\ast}-1}>d_{j^{\ast}}$. As
$\\{j^{\ast}+1,\ldots,l^{\ast}\\}\subset\mathcal{A}_{<}\cup\mathcal{A}_{=}$
and $l^{\ast}\in\mathcal{A}_{<}$ it also holds $d_{j^{\ast}}\leq\ldots\leq
d_{l^{\ast}-1}<d_{l^{\ast}}$. This implies that the considered feed-forward
neural network has a bottleneck as $d_{i^{\ast}}>d_{j^{\ast}}$ and
$d_{j^{\ast}}<d_{l^{\ast}}$.

As the three cases 1, 2.1 and 2.2 are a complete and disjoint subdivision of
possible partitions of the indices $1,\ldots,2L$ in the sets
$\mathcal{A}_{<}$, $\mathcal{A}_{=}$ and $\mathcal{A}_{>}$, also the
subdivision of classical feed-forward neural networks
$\Xi^{k}(\mathcal{X},\mathbb{R})$ in non-augmented neural networks
$\Xi^{k}_{\textup{N}}(\mathcal{X},\mathbb{R})$, augmented neural network
$\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})$ and neural networks with a
bottleneck $\Xi^{k}_{\textup{B}}(\mathcal{X},\mathbb{R})$ is a complete
partition in three disjoint sub-classes of feed-forward neural networks. ∎

###  3.2 Equivalent Neural Network Architectures

In this section, we first define the weight and bias spaces for classical
feed-forward neural networks. Afterwards, we introduce a definition of
equivalent neural network architectures and show via an explicit algorithm how
to obtain under all equivalent neural networks architectures the one with the
fewest number of nodes. The resulting architecture has only full rank matrices
and is called the normal form of the neural network, which is used in the
following Sections 3.3 and 3.4.

To define the weight space, we identify a matrix in $\mathbb{R}^{p\times q}$
with a point in $\mathbb{R}^{pq}$ by stacking the columns of the matrix. This
operation is also known as vectorization.

######  Definition 3.4 ([18]).

Let $A\in\mathbb{R}^{p\times q}$ be a matrix and denote the $j$-th column by
$a_{j}\in\mathbb{R}^{p}$, $j\in\\{1,\ldots,q\\}$. Then the bijective
vectorization operator $\textup{vec}:\mathbb{R}^{p\times
q}\rightarrow\mathbb{R}^{pq}$ is defined as

$\textup{vec}(A)=\begin{pmatrix}a_{1}\\\ \vdots\\\ a_{q}\end{pmatrix}$

with inverse $\textup{vec}^{-1}:\mathbb{R}^{pq}\rightarrow\mathbb{R}^{p\times
q}$.

In the following, we define weight and bias spaces for classical feed-forward
neural networks, generalize the vectorization operator of Definition 3.4 to
multiple weight matrices and introduce a stacking operator for biases.

######  Definition 3.5.

Let $\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$, $k\geq 0$ be a classical feed-
forward neural network with weight matrices
$W=(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})=(V_{1},\ldots,V_{2L})$
and biases $b=(b_{1},\tilde{b}_{1}\ldots,b_{L},\tilde{b}_{L})$.

  1. (a)

The weight space $\mathbb{W}$ is defined as the space of all weight matrices,

$\displaystyle\mathbb{W}$ $\displaystyle\coloneqq\mathbb{R}^{m_{1}\times
n_{0}}\times\mathbb{R}^{n_{1}\times
m_{1}}\times\ldots\times\mathbb{R}^{m_{L}\times
n_{L-1}}\times\mathbb{R}^{n_{L}\times m_{L}}$
$\displaystyle=\mathbb{R}^{d_{1}\times d_{0}}\times\mathbb{R}^{d_{2}\times
d_{1}}\times\ldots\times\mathbb{R}^{d_{2L-1}\times
d_{2L-2}}\times\mathbb{R}^{d_{2L}\times d_{2L-1}}.$

  2. (b)

For $W\in\mathbb{W}$ the bijective multiple vectorization operator
$\textup{vecm}:\mathbb{W}\rightarrow\mathbb{R}^{N_{W}}$ with
$N_{W}\coloneqq\sum_{l=1}^{L}m_{l}(n_{l-1}+n_{l})=\sum_{l=1}^{2L}d_{l}d_{l-1}$
is defined as

$\textup{vecm}(W)\coloneqq\begin{pmatrix}\textup{vec}(W_{1})\\\ \vdots\\\
\textup{vec}(\widetilde{W}_{L})\end{pmatrix}=\begin{pmatrix}\textup{vec}(V_{1})\\\
\vdots\\\ \textup{vec}(V_{2L})\end{pmatrix}\in\mathbb{R}^{N_{W}}.$

The inverse of the operator vecm is denoted by
$\textup{vecm}^{-1}:\mathbb{R}^{N_{W}}\rightarrow\mathbb{W}$.

  3. (c)

The subset of the weight space $\mathbb{W}$, in which all weight matrices $W$
have full rank is denoted by

$\displaystyle\mathbb{W}^{\ast}\coloneqq$
$\displaystyle\Bigl{\\{}W\in\mathbb{W}:\textup{
rank}(W_{l})=\min\\{m_{l},n_{l-1}\\},\textup{
rank}(\widetilde{W}_{l})=\min\\{m_{l},n_{l}\\}\;\forall\;l\in\\{1,\ldots,L\\}\Bigr{\\}}$
$\displaystyle=$ $\displaystyle\Bigl{\\{}W\in\mathbb{W}:\textup{
rank}(V_{j})=\min\\{d_{j},d_{j-1}\\}\;\forall\;j\in\\{1,\ldots,2L\\}\Bigr{\\}}.$

The set of classical feed-forward neural networks
$\Phi\in\Xi^{k}_{i}(\mathcal{X},\mathbb{R})$,
$i\in\\{\varnothing,\textup{N},\textup{A},\textup{B}\\}$ with weight matrices
$W\in\mathbb{W}^{\ast}$ is denoted by
$\Xi^{k}_{i,\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$.

  4. (d)

The bias space $\mathbb{B}$ is defined as the space of all biases
$b=(b_{1},\tilde{b}_{1}\ldots,b_{L},\tilde{b}_{L})$,

$\mathbb{B}\coloneqq\mathbb{R}^{m_{1}}\times\mathbb{R}^{n_{1}}\times\ldots\times\mathbb{R}^{m_{L}}\times\mathbb{R}^{n_{L}}=\mathbb{R}^{d_{1}}\times\mathbb{R}^{d_{2}}\times\ldots\times\mathbb{R}^{d_{2L-1}}\times\mathbb{R}^{d_{2L}}.$

  5. (e)

For $b=(b_{1},\tilde{b}_{1}\ldots,b_{L},\tilde{b}_{L})\in\mathbb{B}$ the
bijective stacking operator
$\textup{stk}:\mathbb{B}\rightarrow\mathbb{R}^{N_{B}}$ with
$N_{B}\coloneqq\sum_{l=1}^{L}(m_{l}+n_{l})=\sum_{l=1}^{2L}d_{l}$ is defined as

$\textup{stk}(b)\coloneqq\begin{pmatrix}b_{1}\\\ \vdots\\\
b_{L}\end{pmatrix}\in\mathbb{R}^{N_{B}}.$

The inverse of the operator stk is denoted by
$\textup{stk}^{-1}:\mathbb{R}^{N_{B}}\rightarrow\mathbb{B}$.

The following lemma shows, that the subset of all weight matrices
$W\in\mathbb{W}$, where at least one matrix has not full rank, i.e. the set
$\mathbb{W}\setminus\mathbb{W}^{\ast}$, is a zero set with respect to the
Lebesgue measure in the identified space $\mathbb{R}^{N_{W}}$.

######  Lemma 3.6.

For all weights $w\in\mathbb{R}^{N_{W}}$, except possibly for a zero set in
$\mathbb{R}^{N_{W}}$ w.r.t. the Lebesgue measure, all corresponding weight
matrices $W=\textup{vecm}^{-1}(w)$ have full rank, i.e. the set

$\textup{vecm}(\mathbb{W}\setminus\mathbb{W}^{\ast})\coloneqq\left\\{\textup{vecm}(W)\in\mathbb{R}^{N_{W}}:W\in\mathbb{W}\setminus\mathbb{W}^{\ast}\right\\}$

is a zero set in $\mathbb{R}^{N_{W}}$.

###### Proof.

By [22, Theorem 5.15], the set of $p\times q$ matrices with rank $k$

$M_{p,q,k}\coloneqq\left\\{M\in\mathbb{R}^{p\times
q}:\textup{rank}(M)=k\right\\}\subset\mathbb{R}^{p\times q},$

is in the identified space $\mathbb{R}^{pq}$ a manifold of dimension
$k(p+q-k)$. For matrices which do not have full rank, i.e. the rank $k$
fulfills $k<k^{\ast}\coloneqq\min\\{p,q\\}$, the dimension of $M_{p,q,k}$ is
strictly smaller than $pq$ as for $k=k^{\ast}-i$, $i\geq 1$ it holds

$\displaystyle k(p+q-k)$
$\displaystyle=(k^{\ast}-i)(p+q-k^{\ast}+i)=(\min\\{p,q\\}-i)(\max\\{p,q\\}+i)$
$\displaystyle=pq-i(\max\\{p,q\\}-\min\\{p,q\\})-i^{2}<pq.$

Consequently
$\textup{vec}(M_{p,q,k})\coloneqq\\{\textup{vec}(M)\in\mathbb{R}^{pq}:M\in
M_{p,q,k}\\}$ has for $k<k^{\ast}$ Lebesgue measure zero in $\mathbb{R}^{pq}$.
We denote the set of all matrices, which do not have full rank by

$M_{p,q,k<k^{\ast}}\coloneqq\bigcup_{k=0}^{k^{\ast}-1}M_{p,q,k}.$

Since

$\textup{vec}(M_{p,q,k<k^{\ast}})=\textup{vec}\left(\bigcup_{k=0}^{k^{\ast}-1}M_{p,q,k}\right)=\bigcup_{k=0}^{k^{\ast}-1}\textup{vec}(M_{p,q,k})$

is a finite union of sets of Lebesgue measure zero in $\mathbb{R}^{pq}$, the
Lebesgue measure of $\textup{vec}(M_{p,q,k<k^{\ast}})$ is also zero in
$\mathbb{R}^{pq}$. Transferred to the weight space $\mathbb{W}$ it follows
that for $j\in\\{1,\ldots,2L\\}$, the set

$\textup{vecm}\left(\mathbb{R}^{d_{1}\times
d_{0}}\times\ldots\times\mathbb{R}^{d_{j-1}\times d_{j-2}}\times
M_{d_{j},d_{j-1},k<k^{\ast}(j)}\times\mathbb{R}^{d_{j+1}\times
d_{j}}\times\ldots\times\mathbb{R}^{d_{2L}\times d_{2L-1}}\right)$

is a zero set w.r.t. the Lebesgue measure in $\mathbb{R}^{N_{W}}$. Hereby
$k^{\ast}(j)=\min\\{d_{j},d_{j-1}\\}$ denotes the maximal rank of a matrix in
$\mathbb{R}^{d_{j}\times d_{j-1}}$. Consequently also the finite union

$\displaystyle\textup{vecm}(\mathbb{W}\setminus\mathbb{W}^{\ast})$
$\displaystyle=\;$
$\displaystyle\textup{vecm}\left(\bigcup_{j=1}^{2L}\mathbb{R}^{d_{1}\times
d_{0}}\times\ldots\times\mathbb{R}^{d_{j-1}\times d_{j-2}}\times
M_{d_{j},d_{j-1},k<k^{\ast}(j)}\times\mathbb{R}^{d_{j+1}\times
d_{j}}\times\ldots\times\mathbb{R}^{d_{2L}\times d_{2L-1}}\right)$
$\displaystyle=\;$
$\displaystyle\bigcup_{j=1}^{2L}\textup{vecm}\Big{(}\mathbb{R}^{d_{1}\times
d_{0}}\times\ldots\times\mathbb{R}^{d_{j-1}\times d_{j-2}}\times
M_{d_{j},d_{j-1},k<k^{\ast}(j)}\times\mathbb{R}^{d_{j+1}\times
d_{j}}\times\ldots\times\mathbb{R}^{d_{2L}\times d_{2L-1}}\Big{)}$

is a zero set w.r.t. the Lebesgue measure in $\mathbb{R}^{N_{W}}$. This
implies that the set of weights $w\in\mathbb{R}^{N_{W}}$, where at least one
of the weight matrices of $W=\textup{vecm}^{-1}(w)$ has not full rank is a
zero set in $\mathbb{R}^{N_{W}}$ w.r.t. the Lebesgue measure and the result
follows. ∎

A first reason to study mainly feed-forward neural networks with full rank
weight matrices is that the set of full rank matrices has full measure in
$\mathbb{R}^{N_{W}}$. A second reason is, that every classical feed-forward
neural network, which has at least one non-full rank weight matrix, is
equivalent to a classical feed-forward neural network with less nodes and only
full rank matrices. By equivalent we mean, that both neural network
architectures have the same output for every input $x\in\mathcal{X}$.

######  Definition 3.7.

Let $k\geq 0$ and $\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$ be a classical
feed-forward neural network. We call another classical feed-forward neural
network $\overline{\Phi}\in\Xi^{k}(\mathcal{X},\mathbb{R})$ equivalent to
$\Phi$ if $\Phi(x)=\overline{\Phi}(x)$ for all $x\in\mathcal{X}$. We say that
the neural network $\overline{\Phi}$ has a smaller (larger) architecture than
$\Phi$ if the number of nodes per layer fulfills $\overline{d}_{j}\leq d_{j}$
($\overline{d}_{j}\geq d_{j}$) for $j\in\\{0,\ldots,2L\\}$ and the total
number of nodes is strictly smaller (larger), i.e. $\overline{N}_{B}<N_{B}$
($\overline{N}_{B}>N_{B}$). It is possible that the number of layers
$\overline{L}$ of $\overline{\Phi}$ is smaller than the number of layers $L$
in $\Phi$, then we set $\overline{d}_{j}=0$ for
$j\in\\{2\overline{L}+1,\ldots,2L\\}$.

We always denote the equivalent neural network and all corresponding weight
matrices, biases and dimensions with an overbar. In the following Lemmas 3.8
and 3.9, we study feed-forward neural networks, which have at least one non-
full rank matrix and explicitly construct an equivalent neural network, where
the considered matrix has full rank. Afterwards we show in Theorem 3.12, how
to combine the two Lemmas to construct an equivalent neural network
architecture with weight matrices $W\in\mathbb{W}^{\ast}$. First, we consider
the case that an inner weight matrix $W_{l+1}\in\mathbb{R}^{m_{l+1}\times
n_{l}}$ has not full rank for some $l\in\\{1,\ldots,L-1\\}$ and show that the
feed-forward neural network is equivalent to a network with a smaller
architecture, which fulfills certain rank properties.

######  Lemma 3.8.

Let
$\Phi\in\Xi^{k}_{\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$
with a non-zero, non-full rank matrix $W_{l+1}\in\mathbb{R}^{m_{l+1}\times
n_{l}}$ for some $l\in\\{1,\ldots,L-1\\}$, i.e.
$0<\textup{rank}(W_{l+1})<\min\\{m_{l+1},n_{l}\\}$. Then there exists an
equivalent feed-forward neural network
$\overline{\Phi}\in\Xi^{k}(\mathcal{X},\mathbb{R})$ with smaller architecture.
Especially only the number of nodes in layer $h_{l}$ is reduced by one, i.e.
$\overline{n}_{l}=n_{l}-1\geq 1$, and $W_{l+1}$, $\widetilde{W}_{l}$ and
$\tilde{b}_{l}$ are replaced by new matrices
$\overline{W}_{l+1}\in\mathbb{R}^{m_{l+1}\times\overline{n}_{l}}$ and
$\overline{\widetilde{W}}_{l}\in\mathbb{R}^{\overline{n}_{l}\times m_{l}}$
with $\textup{rank}(\overline{W}_{l+1})=\textup{rank}(W_{l+1})$,
$\textup{rank}(\overline{\widetilde{W}}_{l})\leq\textup{rank}(\widetilde{W}_{l})$,
$\overline{W}_{l+1}\overline{\widetilde{W}}_{l}=W_{l+1}\widetilde{W}_{l}$ and
a new bias $\overline{\tilde{b}}_{l}\in\mathbb{R}^{\overline{n}_{l}}$.

###### Proof.

If $0<\textup{rank}(W_{l+1})<\min\\{m_{l+1},n_{l}\\}$ for some
$l\in\\{1,\ldots,L-1\\}$, it holds $m_{l+1},n_{l}\geq 2$. The columns of
$W_{l+1}\in\mathbb{R}^{m_{l+1}\times n_{l}}$ are linearly dependent, i.e. for
the columns $[W_{l+1}]_{j}\in\mathbb{R}^{m_{l+1}}$, $j\in\\{1,\ldots,n_{l}\\}$
there exist scalars $\tilde{\alpha}_{j}$, $j\in\\{1,\ldots,n_{l}\\}$ not all
equal to zero, such that

$\sum_{j=1}^{n_{l}}\tilde{\alpha}_{j}[W_{l+1}]_{j}=0\in\mathbb{R}^{m_{l+1}}.$

Since $\tilde{\alpha}_{i}\neq 0$ for some $i\in\\{1,\ldots,n_{l}\\}$, it holds

$[W_{l+1}]_{i}=\sum_{j=1,j\neq i}^{n_{l}}\alpha_{j}[W_{l+1}]_{j}$

with $\alpha_{j}\coloneqq-\tilde{\alpha}_{j}/\tilde{\alpha}_{i}$. If
$[W_{l+1}]_{i}=0$ is a zero column, no information of the node $[h_{l}]_{i}$
is transferred to the next layer, which indicates that the neural network
$\Phi$ is equivalent to a smaller neural network, where the node $[h_{l}]_{i}$
and all connected weights are removed. In the following we prove this
statement for the general case that $[W_{l+1}]_{i}\in\mathbb{R}^{m_{l+1}}$ is
a linear combination of the other columns. We define a new neural network
$\overline{\Phi}\in\Xi^{k}(\mathcal{X},\mathbb{R})$, which has the same
structure, weights, biases and activation functions as $\Phi$, only the number
of nodes in layer $h_{l}$ is reduced by one, i.e.
$\overline{n}_{l}=n_{l}-1\geq 1$, and $W_{l+1}$, $\widetilde{W}_{l}$ and
$\tilde{b}_{l}$ are replaced by new matrices
$\overline{W}_{l+1}\in\mathbb{R}^{m_{l+1}\times\overline{n}_{l}}$ and
$\overline{\widetilde{W}}_{l}\in\mathbb{R}^{\overline{n}_{l}\times m_{l}}$ and
a new bias $\overline{\tilde{b}}_{l}\in\mathbb{R}^{\overline{n}_{l}}$. We
define the matrix

$\overline{W}_{l+1}=\begin{pmatrix}[W_{l+1}]_{1}&\cdots&[W_{l+1}]_{i-1}&[W_{l+1}]_{i+1}\cdots&[W_{l+1}]_{n_{l}}\end{pmatrix}$

which has the same rank as $W_{l+1}$, as $W_{l+1}$ arises from
$\overline{W}_{l+1}$ by adding the new column $[W_{l+1}]_{i}$, which is a
linear combination of the other columns and hence does not increase the
maximal number of linearly independent columns. Furthermore we define

$\overline{\widetilde{W}}_{l}=\begin{pmatrix}[\widetilde{W}_{l}]_{1,1}+\alpha_{1}[\widetilde{W}_{l}]_{i,1}&\cdots&[\widetilde{W}_{l}]_{1,m_{l}}+\alpha_{1}[\widetilde{W}_{l}]_{i,m_{l}}\\\
\vdots&&\vdots\\\
[\widetilde{W}_{l}]_{i-1,1}+\alpha_{i-1}[\widetilde{W}_{l}]_{i,1}&\cdots&[\widetilde{W}_{l}]_{i-1,m_{l}}+\alpha_{i-1}[\widetilde{W}_{l}]_{i,m_{l}}\\\
[\widetilde{W}_{l}]_{i+1,1}+\alpha_{i+1}[\widetilde{W}_{l}]_{i,1}&\cdots&[\widetilde{W}_{l}]_{i+1,m_{l}}+\alpha_{i+1}[\widetilde{W}_{l}]_{i,m_{l}}\\\
\vdots&&\vdots\\\
[\widetilde{W}_{l}]_{n_{l},1}+\alpha_{n_{l}}[\widetilde{W}_{l}]_{i,1}&\cdots&[\widetilde{W}_{l}]_{n_{l},m_{l}}+\alpha_{n_{l}}[\widetilde{W}_{l}]_{i,m_{l}}\end{pmatrix}$

which has rank smaller or equal to $\textup{rank}(\widetilde{W}_{l})$. To see
this, we first apply linear row operations to the matrix $\widetilde{W}_{l}$
by adding to the $j$-th row, $j\in\\{1,\ldots,i-1,i+1,\ldots,n_{l}\\}$, the
$i$-th row multiplied with $\alpha_{j}$ each. The resulting matrix has the
same rank as $\widetilde{W}_{l}$. As we obtain now the matrix
$\overline{\widetilde{W}}_{l}$ by removing the $i$-th row, it holds
$\textup{rank}(\overline{\widetilde{W}}_{l})\leq\textup{rank}(\widetilde{W}_{l})$.
Finally the new bias is given by

$\overline{\tilde{b}}_{l}=\begin{pmatrix}[\tilde{b}_{l}]_{1}+\alpha_{1}[\tilde{b}_{l}]_{i}\\\
\vdots\\\ [\tilde{b}_{l}]_{i-1}+\alpha_{i-1}[\tilde{b}_{l}]_{i}\\\
[\tilde{b}_{l}]_{i+1}+\alpha_{i+1}[\tilde{b}_{l}]_{i}\\\ \vdots\\\
[\tilde{b}_{l}]_{n_{l}}+\alpha_{n_{l}}[\tilde{b}_{l}]_{i}\end{pmatrix}.$

As the neural network architectures $\Phi$ and $\overline{\Phi}$ agree in all
weights, biases and activation functions until $\sigma_{l}$, it holds

$\overline{\sigma}_{l}(\overline{s}_{l})=\overline{\sigma}_{l}(\overline{W}_{l}\overline{h}_{l-1}+\overline{b}_{l})=\sigma_{l}(W_{l}h_{l-1}+b_{l})=\sigma_{l}(s_{l}),\qquad\textup{for
all }x\in\mathcal{X}.$

In the following we aim to show that

$\overline{W}_{l+1}\overline{h}_{l}=\overline{W}_{l+1}\left[\overline{\widetilde{W}}_{l}\overline{\sigma}_{l}(\overline{s}_{l})+\overline{\tilde{b}}_{l}\right]=W_{l+1}\left[\widetilde{W}_{l}\sigma_{l}(s_{l})+\tilde{b}_{l}\right]=W_{l+1}h_{l},$

which implies with the fact, that the neural network architectures $\Phi$ and
$\overline{\Phi}$ agree in the bias $b_{l+1}$ and in all weights, biases and
activation functions from $\sigma_{l+1}$ on-wards, that $\Phi$ and
$\overline{\Phi}$ are equivalent. We calculate

$\displaystyle\overline{W}_{l+1}\overline{h}_{l}$
$\displaystyle=\overline{W}_{l+1}\left[\overline{\widetilde{W}}_{l}\overline{\sigma}_{l}(\overline{s}_{l})+\overline{\tilde{b}}_{l}\right]=\overline{W}_{l+1}\left[\overline{\widetilde{W}}_{l}\sigma_{l}(s_{l})+\overline{\tilde{b}}_{l}\right]$
$\displaystyle=\overline{W}_{l+1}\overline{\widetilde{W}}_{l}\sigma_{l}(s_{l})+\overline{W}_{l+1}\overline{\tilde{b}}_{l}$
$\displaystyle=W_{l+1}\widetilde{W}_{l}\sigma_{l}(s_{l})+W_{l+1}\tilde{b}_{l}=W_{l+1}\left[\widetilde{W}_{l}\sigma_{l}(s_{l})+\tilde{b}_{l}\right]=W_{l+1}h_{l}$

where we used in the last line that
$\overline{W}_{l+1}\overline{\widetilde{W}}_{l}=W_{l+1}\widetilde{W}_{l}$ and
$\overline{W}_{l+1}\overline{\tilde{b}}_{l}=W_{l+1}\tilde{b}_{l}$ since

$\displaystyle\left[\overline{W}_{l+1}\overline{\widetilde{W}}_{l}\right]_{j,k}$
$\displaystyle=\sum_{p=1,p\neq
i}^{n_{l-1}}[W_{l+1}]_{j,p}\left[[\widetilde{W}_{l}]_{p,k}+\alpha_{p}[\widetilde{W}_{l}]_{i,k}\right]=\sum_{p=1}^{n_{l-1}}[W_{l+1}]_{j,p}[\widetilde{W}_{l}]_{p,k}=\left[W_{l+1}\widetilde{W}_{l}\right]_{j,k}$
$\displaystyle\left[\overline{W}_{l+1}\overline{\tilde{b}}_{l}\right]_{j}$
$\displaystyle=\sum_{p=1,p\neq
i}^{n_{l-1}}[W_{l+1}]_{j,p}\left[[\tilde{b}_{l}]_{p}+\alpha_{p}[\tilde{b}_{l}]_{i}\right]=\sum_{p=1}^{n_{l}}[W_{l+1}]_{j,p}[\tilde{b}_{l}]_{p}=\left[W_{l+1}\tilde{b}_{l}\right]_{j}$

by the assumption on linear dependence of the columns of $W_{l+1}$. ∎

Second, we show that also in the case that an outer weight matrix
$\widetilde{W}_{l}\in\mathbb{R}^{m_{l}\times n_{l-1}}$ has for some
$l\in\\{1,\ldots,L-1\\}$ not full rank, the neural network is equivalent to a
smaller architecture with certain rank properties.

######  Lemma 3.9.

Let
$\Phi\in\Xi^{k}_{\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$
with a non-zero, non-full rank matrix
$\widetilde{W}_{l}\in\mathbb{R}^{n_{l}\times m_{l}}$ for some
$l\in\\{1,\ldots,L-1\\}$, i.e.
$0<\textup{rank}(\widetilde{W}_{l})<\min\\{m_{l},n_{l}\\}$. Then there exists
an equivalent feed-forward neural network
$\overline{\Phi}\in\Xi^{k}(\mathcal{X},\mathbb{R})$ with smaller architecture.
Especially only the number of nodes in layer $h_{l}$ is reduced by one, i.e.
$\overline{n}_{l}=n_{l}-1\geq 1$, and $\widetilde{W}_{l}$, $W_{l+1}$ and
$\tilde{b}_{l}$ are replaced by new matrices
$\overline{\widetilde{W}}_{l}\in\mathbb{R}^{\overline{n}_{l}\times m_{l}}$ and
$\overline{W}_{l+1}\in\mathbb{R}^{m_{l+1}\times\overline{n}_{l}}$ with
$\textup{rank}(\overline{\widetilde{W}}_{l})=\textup{rank}(\widetilde{W}_{l})$,
$\textup{rank}(\overline{W}_{l+1})\leq\textup{rank}(W_{l+1})$,
$\overline{W}_{l+1}\overline{\widetilde{W}}_{l}=W_{l+1}\widetilde{W}_{l}$ and
a new bias $\overline{\tilde{b}}_{l}\in\mathbb{R}^{\overline{n}_{l}}$. If
$W_{l+1}\in\mathbb{R}^{m_{l+1}\times n_{l}}$ has full rank, i.e.
$\textup{rank}(W_{l+1})=\min\\{m_{l+1},n_{l}\\}$, then $\overline{W}_{l+1}$
has also full rank, i.e.
$\textup{rank}(\overline{W}_{l+1})=\min\\{m_{l+1},\overline{n}_{l}\\}$.

###### Proof.

If $0<\textup{rank}(\widetilde{W}_{l})<\min\\{m_{l},n_{l}\\}$ for some
$l\in\\{1,\ldots,L-1\\}$, it holds $m_{l},n_{l}\geq 2$. The rows of
$\widetilde{W}_{l}\in\mathbb{R}^{n_{l}\times m_{l}}$ are linearly dependent,
i.e. for the rows $[\widetilde{W}_{l}^{\top}]_{j}\in\mathbb{R}^{m_{l}}$,
$j\in\\{1,\ldots,n_{l}\\}$ there exist scalars $\tilde{\alpha}_{j}$,
$j\in\\{1,\ldots,n_{l}\\}$ not all equal to zero, such that

$\sum_{j=1}^{n_{l}}\tilde{\alpha}_{j}[\widetilde{W}_{l}^{\top}]_{j}=0\in\mathbb{R}^{m_{l}}.$

Since $\tilde{\alpha}_{i}\neq 0$ for some $i\in\\{1,\ldots,n_{l}\\}$, it holds

$[\widetilde{W}_{l}^{\top}]_{i}=\sum_{j=1,j\neq
i}^{n_{l}}\alpha_{j}[\widetilde{W}_{l}^{\top}]_{j}$

with $\alpha_{j}\coloneqq-\tilde{\alpha}_{j}/\tilde{\alpha}_{i}$. If
$[\widetilde{W}_{l}^{\top}]_{i}=0$ is a zero row, no information of the
activated layer $\sigma_{l}(s_{l})$ is transferred to the node $[h_{l}]_{i}$
of the next layer, which indicates that the neural network $\Phi$ is
equivalent to a smaller neural network, where the node $[h_{l}]_{i}$ and all
connected weights are removed. In the following we prove this statement for
the general case that $[\widetilde{W}_{l}^{\top}]_{i}\in\mathbb{R}^{m_{l}}$ is
a linear combination of the other rows. We define a new neural network
$\overline{\Phi}\in\Xi^{k}(\mathcal{X},\mathbb{R})$, which has the same
structure, weights, biases and activation functions as $\Phi$, only the number
of nodes in layer $h_{l}$ is reduced by one, i.e.
$\overline{n}_{l}=n_{l}-1\geq 1$, and $\widetilde{W}_{l}$, $W_{l+1}$ and
$\tilde{b}_{l}$ are replaced by new matrices
$\overline{\widetilde{W}}_{l}\in\mathbb{R}^{\overline{n}_{l}\times m_{l}}$ and
$\overline{W}_{l+1}\in\mathbb{R}^{m_{l+1}\times\overline{n}_{l}}$ and a new
bias $\overline{\tilde{b}}_{l}\in\mathbb{R}^{\overline{n}_{l}}$. We define the
matrix

$\overline{\widetilde{W}}_{l}=\begin{pmatrix}[\widetilde{W}_{l}^{\top}]_{1}^{\top}\\\
\vdots\\\ [\widetilde{W}_{l}^{\top}]_{i-1}^{\top}\\\
[\widetilde{W}_{l}^{\top}]_{i+1}^{\top}\\\ \vdots\\\
[\widetilde{W}_{l}^{\top}]^{\top}_{n_{l}}\end{pmatrix}$

which has the same rank as $\widetilde{W}_{l}$, as $\widetilde{W}_{l}$ arises
from $\overline{\widetilde{W}}_{l}$ by adding the new row
$[\widetilde{W}_{l}^{\top}]^{\top}_{i}$, which is a linear combination of the
other rows and hence does not increase the maximal number of linearly
independent rows. Furthermore we define

$\displaystyle\overline{W}_{l+1}=$
$\displaystyle\left([W_{l+1}]_{1}+\alpha_{1}[W_{l+1}]_{i},\ldots,[W_{l+1}]_{i-1}+\alpha_{i-1}[W_{l+1}]_{i},\right.$
$\displaystyle\left.[W_{l+1}]_{i+1}+\alpha_{i+1}[W_{l+1}]_{i},\ldots,[W_{l+1}]_{n_{l}}+\alpha_{n_{l}}[W_{l+1}]_{i}\right)$

which has rank smaller or equal to $\textup{rank}(W_{l+1})$. To see this, we
first apply linear column operations to the matrix $W_{l+1}$ by adding to the
$j$-th column, $j\in\\{1,\ldots,i-1,i+1,\ldots,n_{l}\\}$, the $i$-th column
multiplied with $\alpha_{j}$ each. The resulting matrix $Y_{l+1}$ has the same
rank as $W_{l+1}$ and $\overline{W}_{l+1}$ is obtained from $Y_{l+1}$ by
removing the $i$-th column, hence
$\textup{rank}(\overline{W}_{l+1})\leq\textup{rank}(Y_{l+1})=\textup{rank}(W_{l+1})$.
If $W_{l+1}$ has full rank, i.e.
$\textup{rank}(W_{l+1})=\min\\{m_{l+1},n_{l}\\}$, then also
$\overline{W}_{l+1}$ has full rank, i.e.
$\textup{rank}(\overline{W}_{l+1})=\min\\{m_{l+1},\overline{n}_{l}\\}$. To see
this, we distinguish two cases: if $m_{l+1}<n_{l}$ it holds
$\textup{rank}(W_{l+1})=m_{l+1}$, such that each $m_{l+1}$ columns of
$W_{l+1}$ and hence also of $Y_{l+1}$ are linearly independent. Consequently
removing one of the $n_{l}$ columns of $Y_{l+1}$ does not change the rank,
such that
$\textup{rank}(\overline{W}_{l+1})=m_{l+1}=\min\\{m_{l+1},\overline{n}_{l}\\}$.
If $m_{l+1}\geq n_{l}$ it holds $\textup{rank}(W_{l+1})=n_{l}$, such that all
$n_{l}$ columns of $W_{l+1}$ and hence also all $\bar{n}_{l}$ columns of
$Y_{l+1}$ are linearly independent. As $Y_{l+1}$ has $n_{l}$ columns, removing
one leads to a matrix with $\overline{n}_{l}=n_{l}-1$ linearly independent
columns. Consequently it holds
$\textup{rank}(\overline{W}_{l+1})=\overline{n}_{l}=\min\\{m_{l+1},\overline{n}_{l}\\}$.
Finally the new bias is given by

$\overline{\tilde{b}}_{l}=y_{l}+c_{l}\coloneqq\begin{pmatrix}[\tilde{b}_{l}]_{1}\\\
\vdots\\\ [\tilde{b}_{l}]_{i-1}\\\ [\tilde{b}_{l}]_{i+1}\\\ \vdots\\\
[\tilde{b}_{l}]_{n_{l}}\end{pmatrix}+\begin{pmatrix}[c_{l}]_{1}\\\ \vdots\\\
[c_{l}]_{i-1}\\\ [c_{l}]_{i+1}\\\ \vdots\\\ [c_{l}]_{n_{l}}\end{pmatrix},$

where $c_{l}\in\mathbb{R}^{\bar{n}_{l}}$ is an arbitrary solution of the
linear system

$\overline{W}_{l+1}c_{l}=W_{l+1}\tilde{b}_{l}-\overline{W}_{l+1}y_{l}\eqqcolon
d_{l}\in\mathbb{R}^{m_{l+1}}.$

This system has by the Rouché-Capelli Theorem (cf. [25]) always at least one
solution as the rank of the matrix $\overline{W}_{l+1}$ is the same as the
rank of the extended coefficient matrix

$\textup{rank}(\overline{W}_{l+1})=\textup{rank}(\overline{W}_{l+1}\big{|}d_{l}).$

This holds as every column of $W_{l+1}$ is a linear combination of columns of
$\overline{W}_{l+1}$, so also the vector $d_{l}$ is a linear combination of
the columns of $\overline{W}_{l+1}$. Consequently the maximal number of
linearly independent columns does not increase by attaching the vector $d_{l}$
to the matrix $\overline{W}_{l+1}$, such that the rank of $\overline{W}_{l+1}$
and $(\overline{W}_{l+1}\big{|}d_{l})$ is the same. As the neural network
architectures $\Phi$ and $\overline{\Phi}$ agree in all weights, biases and
activation functions until $\sigma_{l}$, it holds

$\overline{\sigma}_{l}(\overline{s}_{l})=\overline{\sigma}_{l}(\overline{W}_{l}\overline{h}_{l-1}+\overline{b}_{l})=\sigma_{l}(W_{l}h_{l-1}+b_{l})=\sigma_{l}(s_{l}),\qquad\textup{for
all }x\in\mathcal{X}.$

In the following we aim to show that

$\overline{W}_{l+1}\overline{h}_{l}=\overline{W}_{l+1}\left[\overline{\widetilde{W}}_{l}\overline{\sigma}_{l}(\overline{s}_{l})+\overline{\tilde{b}}_{l}\right]=W_{l+1}\left[\widetilde{W}_{l}\sigma_{l}(s_{l})+\tilde{b}_{l}\right]=W_{l+1}h_{l},$

which implies with the fact, that the neural network architectures $\Phi$ and
$\overline{\Phi}$ agree in the bias $b_{l+1}$ and in all weights, biases and
activation functions from $\sigma_{l+1}$ on-wards, that $\Phi$ and
$\overline{\Phi}$ are equivalent. We calculate

$\displaystyle\overline{W}_{l+1}\overline{h}_{l}$
$\displaystyle=\overline{W}_{l+1}\left[\overline{\widetilde{W}}_{l}\overline{\sigma}_{l}(\overline{s}_{l})+\overline{\tilde{b}}_{l}\right]=\overline{W}_{l+1}\left[\overline{\widetilde{W}}_{l}\sigma_{l}(s_{l})+y_{l}+c_{l}\right]$
$\displaystyle=\overline{W}_{l+1}\overline{\widetilde{W}}_{l}\sigma_{l}(s_{l})+\overline{W}_{l+1}y_{l}+\overline{W}_{l+1}c_{l}$
$\displaystyle=\overline{W}_{l+1}\overline{\widetilde{W}}_{l}\sigma_{l}(s_{l})+W_{l+1}\tilde{b}_{l}$
$\displaystyle=W_{l+1}\widetilde{W}_{l}\sigma_{l}(s_{l})+W_{l+1}\tilde{b}_{l}=W_{l+1}\left[\widetilde{W}_{l}\sigma_{l}(s_{l})+\tilde{b}_{l}\right]=W_{l+1}h_{l},$

where we used in the last line that
$\overline{W}_{l+1}\overline{\widetilde{W}}_{l}=W_{l+1}\widetilde{W}_{l}$
since

$\left[\overline{W}_{l+1}\overline{\widetilde{W}}_{l}\right]_{j,k}=\sum_{p=1,p\neq
i}^{n_{l}}\left([W_{l+1}]_{j,p}+\alpha_{p}[W_{l+1}]_{j,i}\right)[\widetilde{W}_{l}]_{p,k}=\sum_{p=1}^{n_{l}}[W_{l+1}]_{j,p}[\widetilde{W}_{l}]_{p,k}=\left[W_{l+1}\widetilde{W}_{l}\right]_{j,k}$

by the assumption on linear dependence of the rows of $\widetilde{W}_{l}$. ∎

Finally, we aim to apply Lemma 3.8 and Lemma 3.9 to find smaller equivalent
architectures, until all weight matrices of the feed-forward neural network
have full rank. To prove this, we need the following two short lemmas.

######  Lemma 3.10.

Let $A_{1},\ldots,A_{J}$ be matrices $A_{j}\in\mathbb{R}^{k_{j}\times
k_{j+1}}$ with full rank, i.e. for $j\in\\{1,\ldots,J\\}$ it holds
$\textup{rank}(A_{j})=\min\\{k_{j},k_{j+1}\\}$. If the dimensions of the
matrices are monotone, i.e. $k_{1}\geq k_{2}\geq\ldots\geq k_{J+1}$ or
$k_{1}\leq k_{2}\leq\ldots\leq k_{J+1}$, then also the matrix product

$A\coloneqq A_{1}A_{2}\ldots A_{J}\in\mathbb{R}^{k_{1}\times k_{J+1}}$

has full rank, i.e. $\textup{rank}(A)=\min\\{k_{1},k_{J+1}\\}$.

###### Proof.

Sylvester’s rank inequality (cf. [26]) implies for the product of two matrices
$A_{j}\in\mathbb{R}^{k_{j}\times k_{j+1}}$ and
$A_{j+1}\in\mathbb{R}^{k_{j+1}\times k_{j+2}}$ that

$\textup{rank}(A_{j})+\textup{rank}(A_{j+1})-k_{j+1}\leq\textup{rank}(A_{j}A_{j+1})\leq\min\\{k_{j},k_{j+2}\\}.$

If $k_{j}\geq k_{j+1}\geq k_{j+2}$, this implies
$\textup{rank}(A_{j}A_{j+1})=k_{j+2}$ and if $k_{j}\leq k_{j+1}\leq k_{j+2}$,
this implies $\textup{rank}(A_{j}A_{j+1})=k_{j}$, such that in both cases the
matrix product $A_{j}A_{j+1}$ has full rank. Inductively it follows that the
matrix product $A$ has full rank, i.e.
$\textup{rank}(A)=\min\\{k_{1},k_{J+1}\\}$. ∎

######  Lemma 3.11.

Let $A_{0}\in\mathbb{R}^{m\times n}$ with $\textup{rank}(A_{0})>0$. For $i\geq
0$, if $A_{i}\in\mathbb{R}^{m\times(n-i)}$ has not full rank, define
iteratively the matrix $A_{i+1}\in\mathbb{R}^{m\times(n-i-1)}$ by removing a
column of $A_{i}\in\mathbb{R}^{m\times(n-i)}$ in such a way that
$\textup{rank}(A_{i+1})=\textup{rank}(A_{i})$. Then there exists an index
$r\geq 0$, such that $A_{r}\in\mathbb{R}^{m\times(n-r)}$ has full rank. The
analogous statements holds by iteratively removing the rows of $A_{0}$.

###### Proof.

Let $p=\textup{rank}(A_{0})<\min\\{m,n\\}$. By assumption it holds for
$i\in\\{0,\ldots,n-p-1\\}$ that

$\textup{rank}(A_{i})=\textup{rank}(A_{0})=p,$

such that $A_{i}\in\mathbb{R}^{m\times(n-i)}$ has not full rank as
$p<\min\\{m,n-i\\}$. Consequently the matrix $A_{n-p}\in\mathbb{R}^{m\times
p}$ is well defined and has full rank $p<m$, i.e. the statement holds for
$r=n-p$. The statement for iteratively removing the rows of $A_{0}$ follows
with the same argumentation for the transpose $A_{0}^{\top}$. ∎

The following theorem is the main reason, why we restrict ourselves to the
analysis of neural networks with full rank weight matrices
$W\in\mathbb{W}^{\ast}$. It shows, that the neural network is either up to a
linear change of coordinates equivalent to a smaller architecture with full
rank matrices, or the neural network is a constant function. The resulting
architecture is called the normal form of the network.

######  Theorem 3.12.

Let
$\Phi\in\Xi^{k}_{\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$,
$k\geq 0$, $\mathcal{X}\subset\mathbb{R}^{n}$ be a classical feed-forward
neural network with weight matrices
$W=(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})\in\mathbb{W}\setminus\mathbb{W}^{\ast}$
and biases $b=(b_{1},\tilde{b}_{1},\ldots,b_{L},\tilde{b}_{L})\in\mathbb{B}$.

  1. (a)

If $\textup{rank}(W_{1})>0$, $\textup{rank}(\widetilde{W}_{L})>0$ and
$\textup{rank}(W_{l+1}\widetilde{W}_{l})>0$ for all $l\in\\{1,\ldots,L-1\\}$,
there exists a feed-forward neural network
$\overline{\Phi}\in\Xi^{k}_{\mathbb{W}^{\ast}}(\mathcal{Y},\mathbb{R})$,
$\mathcal{Y}\subset\mathbb{R}^{\bar{n}}$ for some $\bar{n}\leq n$, which has a
smaller architecture, only full rank weight matrices and which is up to a
linear change of coordinates, represented by a full rank matrix
$A\in\mathbb{R}^{\bar{n}\times n}$, equivalent to $\Phi$. If $\bar{n}=n$, then
$A$ is the identity matrix and $\mathcal{Y}=\mathcal{X}$, if $\bar{n}<n$, then
$\mathcal{Y}=\\{y\in\mathbb{R}^{\bar{n}}:y=Ax,x\in\mathcal{X}\\}$.

  2. (b)

If $\textup{rank}(W_{1})=0$ or $\textup{rank}(\widetilde{W}_{L})=0$ or
$\textup{rank}(W_{l+1}\widetilde{W}_{l})=0$ for some $l\in\\{1,\ldots,L-1\\}$,
it holds $\Phi(x)=c_{W,b}$ for all $x\in\mathcal{X}$, where $c_{W,b}$ is a
scalar independent of $x$, only depending on $W$ and $b$. $\Phi$ is equivalent
to $\overline{\Phi}\in\Xi^{k}(\mathcal{X},\mathbb{R})$ defined by
$\overline{L}=1$, $\overline{W}_{1}=0\in\mathbb{R}^{1\times n}$,
$\overline{b}_{1}=0\in\mathbb{R}$,
$\overline{\widetilde{W}}_{1}=0\in\mathbb{R}$ and
$\overline{\tilde{b}}_{1}=c_{W,b}\in\mathbb{R}$, which has a smaller
architecture than $\Phi$ if $\overline{\Phi}\neq\Phi$.

###### Proof.

For case (a) we consider a classical feed-forward neural network
$\Phi\in\Xi^{k}_{\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$
and denote its weight matrices by
$W^{(0)}=(W_{1}^{(0)},\widetilde{W}_{1}^{(0)},\ldots,W_{L}^{(0)},\widetilde{W}_{L}^{(0)})$
and its input by $x^{(0)}\in\mathcal{X}$. As
$W^{(0)}\in\mathbb{W}\setminus\mathbb{W}^{\ast}$, at least one of the weight
matrices has not full rank. The assumption $\textup{rank}(W_{1}^{(0)})>0$,
$\textup{rank}(\widetilde{W}_{L}^{(0)})>0$ and
$\textup{rank}(W_{l+1}^{(0)}\widetilde{W}_{l}^{(0)})>0$ for all
$l\in\\{1,\ldots,L-1\\}$ implies, that all weight matrices of $W^{(0)}$ have
at least rank one and every weight matrix, which has not full rank, has at
least width and height two. In the following, we explicitly construct
equivalent feed-forward neural networks with smaller architectures, until all
weight matrices have full rank. The structure of the algorithm is visualized
in Figure 3.3. We start with step (i) and $r=0$.

Figure 3.3: Structure of the algorithm defined in the proof of Theorem
3.12(a).

  1. (i)

If this is the first iteration of step (i), denote the considered feed-forward
neural network with weight matrices
$(W_{1}^{(0)},\widetilde{W}_{1}^{(0)},W_{2}^{(0)},\ldots,W_{L}^{(0)},\widetilde{W}_{L}^{(0)})$
by
$\Phi^{(\textup{(i)},0)}\in\Xi^{k}_{\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$
and set $r=0$.

If $W_{1}^{(r)}\in\mathbb{R}^{m_{1}\times(n-r)}$ has full rank, go to step
(ii) and in the case that $r=0$ set $r_{0}=0$, $W_{1}^{(\ast)}\coloneqq
W_{1}^{(r_{0})}=W_{1}^{(0)}$, $\mathcal{Y}\coloneqq\mathcal{X}$,
$\Phi^{(\textup{(i)},r_{0})}=\Phi^{(\textup{(i)},0)}$ and define
$A\coloneqq\text{Id}_{n}$, which is the identity transformation on
$\mathbb{R}^{n}$.

If $W_{1}^{(r)}\in\mathbb{R}^{m_{1}\times(n-r)}$ has not full rank, it holds
$0<\textup{rank}(W_{1}^{(r)})<\min\\{m_{1},n-r\\}$. The columns of
$W_{1}^{(r)}$ are linearly dependent, hence there exist scalars
$\tilde{\alpha}_{j}^{(r)}$, $j\in\\{1,\ldots,n-r\\}$ not all equal to zero,
such that

$\sum_{j=1}^{n-r}\tilde{\alpha}_{j}^{(r)}[W_{1}^{(r)}]_{j}=0\in\mathbb{R}^{m_{1}}.$

Since $\tilde{\alpha}_{i}^{(r)}\neq 0$ for some $i\in\\{1,\ldots,n-r\\}$, it
holds

$[W_{1}^{(r)}]_{i}=\sum_{j=1,j\neq i}^{n-r}\alpha_{j}^{(r)}[W_{1}^{(r)}]_{j}$

with
$\alpha_{j}^{(r)}\coloneqq-\tilde{\alpha}_{j}^{(r)}/\tilde{\alpha}_{i}^{(r)}$.
We replace the matrix $W_{1}^{(r)}$ by the matrix

$W_{1}^{(r+1)}=\begin{pmatrix}[W_{1}^{(r)}]_{1}&\cdots&[W_{1}^{(r)}]_{i-1}&[W_{1}^{(r)}]_{i+1}\cdots&[W_{1}^{(r)}]_{n-r}\end{pmatrix}\in\mathbb{R}^{m_{1}\times(n-r-1)}$

which has the same rank as $W_{1}^{(r)}$, $W_{1}^{(r)}$ arises from
$W_{1}^{(r+1)}$ by adding a new column which is a linear combination of the
other columns and hence does not increase the maximal number of linearly
independent columns. As $\text{rank}(W_{1}^{(r+1)})=\text{rank}(W_{1}^{(r)})$,
it holds $\text{rank}(W_{1}^{(r+1)})>0$. Furthermore we make a linear change
of coordinates $A^{(r)}:\mathbb{R}^{n-r}\rightarrow\mathbb{R}^{n-r-1}$ of the
input data $x^{(r)}\subset\mathbb{R}^{n-r}$ defined by

$x^{(r+1)}=A^{(r)}(x^{(r)})=\begin{pmatrix}1&\ldots&0&\alpha_{1}&0&\ldots&0\\\
\vdots&&0&\ldots&0&&\vdots\\\ 0&\ldots&1&\alpha_{i-1}&0&\ldots&0\\\
0&\ldots&0&\alpha_{i+1}&1&\ldots&0\\\ \vdots&&0&\ldots&0&&\vdots\\\
0&\ldots&0&\alpha_{n-r}&0&\ldots&1\end{pmatrix}x^{(r)}=\begin{pmatrix}x_{1}+\alpha_{1}x_{i}\\\
\vdots\\\ x_{i-1}+\alpha_{i-1}x_{i}\\\ x_{i+1}+\alpha_{i+1}x_{i}\\\ \vdots\\\
x_{n-r}+\alpha_{n-r}x_{i}\end{pmatrix}\in\mathbb{R}^{n-r-1},$

such that
$W_{1}^{(r)}x^{(r)}=W_{1}^{(r+1)}x^{(r+1)}=W_{1}^{(r+1)}A^{(r)}(x^{(r)})$ for
all $x^{(r)}\in\mathbb{R}^{n-r}$. By construction, the matrix $A^{(r)}$ has
full rank. The new neural network $\Phi^{(\textup{(i)},r+1)}$ with
$W_{1}^{(r)}$ replaced by $W_{1}^{(r+1)}$ and $x^{(r)}$ replaced by
$x^{(r+1)}$ is up to the linear change of coordinates $A^{(r)}$ equivalent to
$\Phi^{(\textup{(i)},r)}$ and has a smaller architecture.

If $W_{1}^{(r+1)}$ has full rank, continue with step (ii) and define
$r_{0}=r+1$ and

$A:\mathbb{R}^{n}\rightarrow\mathbb{R}^{\bar{n}},\quad A\coloneqq
A^{(r)}\circ\ldots\circ A^{(0)},$

$\mathcal{Y}\coloneqq A(\mathcal{X})\subset\mathbb{R}^{\bar{n}}$,
$\bar{n}\coloneqq n-r-1$, and $W_{1}^{(\ast)}\coloneqq W_{1}^{(r_{0})}$. The
matrix $A$ has by Lemma 3.10 full rank $\bar{n}$, as all matrices $A^{(i)}$,
$i\in\\{0,\ldots,r\\}$ have full rank and the dimensions of the matrices are
monotone. The neural network
$\Phi^{(\textup{(i)},r_{0})}\in\Xi^{k}(\mathcal{Y},\mathbb{R})$ is up to the
linear change of coordinates $A$ equivalent to
$\Phi^{(\textup{(i)},0)}\in\Xi^{k}(\mathcal{X},\mathbb{R})$.

If $W_{1}^{(r+1)}$ has not full rank, repeat step (i) for the neural network
$\Phi^{(\textup{(i)},r)}$ with the counter $r$ increased by one. Lemma 3.11
guarantees that after a finite number of iterations, $W_{1}^{(r+1)}$ has full
rank and step (i) ends.

  2. (ii)

If this is the first iteration of step (ii), denote the feed-forward neural
network $\Phi^{(\textup{(i)},r_{0})}\in\Xi^{k}(\mathcal{Y},\mathbb{R})$
obtained from (i) with weight matrices
$(W_{1}^{(\ast)},\widetilde{W}_{1}^{(0)},W_{2}^{(0)},\ldots,W_{L}^{(0)},\widetilde{W}_{L}^{(0)})$
by $\Phi^{(\textup{(ii)},0)}$ and set $l=1$. If $L=1$, go to step (iii).

If $W_{l+1}^{(0)}\in\mathbb{R}^{m_{l+1}\times n_{l}}$ has full rank, set
$r_{l}=0$ and define
$\Phi^{(\textup{(ii)},l)}\coloneqq\Phi^{(\textup{(ii)},l-1)}$. If $l<L-1$,
increase the counter $l$ by one and repeat step (ii). If $l=L-1$, notice that
$\Phi^{(\textup{(ii)},L-1)}$ is equivalent to $\Phi^{(\textup{(ii)},0)}$ and
continue with step (iii).

For $r\geq 0$, if $W_{l+1}^{(r)}\in\mathbb{R}^{m_{l+1}\times(n_{l}-r)}$ has
not full rank, it has by assumption at least rank one and Lemma 3.8 guarantees
the existence of an feed-forward neural network, which is equivalent to
$\Phi^{(\textup{(ii)},l-1)}$, where the matrix $W_{l+1}^{(r)}$ is replaced by
a matrix $W_{l+1}^{(r+1)}\in\mathbb{R}^{m_{l+1}\times(n_{l}-r-1)}$ with the
same rank, $\widetilde{W}_{l}^{(r)}$ is replaced by a matrix
$\widetilde{W}_{l}^{(r+1)}\in\mathbb{R}^{(n_{l}-r-1)\times m_{l}}$, the bias
$\tilde{b}_{l}$ is replaced by a new bias and it holds
$W_{l+1}^{(r+1)}\widetilde{W}_{l}^{(r+1)}=W_{l+1}^{(r)}\widetilde{W}_{l}^{(r)}$.
As $\textup{rank}(W_{l+1}^{(r+1)})=\textup{rank}(W_{l+1}^{(r)})$, Lemma 3.11
implies that there exist an index $r_{l}$, such that after $r_{l}$
applications of Lemma 3.8, the matrix
$W_{l+1}^{(r_{l})}\in\mathbb{R}^{m_{l+1}\times(n_{l}-r_{l})}$ has full rank.
We denote the equivalent neural network with smaller architecture obtained
after applying Lemma 3.8 $r_{l}$ times to $\Phi^{(\textup{(ii)},l-1)}$ by
$\Phi^{(\textup{(ii)},l)}$. $\Phi^{(\textup{(ii)},l)}$ has the matrix
$W_{l+1}^{(0)}$ replaced by the full rank matrix
$W_{l+1}^{(r_{l})}\in\mathbb{R}^{m_{l+1}\times(n_{l}-r_{l})}$, the matrix
$\widetilde{W}_{l}^{(0)}$ replaced by a matrix
$\widetilde{W}_{l}^{(r_{l})}\in\mathbb{R}^{(n_{l}-r_{l})\times m_{l}}$ and the
bias $\tilde{b}_{l}$ replaced by a new bias. It holds
$W_{l+1}^{(r_{l})}\widetilde{W}_{l}^{(r_{l})}=W_{l+1}^{(0)}\widetilde{W}_{l}^{(0)}$
and as $\text{rank}(W_{l+1}^{(0)}\widetilde{W}_{l}^{(0)})>0$, the matrix
$\widetilde{W}_{l}^{(r_{l})}$ has at least rank one. If $l<L-1$, increase the
counter $l$ by one and repeat step (ii). If $l=L-1$, notice that
$\Phi^{(\textup{(ii)},L-1)}$ is equivalent to $\Phi^{(\textup{(ii)},0)}$ and
continue with step (iii).

  3. (iii)

If this is the first iteration of step (iii), denote the feed-forward neural
network
$\Phi^{(\textup{(ii)},L-1)}(\mathcal{Y},\mathbb{R})\in\Xi^{k}(\mathcal{Y},\mathbb{R})$
obtained from (ii) with weight matrices
$(W_{1}^{(\ast)},\widetilde{W}_{1}^{(r_{1})},W_{2}^{(r_{1})},\ldots,W_{L}^{(r_{L-1})},\widetilde{W}_{L}^{(0)})$
by $\Phi^{(\textup{(iii)},0)}$ and set $l=1$. If $L=1$, go to step (iv).

If $\widetilde{W}_{l}^{(r_{l})}\in\mathbb{R}^{(n_{l}-r_{l})\times m_{l}}$ has
full rank, set $\tilde{r}_{l}=0$,
$\widetilde{W}_{l}^{(\ast)}=\widetilde{W}_{l}^{(r_{l})}$,
$W_{l+1}^{(\ast)}=W_{l+1}^{(r_{l})}$ and define
$\Phi^{(\textup{(iii)},l)}=\Phi^{(\textup{(iii)},l-1)}$. If $l<L-1$, increase
the counter $l$ by one and repeat step (iii). If $l=L-1$, notice that
$\Phi^{(\textup{(iii)},L-1)}$ is equivalent to $\Phi^{(\textup{(iii)},0)}$ and
continue with step (iv).

For $r\geq 0$, if
$\widetilde{W}_{l}^{(r_{l}+r)}\in\mathbb{R}^{(n_{l}-r_{l}-r)\times m_{l}}$ has
not full rank, it has by step (ii) at least rank one and Lemma 3.9 guarantees
the existence of an feed-forward neural network, which is equivalent to
$\Phi^{(\textup{(iii)},l-1)}$, where the matrix
$\widetilde{W}_{l}^{(r_{l}+r)}$ is replaced by a matrix
$\widetilde{W}_{l}^{(r_{l}+r+1)}\in\mathbb{R}^{(n_{l}-r_{l}-r-1)\times m_{l}}$
with the same rank, the full rank matrix $W_{l+1}^{(r_{l}+r)}$ is replaced by
a full rank matrix
$W_{l+1}^{(r_{l}+r+1)}\in\mathbb{R}^{m_{l+1}\times(n_{l}-r_{l}-r-1)}$ and the
bias $\tilde{b}_{l}$ is replaced by a new bias. As the rank of
$\widetilde{W}_{l}^{(r_{l}+r+1)}$ is the same as the rank of
$\widetilde{W}_{l}^{(r_{l}+r)}$, Lemma 3.11 implies that there exist an index
$\tilde{r}_{l}$, such that after $\tilde{r}_{l}$ applications of Lemma 3.9,
the matrix
$\widetilde{W}_{l}^{(r_{l}+\tilde{r}_{l})}\in\mathbb{R}^{(n_{l}-r_{l}-\tilde{r}_{l})\times
m_{l}}$ has full rank. We denote the equivalent neural network obtained after
applying Lemma 3.9 $\tilde{r}_{l}$ times to $\Phi^{(\textup{(iii)},l-1)}$ by
$\Phi^{(\textup{(iii)},l)}$. $\Phi^{(\textup{(iii)},l)}$ has the matrix
$\widetilde{W}_{l}^{(r_{l})}$ replaced by the full rank matrix
$\widetilde{W}_{l}^{(\ast)}\coloneqq\widetilde{W}_{l}^{(r_{l}+\tilde{r}_{l})}\in\mathbb{R}^{(n_{l}-r_{l}-\tilde{r}_{l})\times
m_{l}}$, the full rank matrix $W_{l+1}^{(r_{l})}$ replaced by the full rank
matrix $W_{l+1}^{(\ast)}\coloneqq
W_{l+1}^{(r_{l}+\tilde{r}_{l})}\in\mathbb{R}^{m_{l+1}\times(n_{l}-r_{l}-\tilde{r}_{l})}$
and the bias $\tilde{b}_{l}$ replaced by a new bias. If $l<L-1$, increase the
counter $l$ by one and repeat step (iii). If $l=L-1$, notice that
$\Phi^{(\textup{(iii)},L-1)}$ is equivalent to $\Phi^{(\textup{(iii)},0)}$ and
continue with step (iv).

  4. (iv)

Denote the feed-forward neural network
$\Phi^{(\textup{(iii)},L-1)}\in\Xi^{k}(\mathcal{Y},\mathbb{R})$ obtained from
(iii) with weight matrices

$W^{\ast}\coloneqq\left(W_{1}^{(\ast)},\widetilde{W}_{1}^{(\ast)},W_{2}^{(\ast)},\ldots,\widetilde{W}_{L-1}^{(\ast)},W_{L}^{(\ast)},\widetilde{W}_{L}^{(0)}\right)$

by $\Phi^{(\textup{(iv)},0)}$. By step (i), the matrix $W_{1}^{(\ast)}$ has
full rank and by steps (ii) and (iii), all the matrices
$\widetilde{W}_{1}^{(\ast)}$, $W_{2}^{(\ast)}$, $\ldots$,
$\widetilde{W}_{L-1}^{(\ast)}$, $W_{L}^{(\ast)}$ have full rank. As
$\widetilde{W}_{L}^{(0)}\in\mathbb{R}^{n_{L}\times m_{L}}=\mathbb{R}^{1\times
m_{L}}$ and $\widetilde{W}_{L}^{(0)}$ has by assumption at least rank one, it
holds $\text{rank}(\widetilde{W}_{L}^{(0)})=1$, such that
$\widetilde{W}_{L}^{(\ast)}=\widetilde{W}_{L}^{(0)}$ has full rank.
Consequently all matrices of $W^{\ast}$ are full rank matrices, such that
$\Phi^{(\textup{(iv)},0)}\in\Xi^{k}_{\mathbb{W}^{\ast}}(\mathcal{Y},\mathbb{R})$.
$\Phi^{(\textup{(iv)},0)}=\Phi^{(\textup{(iii)},L-1)}$ is equivalent to
$\Phi^{(\textup{(iii)},0)}=\Phi^{(\textup{(ii)},L-1)}$, which is equivalent to
$\Phi^{(\textup{(ii)},0)}=\Phi^{(\textup{(i)},r_{0})}$, which is up to the
linear change of coordinates $A$ defined in step (i) equivalent to
$\Phi^{(\textup{(i)},0)}=\Phi\in\Xi^{k}_{\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$.
The architecture $\Phi^{(\textup{(iv)},0)}$ is smaller than the architecture
$\Phi$, as at least one weight matrix of $\Phi$ has not full rank, such that
in at least one of the steps (i), (ii) and (iii) the number of nodes in one of
the layers $h_{l}$, $l\in\\{0,\ldots,L-1\\}$ is reduced by one, which implies
the result.

For case (b) we consider a classical feed-forward neural network
$\Phi\in\Xi^{k}_{\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$
with weight matrices
$W=(W_{1},\widetilde{W}_{1},W_{2},\ldots,W_{L},\widetilde{W}_{L})$, biases
$b=(b_{1},\tilde{b}_{1},\ldots,b_{L},\tilde{b}_{L})$ and assume that
$\textup{rank}(W_{1})=0$ or $\textup{rank}(\widetilde{W}_{L})=0$ or
$\textup{rank}(W_{l+1}\widetilde{W}_{l})=0$ for some $l\in\\{1,\ldots,L-1\\}$.
Consequently at least one of the vectors $h_{0}$ or $\sigma_{l}(s_{l})$,
$l\in\\{1,\ldots,L\\}$ is multiplied with a zero matrix, such that
$\Phi(x)=c_{W,b}$ for all $x\in\mathcal{X}$, where $c_{W,b}$ is a scalar
independent of $x$, only depending on $W$ and $b$. $\Phi$ is equivalent to the
feed-forward neural network
$\overline{\Phi}\in\Xi^{k}(\mathcal{X},\mathbb{R})$ defined by
$\overline{L}=1$, $\overline{W}_{1}=0\in\mathbb{R}^{1\times n}$,
$\overline{b}_{1}=0\in\mathbb{R}$,
$\overline{\widetilde{W}}_{1}=0\in\mathbb{R}$ and
$\overline{\tilde{b}}_{1}=c_{W,b}\in\mathbb{R}$ as
$\overline{\Phi}(x)=c_{W,b}$ for all $x\in\mathcal{X}$. If
$\overline{\Phi}\neq\Phi$, $\overline{\Phi}$ has a smaller architecture than
$\Phi$, as $\overline{\Phi}$ only consists of the $n$-dimensional input layer,
the one-dimensional intermediate layer and the one-dimensional output layer. ∎

######  Remark 3.13.

The rank of the weight matrices of the feed-forward neural network $\Phi$ in
Theorem 3.12 determines the widths of the layers of the equivalent neural
network $\overline{\Phi}$. Hence, we refer with the term ‘normal form’ of a
feed-forward neural network to the geometry of the smallest equivalent neural
network, i.e. to the number and the widths of the layers. The proof of Theorem
3.12 is constructive, but the chosen weights and biases of the equivalent
neural network architectures are not unique. For a given neural network
$\Phi$, there exists a unique geometry of the normal form architecture
$\overline{\Phi}$, but multiple realizations of the weights and biases, which
define equivalent neural networks are possible.

In the following example, we illustrate the explicit algorithm of the proof of
Theorem 3.12(a) for a two-layer neural network architecture.

######  Example 3.14.

Consider the neural network
$\Phi=\Phi^{(\textup{(i)},0)}\in\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})$
with $\mathcal{X}=(-1,1)\times(-1,1)\subset\mathbb{R}^{2}$ and $L=2$ defined
by the weight matrices

$\displaystyle W_{1}^{(0)}=\begin{pmatrix}-1&2\\\
2&-4\end{pmatrix},\quad\widetilde{W}_{1}^{(0)}=\begin{pmatrix}1&0\\\ 2&3\\\
0&1\end{pmatrix},\quad W_{2}^{(0)}=\begin{pmatrix}1&0&2\\\ 0&2&2\\\
1&-1&1\end{pmatrix},\quad\widetilde{W}_{2}^{(0)}=\begin{pmatrix}-1&1&2\end{pmatrix},$

and arbitrary biases, see also Figure 3.44(a). It holds
$\textup{rank}(W_{1}^{(0)})=1<2$, $\textup{rank}(\widetilde{W}_{1}^{(0)})=2$,
$\textup{rank}(W_{2}^{(0)})=2<3$ and
$\textup{rank}(\widetilde{W}_{2}^{(0)})=1$, such that
$W^{(0)}=(W_{1}^{(0)},\widetilde{W}_{1}^{(0)},W_{2}^{(0)},\widetilde{W}_{2}^{(0)})\in\mathbb{W}\setminus\mathbb{W}^{\ast}$.
As $\textup{rank}(W_{1}^{(0)})>0$,
$\textup{rank}(W_{2}^{(0)}\widetilde{W}_{1}^{(0)})=1>0$ and
$\textup{rank}(\widetilde{W}_{2}^{(0)})>0$, Theorem 3.12(a) implies, that
there exists a neural network $\overline{\Phi}$, which is up to a linear
change of coordinates equivalent to $\Phi$ and which has only full rank
matrices. For step (i) of the proof of Theorem 3.12(a), we find
$[W_{1}^{(0)}]_{2}=-2\cdot[W_{1}^{(0)}]_{1}$, such that

$A:\mathbb{R}^{2}\rightarrow\mathbb{R},\qquad A\cdot\begin{pmatrix}x_{1}\\\
x_{2}\end{pmatrix}=\begin{pmatrix}1&-2\end{pmatrix}\cdot\begin{pmatrix}x_{1}\\\
x_{2}\end{pmatrix}=x_{1}-2x_{2},\qquad\mathcal{Y}=A(\mathcal{X})=(-3,3)\subset\mathbb{R},$

and $\Phi^{(\textup{(i)},0)}$ is up to the linear change of coordinates $A$
equivalent to the neural network $\Phi^{(\textup{(i)},1)}$, where the matrix
$W_{1}^{(0)}$ is replaced by the matrix $W_{1}^{(\ast)}=\begin{pmatrix}-1\\\
2\end{pmatrix}$. In step (ii) Lemma 3.8 is applied and as
$[W_{2}^{(0)}]_{3}=2\cdot[W_{2}^{(0)}]_{1}+1\cdot[W_{2}^{(0)}]_{2}$, the
matrices $\widetilde{W}_{1}^{(0)}$ and $W_{2}^{(0)}$ are replaced by

$\widetilde{W}_{1}^{(1)}=\begin{pmatrix}1+2\cdot 0&0+2\cdot 1\\\ 2+1\cdot
0&3+1\cdot 1\end{pmatrix}=\begin{pmatrix}1&2\\\ 2&4\end{pmatrix},\qquad
W_{2}^{(1)}=\begin{pmatrix}1&0\\\ 0&2\\\ 1&-1\end{pmatrix},$

and the bias $\tilde{b}_{1}$ is adapted accordingly. The obtained architecture
$\Phi^{(\textup{(ii)},1)}$ is equivalent to $\Phi^{(\textup{(i)},1)}$. We
continue with step (iii) since $W_{2}^{(1)}$ is a full rank matrix, but
$\textup{rank}(\widetilde{W}_{1}^{(1)})=1<2$. As
$[[\widetilde{W}_{1}^{(1)}]^{\top}]_{2}=2\cdot[[\widetilde{W}_{1}^{(1)}]^{\top}]_{1}$,
the application of Lemma 3.9 in step (iii) yields

$\widetilde{W}_{1}^{(\ast)}=\widetilde{W}_{1}^{(2)}=(1,2),\qquad
W_{2}^{(\ast)}=W_{2}^{(2)}=\begin{pmatrix}1+2\cdot 0\\\ 0+2\cdot 2\\\ 1-2\cdot
1\end{pmatrix}=\begin{pmatrix}1\\\ 4\\\ -1\end{pmatrix},$

and the bias $\tilde{b}_{1}$ is again adapted accordingly. The resulting
architecture is denoted by $\Phi^{(\textup{(iii)},1)}$. As
$\widetilde{W}_{1}^{(\ast)}$ and $W_{2}^{(\ast)}$ have both full rank, we
continue with step (iv), which implies with
$\widetilde{W}_{2}^{(\ast)}=\widetilde{W}_{2}^{(0)}$ that
$\Phi^{(\textup{(iv)},0)}=\Phi^{(\textup{(iii)},1)}$ has only full rank
matrices and is up to the linear change of coordinates $A$ equivalent to the
neural network architecture
$\Phi=\Phi^{(\textup{(i)},0)}\in\Xi^{k}_{\textup{A},\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$.
The equivalent normal form
$\overline{\Phi}\coloneqq\Phi^{(\textup{(iv)},0)}\in\Xi_{\textup{B},\mathbb{W}^{\ast}}^{k}(\mathcal{Y},\mathbb{R})$
has a bottleneck and is visualized in Figure 3.44(b).

(a) Example of a two-layer augmented neural network
$\Phi\in\Xi^{k}_{\textup{A},\mathbb{W}\setminus\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$,
where the two weight matrices $W_{1}^{(0)}$ and $W_{2}^{(0)}$ have both not
full rank.

(b) Two-layer neural network
$\overline{\Phi}\in\Xi^{k}_{\textup{B},\mathbb{W}^{\ast}}(\mathcal{Y},\mathbb{R})$
with a bottleneck, which has only full rank matrices and which is up to a
linear change of coordinates equivalent to the neural network architecture
$\Phi$ of 4(a).

Figure 3.4: Equivalent neural network architectures of Example 3.14 to
illustrate Theorem 3.12(a).

Theorem 3.12 is an explicit algorithm showing equivalence up to a linear
change of coordinates. Due to the linear change of coordinates, it is not
guaranteed that the regularity of the critical points of equivalent neural
networks stay the same. The following theorem shows that if a coordinate
transformation is necessary to obtain an equivalent neural network with full
rank matrices, it is possible that degenerate critical points become non-
degenerate.

######  Theorem 3.15.

Let $\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$, $k\geq 2$,
$\mathcal{X}\subset\mathbb{R}^{n}$ be a classical feed-forward neural network,
which is up to the linear change of coordinates $A\in\mathbb{R}^{\bar{n}\times
n}$, $\bar{n}\leq n$, $\textup{rank}(A)=\bar{n}$ equivalent to
$\overline{\Phi}\in\Xi^{k}(\mathcal{Y},\mathbb{R})$,
$\mathcal{Y}=A(\mathcal{X})\subset\mathbb{R}^{\bar{n}}$. Then

$\overline{\Phi}\in(\mathcal{C}1)^{k}(\mathcal{Y},\mathbb{R})\quad\Leftrightarrow\quad\Phi\in(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R}).$

If $\bar{n}=n$, it holds additionally

$\displaystyle\overline{\Phi}\in(\mathcal{C}2)^{k}(\mathcal{Y},\mathbb{R})\quad$
$\displaystyle\Leftrightarrow\quad\Phi\in(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R}),$
$\displaystyle\overline{\Phi}\in(\mathcal{C}3)^{k}(\mathcal{Y},\mathbb{R})\quad$
$\displaystyle\Leftrightarrow\quad\Phi\in(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R}).$

If $\bar{n}<n$, then $\Phi\notin(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$
and it holds

$\overline{\Phi}\in(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})\cup(\mathcal{C}3)^{k}(\mathcal{Y},\mathbb{R})\quad\Leftrightarrow\quad\Phi\in(\mathcal{C}3)^{k}(\mathcal{X},\mathbb{R}).$

###### Proof.

As $\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$ is up to the linear change of
coordinates $A$ equivalent to
$\overline{\Phi}\in\Xi^{k}(\mathcal{Y},\mathbb{R})$, it holds

$\Phi(x)=\overline{\Phi}(Ax)\qquad\text{for all }x\in\mathcal{X}.$

Calculating the gradient leads to

$\nabla\Phi(x)=A^{\top}\cdot\nabla\overline{\Phi}(Ax)\qquad\text{for all
}x\in\mathcal{X}.$

If $\nabla\overline{\Phi}(Ax)=0$ for some $x\in\mathcal{X}$ with
$y=Ax\in\mathcal{Y}$, then $\nabla\overline{\Phi}(Ax)=0$ for all
$x\in\mathcal{X}_{y}$, where

$\mathcal{X}_{y}\coloneqq\left\\{x\in\mathcal{X}:Ax=y\in\mathcal{Y}\right\\}.$

Given $y\in\mathcal{Y}$, $\nabla\overline{\Phi}(y)=0$ implies that
$\nabla\Phi(x)=0$ for all $x\in\mathcal{X}_{y}$. As the matrix
$A^{\top}\in\mathbb{R}^{n\times\bar{n}}$ has rank $\bar{n}\leq n$, the linear
system $A^{\top}\cdot\nabla\overline{\Phi}(y)=0$ has only the solution
$\nabla\overline{\Phi}(y)=0$, such that from $\nabla\Phi(x)=0$ for some
$x\in\mathcal{X}$ it follows $\nabla\overline{\Phi}(Ax)=0$ for
$Ax\in\mathcal{Y}$. Hence, there exists a bijection between the critical
points $y\in\mathcal{Y}$ of $\overline{\Phi}$ and the set of critical points
$\mathcal{X}_{y}\subset\mathcal{X}$ of $\Phi$. Especially, $\overline{\Phi}$
has critical points if and only if $\Phi$ has critical points, such that the
first assertion follows.

To determine the regularity of the critical points, we calculate the Hessian
matrices of $\Phi$ and $\overline{\Phi}$:

$H_{\Phi}(x)=\nabla(\nabla\Phi(x)^{\top})=\nabla(\nabla\overline{\Phi}(Ax)^{\top}\cdot
A)=A^{\top}\cdot H_{\overline{\Phi}}(x)\cdot A\qquad\text{for all
}x\in\mathcal{X}.$

As the matrix $A$ has rank $\bar{n}$ and $H_{\overline{\Phi}}(x)$ is a
$\bar{n}\times\bar{n}$ matrix, it holds

$\text{rank}(H_{\Phi}(x))=\text{rank}(A^{\top}\cdot
H_{\overline{\Phi}}(x)\cdot A)=\text{rank}(A^{\top}\cdot
H_{\overline{\Phi}}(x))=\text{rank}(H_{\overline{\Phi}}(x))\qquad\text{for all
}x\in\mathcal{X},$

which implies with the fact that $H_{\Phi}(x)$ is a $n\times n$ matrix the
remaining assertions of the theorem. ∎

The following example shows a neural network with degenerate critical points,
which is up to a linear change of coordinate equivalent to a neural network
with only non-degenerate critical points. It illustrates the case of Theorem
3.15, where under a linear change of coordinates represented by a full rank
matrix $A$, the class of the neural network can change.

######  Example 3.16.

Consider the neural network $\Phi\in\Xi^{\infty}(\mathbb{R}^{2},\mathbb{R})$
with $L=1$ defined by the weight matrices

$W_{1}=\begin{pmatrix}1&2\\\
2&4\end{pmatrix},\qquad\widetilde{W}_{1}=\begin{pmatrix}2&-1\end{pmatrix},\qquad
b_{1}=\begin{pmatrix}0\\\ 0\end{pmatrix},\qquad\tilde{b}_{1}=0,$

arbitrary biases and soft-plus activation functions
$[\sigma_{1}]_{1}(x)=[\sigma_{1}]_{2}(x)=\ln(1+\exp(x))$, see Figure 3.55(a).
As $\textup{rank}(W_{1})=1<2$ and $\textup{rank}(\widetilde{W}_{1})=1$,
Theorem 3.12(a) implies that there exists a neural network architecture
$\overline{\Phi}\in\Xi^{\infty}(\mathbb{R},\mathbb{R})$, which is up to a
linear change of coordinates $A:\mathbb{R}^{2}\rightarrow\mathbb{R}$
equivalent to $\Phi$. As $[W_{1}]_{2}=2[W_{1}]_{1}$, it follows by the proof
of Theorem 3.12(a) that the weights of $\overline{\Phi}$ and the matrix $A$
are given by

$\overline{W}_{1}=\begin{pmatrix}1\\\
2\end{pmatrix},\qquad\overline{\widetilde{W}}_{1}=\begin{pmatrix}2&-1\end{pmatrix},\qquad\bar{b}_{1}=\begin{pmatrix}0\\\
0\end{pmatrix},\qquad\bar{\tilde{b}}_{1}=0,\qquad
A=\begin{pmatrix}1&2\end{pmatrix},$

such that $\Phi(x_{1},x_{2})=\overline{\Phi}(x_{1}+2x_{2})=\Phi(y)$ for
$y=x_{1}+2x_{2}$. We verify now the properties of Theorem 3.15. It holds

$\overline{\Phi}(y)=2\ln(1+\exp(y))-\ln(1+\exp(2y))$

with gradient

$\nabla\overline{\Phi}(y)=\frac{2\exp(y)(1-\exp(y))}{(1+\exp(y))(1+\exp(2y))},$

such that $\overline{\Phi}$ has exactly one critical point at $y^{\ast}=0$.
The critical point is non-degenerate as

$H_{\overline{\Phi}}(y^{\ast})=-0.5\neq 0.$

Consequently $\overline{\Phi}$ is of class
$(\mathcal{C}2)^{\infty}(\mathbb{R},\mathbb{R})$. By Theorem 3.15 the original
neural network $\Phi$ has to be of class
$(\mathcal{C}3)^{\infty}(\mathbb{R}^{2},\mathbb{R})$. It holds

$\Phi(x_{1},x_{2})=2\ln(1+\exp(x_{1}+2x_{2}))-\ln(1+\exp(2x_{1}+4x_{2})),$

with gradient

$\nabla\overline{\Phi}(x_{1},x_{2})=\begin{pmatrix}\frac{2\exp(x_{1}+2x_{2})(1-\exp(x_{1}+2x_{2}))}{(1+\exp(x_{1}+2x_{2}))(1+\exp(2x_{1}+4x_{2}))}\\\
\frac{4\exp(x_{1}+2x_{2})(1-\exp(x_{1}+2x_{2}))}{(1+\exp(x_{1}+2x_{2}))(1+\exp(2x_{1}+4x_{2}))}\end{pmatrix},$

such that $\Phi$ has a line of equilibria defined by $x_{1}+2x_{2}=0$. As the
entries of $\nabla\overline{\Phi}(x_{1},x_{2})$ are linearly dependent, the
Hessian matrix $H_{\Phi}(x_{1},x_{2})$ is for every
$(x_{1},x_{2})\in\mathbb{R}^{2}$ singular, which implies that all equilibria
of $\Phi$ are degenerate and $\Phi$ is of class
$(\mathcal{C}3)^{\infty}(\mathbb{R}^{2},\mathbb{R})$.

.

(a) Example of a one-layer neural network
$\Phi\in\Xi^{\infty}(\mathbb{R}^{2},\mathbb{R})$ of class
$(\mathcal{C}3)^{\infty}(\mathbb{R}^{2},\mathbb{R})$, which has one line of
degenerate equilibria.

.

(b) One-layer neural network
$\overline{\Phi}\in\Xi^{\infty}(\mathbb{R},\mathbb{R})$ of class
$(\mathcal{C}2)^{\infty}(\mathbb{R},\mathbb{R})$, which is up to a linear
change of coordinates equivalent to $\Phi$ of 5(a). $\overline{\Phi}$ has one
non-degenerate critical point.

.

Figure 3.5: Equivalent neural network architectures of Example 3.16 to
illustrate Theorem 3.15.

If we aim to have a large expressivity of classical feed-forward neural
networks with respect to the space of $k$ times continuously differentiable
functions, Theorem 3.15 implies that we should choose the input dimension as
small as possible. If the input dimension $n$ can be reduced, the considered
architecture cannot be of class $(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$,
so at least one critical point is degenerate. Consequently, the generic class
of Morse functions, where every critical point is non-degenerate, cannot be
represented.

Due to Lemma 3.6 and Theorems 3.12 and 3.15, we assume in the upcoming
analysis, that the considered neural network architecture has only full rank
matrices, as every neural network with non-trivial dynamics is up to a linear
change of coordinates equivalent to a smaller architecture in normal form and
the set of matrices, where at least one weight matrix has not full rank, is a
zero set in the weight space.

###  3.3 Existence of Critical Points

In this section, we study the existence of critical points dependent on the
special architecture of the neural network. To that purpose, we first
calculate the network gradient.

######  Lemma 3.17.

Let $\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$, $k\geq 1$ be a classical feed-
forward neural network with weight matrices
$W=(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})\in\mathbb{W}$ and
biases $b=(b_{1},\tilde{b}_{1},\ldots,b_{L},\tilde{b}_{L})\in\mathbb{B}$. Then

$\nabla\Phi(x)=\left[\widetilde{W}_{L}\Psi_{L}(s_{L})W_{L}\ldots\widetilde{W}_{1}\Psi_{1}(s_{1})W_{1}\right]^{\top}\in\mathbb{R}^{n},$

where
$\Psi_{l}(s_{l})=\textup{diag}([\sigma_{l}]_{i}^{\prime}([s_{l}]_{i}))\in\mathbb{R}^{m_{l}\times
m_{l}}$, $i\in\\{1,\ldots,m_{l}\\}$ is a diagonal matrix.

###### Proof.

Due to the layer structure of the feed-forward neural network it holds for
$l\in\\{1,.\ldots,L-1\\}$:

$\Phi(x)=h_{L}=\widetilde{W}_{L}\sigma_{L}(W_{L}(\ldots\sigma_{2}(W_{2}(\widetilde{W}_{1}\sigma_{1}(W_{1}x+b_{1})+\tilde{b}_{1})+b_{2})\ldots)+b_{L})+\tilde{b}_{L}.$

By Lemma 3.1 it holds $\Phi\in C^{1}(\mathcal{X},\mathbb{R})$, such that the
multi-dimensional chain rule implies

$\frac{\mathrm{d}\Phi}{\mathrm{d}x}=\widetilde{W}_{L}\Psi_{L}(s_{L})W_{L}\ldots\widetilde{W}_{1}\Psi_{1}(s_{1})W_{1}\in\mathbb{R}^{1\times
n},$

where
$\Psi_{l}(s_{l})=\textup{diag}([\sigma_{l}]_{i}^{\prime}([s_{l}]_{i}))\in\mathbb{R}^{m_{l}\times
m_{l}}$, $i\in\\{1,\ldots,m_{l}\\}$ is a diagonal matrix. The result follows
by taking the transpose. ∎

Due to the reasons established in Section 3.2, we restrict our upcoming
analysis to neural networks
$\Phi\in\Xi^{k}_{\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$ in normal form.
The upcoming theorems established for networks in
$\Xi^{k}_{\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$ can be generalized to
general networks in $\Xi^{k}(\mathcal{X},\mathbb{R})$ by using the statement
of Lemma 3.6, that $\textup{vecm}(\mathbb{W}\setminus\mathbb{W}^{\ast})$ is a
zero set in $\mathbb{R}^{N_{W}}$. For non-augmented classical feed-forward
neural networks $\Phi$, the following theorem shows, that $\Phi$ has no
critical points if all weight matrices have full rank.

######  Theorem 3.18.

Any non-augmented classical feed-forward neural network
$\Phi\in\Xi^{k}_{\textup{N},\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$,
$k\geq 1$, with weight matrices $W\in\mathbb{W}^{\ast}$ has no critical point,
i.e. $\nabla\Phi(x)\neq 0$ for all $x\in\mathcal{X}$. Consequently it holds
for $k\geq 1$

$\Xi^{k}_{\textup{N},\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})\subset(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R}).$

This implies that for all weights
$(\textup{vecm}(W);\textup{stk}(b))\in\mathbb{R}^{N_{W}+N_{B}}$,
$W\in\mathbb{W}$, $b\in\mathbb{B}$ except possibly for a zero set in
$\mathbb{R}^{N_{W}+N_{B}}$ w.r.t. the Lebesgue measure, a non-augmented
classical feed-forward neural network
$\Phi\in\Xi^{k}_{\textup{N}}(\mathcal{X},\mathbb{R})$, $k\geq 1$ is of class
$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$ and hence a Morse function.

###### Proof.

Let $\Phi\in\Xi^{k}_{N,\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$ with weight
matrices $W=(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})$. By
Lemma 3.17 it holds

$\nabla\Phi(x)=\left[\widetilde{W}_{L}\Psi_{L}(s_{L})W_{L}\ldots\widetilde{W}_{1}\Psi_{1}(s_{1})W_{1}\right]^{\top}\in\mathbb{R}^{n},$

where
$\Psi_{l}(s_{l})=\textup{diag}([\sigma_{l}]_{i}^{\prime}([s_{l}]_{i}))\in\mathbb{R}^{m_{l}\times
m_{l}}$, $i\in\\{1,\ldots,m_{l}\\}$, is a diagonal matrix with
$s_{l}=W_{l}h_{l-1}+b_{l}$. As $[\sigma_{l}]_{i}\in
C^{k}(\mathbb{R},\mathbb{R})$, $k\geq 1$ is by Definition 3.2 strictly
monotone for $l\in\\{1,\ldots,L\\}$, $i\in\\{1,\ldots,m_{l}\\}$, it either
holds $[\sigma_{l}]_{i}^{\prime}>0$ or $[\sigma_{l}]_{i}^{\prime}<0$.
Consequently each matrix $\Psi_{l}(s_{l})$, $l\in\\{1,\ldots,L\\}$ has non-
zero diagonal entries and hence full rank. Due to the assumption
$W\in\mathbb{W}^{\ast}$ all matrices $W_{l}$ and $\widetilde{W}_{l}$ have full
rank for $l\in\\{1,\ldots,L\\}$. As the neural network is non-augmented, the
dimensions of the full rank matrices
$\widetilde{W}_{L},\Psi_{L}(s_{L}),\ldots,\Psi_{1}(s_{1}),W_{1}$ are
monotonically increasing, such that Lemma 3.10 implies that the vector
$[\nabla\Phi(x)]^{\top}\in\mathbb{R}^{1\times n}$ has independently of
$x\in\mathcal{X}$ always rank one. Consequently $\nabla\Phi(x)\neq 0$ for all
$x\in\mathcal{X}$. By Definition 2.3 it follows
$\Xi^{k}_{\textup{N},\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})\subset(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$.
The second statement is a consequence of the first part and Lemma 3.6: as
$\textup{vecm}(\mathbb{W}\setminus\mathbb{W}^{\ast})$ is a zero set w.r.t. the
Lebesgue measure in $\mathbb{R}^{N_{W}}$, it follows that the set of non-full
rank matrices and arbitrary biases
$\textup{vecm}(\mathbb{W}\setminus\mathbb{W}^{\ast})\times\textup{stk}(\mathbb{B})$
is a zero set in $\mathbb{R}^{N_{W}+N_{B}}$ w.r.t. the Lebesgue measure. ∎

######  Example 3.19.

Consider the one-layer neural network architecture
$\Phi\in\Xi^{k}_{\textup{N}}(\mathbb{R}^{3},\mathbb{R})$, $k\geq 1$ with $L=1$
defined by the weight matrices

$W_{1}=\begin{pmatrix}w_{11}&w_{12}&w_{13}\\\
w_{21}&w_{22}&w_{23}\end{pmatrix}\in\mathbb{R}^{2\times
3},\qquad\widetilde{W}_{1}=(\widetilde{w}_{1},\widetilde{w}_{2})\in\mathbb{R}^{1\times
2},$

and arbitrary biases, see Figure 3.6. By Lemma 3.17 it holds

$\displaystyle\nabla\Phi(x)$ $\displaystyle=\begin{pmatrix}w_{11}&w_{21}\\\
w_{12}&w_{22}\\\
w_{13}&w_{23}\end{pmatrix}\begin{pmatrix}[\sigma_{1}]_{1}^{\prime}([s_{1}]_{1})&0\\\
0&[\sigma_{1}]_{2}^{\prime}([s_{1}]_{2})\end{pmatrix}\begin{pmatrix}\widetilde{w}_{1}\\\
\widetilde{w}_{2}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\widetilde{w}_{1}w_{11}[\sigma_{1}]_{1}^{\prime}([s_{1}]_{1})+\widetilde{w}_{2}w_{21}[\sigma_{1}]_{2}^{\prime}([s_{1}]_{2})\\\
\widetilde{w}_{1}w_{12}[\sigma_{1}]_{1}^{\prime}([s_{1}]_{1})+\widetilde{w}_{2}w_{22}[\sigma_{1}]_{2}^{\prime}([s_{1}]_{2})\\\
\widetilde{w}_{1}w_{13}[\sigma_{1}]_{1}^{\prime}([s_{1}]_{1})+\widetilde{w}_{2}w_{23}[\sigma_{1}]_{2}^{\prime}([s_{1}]_{2})\end{pmatrix}.$

By Theorem 3.18, there exists no critical point if $W_{1}$ and
$\widetilde{W}_{1}$ have both full rank. This is the case, as if
$\nabla\Phi(x)=0$ for some $x\in\mathcal{X}$ then

$\widetilde{w}_{1}[\sigma_{1}]_{1}^{\prime}([s_{1}]_{1})\begin{pmatrix}w_{11}\\\
w_{12}\\\
w_{13}\end{pmatrix}+\widetilde{w}_{2}[\sigma_{1}]_{2}^{\prime}([s_{1}]_{2})\begin{pmatrix}w_{21}\\\
w_{22}\\\ w_{23}\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\end{pmatrix},$

such that either $W_{1}$ has only rank 1 as its columns are linearly dependent
or the matrix $\widetilde{W}_{1}$ is the zero matrix and has rank 0.

Figure 3.6: One-layer non-augmented neural network architecture
$\Phi\in\Xi^{k}_{\textup{N}}(\mathbb{R}^{3},\mathbb{R})$ of Example 3.19.

In contrast to non-augmented neural networks, critical points can exist in the
case of augmented or bottleneck architectures. To show this statement in
Theorem 3.21, we need the following lemma.

######  Lemma 3.20.

Given $A\in\mathbb{R}^{1\times n}$, $\textup{rank}(A)=1$ and
$C\in\mathbb{R}^{1\times m}$, $\textup{rank}(C)=1$ with $n\leq m$, the linear
system $AB=C$ always has a full rank solution $B\in\mathbb{R}^{n\times m}$,
$\textup{rank}(B)=n$.

###### Proof.

As by assumption $\text{rank}(A)=\text{rank}(A|C)=1$, the Rouché-Capelli
Theorem [25] guarantees the existence of a solution to the linear system. In
the following we show via an explicit construction, that the solution $B$ can
be chosen as a full rank matrix. Denote by
$\overline{A}=[A]_{i_{1},\ldots,i_{\bar{n}}}\in\mathbb{R}^{1\times\bar{n}}$,
$\bar{n}\leq n$, $\\{i_{1},\ldots,i_{\bar{n}}\\}\subset\\{1,\ldots,n\\}$ the
submatrix of $A$, which consists only of the non-zero entries of $A$, i.e.
$[A]_{i_{k}}\neq 0$ for all $k\in\\{1,\ldots,\bar{n}\\}$ and denote the non-
zero entries of $C$ by
$[C]_{j_{1},\ldots,j_{\overline{m}}}\in\mathbb{R}^{1\times\overline{m}}$,
$\overline{m}\leq m$, i.e. $[C]_{j_{k}}\neq 0$ for all
$k\in\\{1,\ldots,\overline{m}\\}$. If $\overline{m}\geq\bar{n}$, we define the
following matrix entries of the submatrix
$[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}$:

$\displaystyle[B]_{i_{k},j_{k}}$
$\displaystyle=\frac{[C]_{j_{k}}}{[A]_{i_{k}}}\neq 0,\qquad$
$\displaystyle\text{if }k\in\\{1,\ldots,\bar{n}\\},$
$\displaystyle[B]_{i_{\bar{n}},j_{k}}$
$\displaystyle=\frac{[C]_{j_{k}}}{[A]_{i_{\bar{n}}}}\neq 0,\qquad$
$\displaystyle\text{if }k\in\\{\bar{n}+1,\ldots,\overline{m}\\},$

and set all other matrix entries to zero. By construction,
$[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}$ has rank $\bar{n}$ and it
holds

$\overline{A}\cdot[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}=C.$

If $\overline{m}<\bar{n}$, define $j_{\overline{m}+1},\ldots,j_{\bar{n}}$ to
be arbitrary, but different indices of
$\\{1,\ldots,m\\}\setminus\\{j_{1},\ldots,j_{\overline{m}}\\}$, which is
possible as $\bar{n}\leq n\leq m$. Let the matrix entries of
$[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}$ be

$\displaystyle[B]_{i_{k},j_{k}}$
$\displaystyle=\frac{[C]_{j_{k}}}{[A]_{i_{k}}}\neq 0,\qquad$
$\displaystyle\text{if }k\in\\{1,\ldots,\overline{m}\\},$
$\displaystyle[B]_{i_{k},j_{k}}$
$\displaystyle=A_{i_{1}},\quad[B]_{i_{1},j_{k}}=-A_{i_{k}},\qquad$
$\displaystyle\text{if }k\in\\{\overline{m}+1,\ldots,\bar{n}\\},$

and set all other matrix entries to zero. By construction,
$[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}$ has rank $\bar{n}$ and it
holds

$\overline{A}\cdot[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}=C,$

as for $k\in\\{\overline{m}+1,\ldots,\bar{n}\\}$ it holds
$\overline{A}\cdot[B]_{(i_{1},\ldots,i_{\bar{n}}),(j_{k})}=A_{i_{1}}A_{i_{k}}-A_{i_{1}}A_{i_{k}}=0=[C]_{j_{k}}$.

For both cases, i.e. $\overline{m}\geq\bar{n}$ and $\overline{m}<\bar{n}$,
choose the other rows of $B$, which are not part of
$[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}$ in such a way, that they are
linearly independent of the rows of
$[B]_{(i_{1},\ldots,i_{\bar{n}}),(1,\ldots,m)}$. This is possible, as the
number $n$ of rows of $B$ is smaller than their dimension $m$. Hence, the
constructed matrix $B$ has rank $n$. As $[A]_{i}=0$ for
$i\in\\{1,\ldots,n\\}\setminus\\{i_{1},\ldots,i_{\bar{n}}\\}$ it follows
$AB=C$. ∎

The following proposition shows, that for augmented and bottleneck
architectures in normal form, there exist a choice of the full rank matrices
$W\in\mathbb{W}^{\ast}$, such that the neural network has a critical point.
Hereby the position of the critical point is freely selectable.

######  Theorem 3.21.

Given $L\geq 1$ and $\mathcal{X}\subset\mathbb{R}^{n}$, for every
$x\in\mathcal{X}$ there exist weight matrices $W_{x}\in\mathbb{W}^{\ast}$
corresponding to an augmented architecture
$\Phi\in\Xi^{k}_{\textup{A},\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$ and
weight matrices $W_{x}\in\mathbb{W}^{\ast}$ corresponding to a bottleneck
architecture
$\Phi\in\Xi^{k}_{\textup{B},\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$,
$k\geq 1$, such that $\nabla\Phi(x)=0$, i.e. $\Phi$ has a critical point at
$x\in\mathcal{X}$.

###### Proof.

For $\Phi\in\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})$, the first layer of
maximal width $g_{l^{\ast}}$, $l^{\ast}\in\\{1,\ldots,2L-1\\}$ fulfills
$d_{l^{\ast}-1}<d_{l^{\ast}}$ and it holds $d_{j-1}\geq d_{j}$ for
$l^{\ast}<j\leq 2L$. For
$\Phi\in\Xi^{k}_{\textup{B}}(\mathcal{X},\mathbb{R})$, consider the last
bottleneck of $\Phi$. Then there exist layers $g_{i}^{\ast}$, $g_{j}^{\ast}$
and $g_{l}^{\ast}$ with $0\leq i^{\ast}<j^{\ast}<l^{\ast}\leq 2L$, such that
$d_{i}^{\ast}>d_{j}^{\ast}$, $d_{j}^{\ast}\leq d_{j^{\ast}+1}\leq\ldots\leq
d_{l^{\ast}-1}<d_{l}^{\ast}$ and $d_{j-1}\geq d_{j}$ for $l^{\ast}<j\leq 2L$.
In both cases there exists a layer $g_{l^{\ast}}$ such that
$d_{l^{\ast}-1}<d_{l^{\ast}}$, $d_{l^{\ast}}\geq d_{l^{\ast}+1}$ and from
layer $g_{l^{\ast}}$ on-wards the width of the layers is monotonically
decreasing.

Let
$\Phi\in\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})\cup\Xi^{k}_{\textup{B}}(\mathcal{X},\mathbb{R})$,
fix some $x\in\mathcal{X}$ and denote the weight matrices by
$W=(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})=(V_{1},\ldots,V_{2L})\in\mathbb{W}$,
where $V_{1},\ldots,V_{l^{\ast}},V_{l^{\ast}+2},\ldots,V_{2L}$ are arbitrary
but fixed full rank matrices. As $d_{l^{\ast}-1}<d_{l^{\ast}}$, the
corresponding weight matrix $V_{l^{\ast}}\in\mathbb{R}^{d_{l^{\ast}}\times
d_{l^{\ast}-1}}$ has rank $d_{l^{\ast}-1}$, where
$V_{l^{\ast}}=\widetilde{W}_{l^{\ast}/2}$ if $l^{\ast}$ is even and
$V_{l^{\ast}}=W_{(l^{\ast}+1)/2}$ if $l^{\ast}$ is odd. As
$d_{l^{\ast}}>d_{l^{\ast}-1}$ and $\text{rank}(V_{l^{\ast}})=d_{l^{\ast}-1}$,
the $d_{l^{\ast}}$ rows of $V_{l^{\ast}}$ are linearly dependent. Hence, there
exists a non-trivial linear combination of the rows of $V_{l^{\ast}}$, which
results in a zero row, i.e. there exists $v_{l^{\ast}}\in\mathbb{R}^{1\times
d_{l^{\ast}}}$, $\text{rank}(v_{l^{\ast}})=1$, such that

$v_{l^{\ast}}V_{l^{\ast}}=0\in\mathbb{R}^{1\times d_{l^{\ast}-1}}.$

If $l^{\ast}$ is even, then

$(\nabla\Phi(x))^{\top}=V_{2L}\Psi_{L}(s_{L})V_{2L-1}\ldots\Psi_{l^{\ast}/2+1}(s_{l^{\ast}/2+1})V_{l^{\ast}+1}V_{l^{\ast}}\ldots
V_{2}\Psi_{1}(s_{1})V_{1}\in\mathbb{R}^{1\times n}.$

As $V_{2L}$, $\Psi_{L}(s_{L})$, …, $\Psi_{l^{\ast}/2+1}(s_{l^{\ast}/2+1})$ are
full rank matrices with monotonically increasing width, Lemma 3.10 guarantees
that the matrix product
$V_{2L}\Psi_{L}(s_{L})\ldots\Psi_{l^{\ast}/2+1}(s_{l^{\ast}/2+1})\in\mathbb{R}^{1\times
d_{l^{\ast}+1}}$ has rank one, independently of the choice of
$x\in\mathcal{X}$. Since $d_{l^{\ast}}\geq d_{l^{\ast}+1}$, Lemma 3.20 implies
that there exist a full rank solution
$V_{l^{\ast}+1}\in\mathbb{R}^{d_{l^{\ast}+1}\times d_{l^{\ast}}}$ of the
linear system

$\left[V_{2L}\ldots\Psi_{l^{\ast}/2+1}(s_{l^{\ast}/2+1})\right]V_{l^{\ast}+1}=v_{l^{\ast}}\in\mathbb{R}^{1\times
d_{l^{\ast}}}.$

Hence, there exist weight matrices $W_{x}\in\mathbb{W}^{\ast}$, which depend
on $x$, such that $\nabla\Phi(x)=0\in\mathbb{R}^{n}$ for the fixed
$x\in\mathcal{X}$. If $l^{\ast}$ is odd, then

$(\nabla\Phi(x))^{\top}=V_{2L}\Psi_{L}(s_{L})V_{2L-1}\ldots
V_{l^{\ast}+2}V_{l^{\ast}+1}\Psi_{(l^{\ast}+1)/2}(s_{(l^{\ast}+1)/2})V_{l^{\ast}}\ldots
V_{2}\Psi_{1}(s_{1})V_{1}\in\mathbb{R}^{1\times n}.$

As $V_{2L}$, …, $V_{l^{\ast}+2}$ are full rank matrices with monotonically
increasing width, Lemma 3.10 guarantees that the matrix product
$\widetilde{W}_{L}\ldots V_{l^{\ast}+2}\in\mathbb{R}^{1\times d_{l^{\ast}+1}}$
has rank one, independently of the choice of $x\in\mathcal{X}$. As
$\Psi_{(l^{\ast}+1)/2}(s_{(l^{\ast}+1)/2})$ is a diagonal, invertible full
rank matrix,
$v_{l^{\ast}}\left[\Psi_{(l^{\ast}+1)/2}(s_{(l^{\ast}+1)/2})\right]^{-1}$ has
rank one. Since $d_{l^{\ast}}\geq d_{l^{\ast}+1}$, Lemma 3.20 implies that
there exist a full rank solution
$V_{l^{\ast}+1}\in\mathbb{R}^{d_{l^{\ast}+1}\times d_{l^{\ast}}}$ of the
linear system

$\left[V_{2L}\ldots
V_{l^{\ast}+2}\right]V_{l^{\ast}+1}=v_{l^{\ast}}\left[\Psi_{(l^{\ast}+1)/2}(s_{(l^{\ast}+1)/2})\right]^{-1}\in\mathbb{R}^{1\times
d_{l^{\ast}}}.$

Hence there exist weight matrices $W_{x}\in\mathbb{W}^{\ast}$, which depend on
$x$, such that $\nabla\Phi(x)=0\in\mathbb{R}^{n}$ for the fixed
$x\in\mathcal{X}$. As $\Phi$ was an augmented or a bottleneck neural network,
the result holds for both architectures. ∎

Examples of augmented and bottleneck architectures, which have critical points
are shown in Examples 3.27 and 3.29, when the regularity of the critical
points is analyzed. The last theorem has shown, that for every
$x\in\mathcal{X}$, the weight matrices of augmented neural networks and neural
networks with a bottleneck can be chosen in such a way, that $x\in\mathcal{X}$
is a critical point. From this statement we cannot deduce if it is a generic
property of augmented and bottleneck architectures to have a critical point or
not. In the following we show, that if there exists for a fixed architecture a
non-degenerate critical point, then the set of weights, such that the
corresponding neural network has a non-degenerate critical point, has non-zero
Lebesgue measure in the weight space. Hence, if for one set of weights, a non-
degenerate critical point exist, it is locally a generic property of the
chosen architecture to have at least one non-degenerate critical point.

######  Theorem 3.22.

Let $\Phi\in\Xi^{k}(\mathcal{X},\mathbb{R})$, $k\geq 2$ be a classical feed-
forward neural network with weight matrices $W^{\ast}\in\mathbb{W}$. If $\Phi$
has a non-degenerate critical point $x^{\ast}\in\mathcal{X}$, then there exist
an open neighborhood $\mathcal{V}$ of
$w^{\ast}=\textup{vecm}(W^{\ast})\in\mathbb{R}^{N_{W}}$, which has non-zero
Lebesgue measure in $\mathbb{R}^{N_{W}}$, such that for every
$w\in\mathcal{V}$, the corresponding neural network has at least one critical
point. By choosing $\mathcal{V}$ small enough, it can be guaranteed that at
last one critical point of the corresponding neural network is non-degenerate.

###### Proof.

Let $w^{\ast}=\textup{vecm}(W^{\ast})\in\mathbb{R}^{N_{W}}$ be the vector of
stacked weight matrices of the neural network $\Phi$. Define the function

$F:\mathcal{X}\times\mathbb{R}^{N_{W}}\rightarrow\mathbb{R}^{n},\qquad(x,w)\mapsto
F(x,w)=\nabla\Phi(x)$

with $\mathcal{X}\subset\mathbb{R}^{n}$ open and $\nabla\Phi(x)$ defined in
Lemma 3.17, which also depends on $w\in\mathbb{R}^{N_{W}}$. As $k\geq 2$,
$\Phi$ is a composition of functions, which are at least twice differentiable
in $x$ and $w$, such that $F$ is a continuously differentiable function. By
assumption, the neural network $\Phi$ has a critical point at
$x^{\ast}\in\mathcal{X}$, such that $F(x^{\ast},w^{\ast})=0$. The $n\times n$
matrix

$\frac{\partial F}{\partial x}=\frac{\nabla\Phi(x)}{\partial x}=H_{\Phi}(x)$

is non-singular at the point $(x^{\ast},w^{\ast})$ as by assumption $x^{\ast}$
is a non-degenerate critical point. The Implicit Function Theorem (cf. [6])
now implies that there exist open neighborhoods
$\mathcal{U}\subset\mathcal{X}$ and $\mathcal{V}\subset\mathbb{R}^{N_{W}}$
with $(x^{\ast},w^{\ast})\in\mathcal{U}\times\mathcal{V}$ and a continuously
differentiable function $g:\mathcal{V}\rightarrow\mathcal{U}$ with
$g(w^{\ast})=x^{\ast}$ such that

$F(g(w),w)=0\qquad\text{for all }w\in\mathcal{V}.$

Consequently for every $w\in\mathcal{V}$, the corresponding neural network has
a critical point at $x=g(w)$. As $\mathcal{V}$ is an open set in
$\mathbb{R}^{N_{W}}$ it has non-zero Lebesgue measure. As the determinant of
the matrix $\frac{\partial F}{\partial x}=H_{\Phi}(x)$ is a continuous
function in $w$, the neighborhood $\mathcal{V}$ can be chosen small enough,
such that the critical point $x=g(w)$ is for every $w\in\mathcal{V}$ non-
degenerate. ∎

###  3.4 Regularity of Critical Points

To prove the main results of this section, we use the following lemma of
differential geometry, characterizing Morse function not via their Hessian,
but via the mixed second derivatives with respect to the weights and the input
data.

######  Lemma 3.23 ([20]).

Let $\widehat{\Lambda}\in C^{2}(\mathcal{X}\times\mathcal{V},\mathbb{R})$,
$\mathcal{X}\subset\mathbb{R}^{n}$, $\mathcal{V}\subset\mathbb{R}^{p}$ with
$n\leq p$ and denote by $\Lambda_{v}\in C^{2}(\mathcal{X},\mathbb{R})$ the
family of functions $\Lambda_{v}(x)\coloneqq\widehat{\Lambda}(x,v)$, which
depend continuously on the parameter $v\in\mathcal{V}$. If

$\frac{\partial^{2}\widehat{\Lambda}}{\partial v\partial
x}(x,v)\in\mathbb{R}^{n\times
p},\quad\left[\frac{\partial^{2}\widehat{\Lambda}}{\partial v\partial
x}(x,v)\right]_{ij}=\frac{\partial^{2}\widehat{\Lambda}}{\partial
v_{j}\partial x_{i}}(x,v),\quad i\in\\{1,\ldots,n\\},\;j\in\\{1,\ldots,p\\},$

is for every $(x,v)\in\mathcal{X}\times\mathcal{V}$ surjective, i.e. the
matrix $\frac{\partial^{2}\widehat{\Lambda}}{\partial v\partial x}(x,v)$ has
for every $(x,v)\in\mathcal{X}\times\mathcal{V}$ full rank $n$, then there
exists a set $\mathcal{V}_{0}\subset\mathcal{V}$ of Lebesgue measure zero in
$\mathbb{R}^{p}$, such that the function $\Lambda_{v}$ is for all weights
$v\in\mathcal{V}\setminus\mathcal{V}_{0}$ a Morse function.

######  Example 3.24.

Let $\widehat{\Lambda}\in C^{2}(\mathbb{R}\times\mathbb{R}^{2},\mathbb{R})$ be
defined by $\widehat{\Lambda}(x,v_{1},v_{2})=v_{1}x^{2}+v_{2}x$. As the matrix

$\frac{\partial^{2}\widehat{\Lambda}}{\partial v\partial
x}(x,v)=\left(2x,1\right)$

has for all $(x,v)\in\mathbb{R}\times\mathbb{R}^{2}$ rank one, Lemma 3.23
implies that $\Lambda_{v}(x)=v_{1}x^{2}+v_{2}x$ is for all
$v\in\mathbb{R}^{2}$, except possibly for a set
$\mathcal{V}_{0}\subset\mathbb{R}$ of Lebesgue measure zero, a Morse function.
In this example $\mathcal{V}_{0}=(0,0)$ as for $v_{1}\neq 0$ it holds for the
Hessian $H_{\Lambda_{v}}(x)=2v_{1}\neq 0$, such that every possible critical
point is non-degenerate. For $v_{1}=0$ and $v_{2}\neq 0$, the map
$\Lambda_{v}$ has no critical point and hence is a Morse function, only for
$v_{1}=v_{2}=0$ the map $\Lambda_{v}$ has degenerate critical points and is no
Morse function.

The idea to apply Theorem 3.23 to feed-forward neural networks was already
used b¡ Kurochkin in [16]. In this work, we rigorously proof an analogous
result to the main theorem of [16] for our more general setting.

######  Theorem 3.25.

Any augmented classical feed-forward neural network
$\Phi\in\Xi^{k}_{\textup{A}}(\mathcal{X},\mathbb{R})$, $k\geq 2$, with weight
matrices $W\in\mathbb{W}^{\ast}$ and biases $b\in\mathbb{B}$, is for all
weights $(\textup{vecm}(W);\textup{stk}(B))\in\mathbb{R}^{N_{W}+N_{B}}$,
except possibly for a zero set in $\mathbb{R}^{N_{W}+N_{B}}$ w.r.t. the
Lebesgue measure, of class $(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$ or
$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$ and hence a Morse function. The
same statement holds if $\mathbb{W}^{\ast}$ is replaced by $\mathbb{W}$.

###### Proof.

Let $\Phi\in\Xi^{k}_{\textup{A},\mathbb{W}^{\ast}}(\mathcal{X},\mathbb{R})$,
$k\geq 2$ be an augmented classical feed-forward neural network with weight
matrices
$(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})\in\mathbb{W}^{\ast}$.
By Theorem 3.21 it is possible that the neural network $\Phi$ has a critical
point. In the case that $\Phi$ has no critical point, $\Phi$ is of class
$(\mathcal{C}1)^{k}(\mathcal{X},\mathbb{R})$ and hence a Morse function. In
the following we show that if $\Phi$ has a critical point, then it is for all
weights, where $\Phi$ has critical points, except possibly for a zero set
w.r.t. the Lebesgue measure, of class
$(\mathcal{C}2)^{k}(\mathcal{X},\mathbb{R})$. To show this statement, we
consider feed-forward neural networks with full rank weight matrices
$W=(W_{1},\widetilde{W}_{1},\ldots,W_{L},\widetilde{W}_{L})\in\mathbb{W}^{\ast}$.
By Lemma 3.17, the gradient of $\Phi$ is given by

$\nabla\Phi(x)=\left[\widetilde{W}_{L}\Psi_{L}(s_{L})W_{L}\ldots\widetilde{W}_{1}\Psi_{1}(s_{1})W_{1}\right]^{\top}\in\mathbb{R}^{n},$

where
$\Psi_{l}(s_{l})=\textup{diag}([\sigma_{l}]_{i}^{\prime}([s_{l}]_{i}))\in\mathbb{R}^{n_{l}\times
n_{l}}$, $i\in\\{1,\ldots,n_{l}\\}$, is a diagonal matrix with
$s_{l}=W_{l}h_{l-1}+b_{l}$, $W\in\mathbb{W}^{\ast}$ and $b\in\mathbb{B}$. Let
$v=(\textup{vecm}(W);\textup{stk}(b))\in\mathbb{R}^{p}$ with $p=N_{W}+N_{B}$
be the vector with all stacked weight matrices and biases and define
$\widehat{\Phi}\in
C^{k}(\mathcal{X}\times\left(\textup{vecm}(\mathbb{W}^{\ast})\times\textup{stk}(\mathbb{B})\right))$,
$k\geq 2$ to be the neural network $\Phi$ with an explicit dependence on the
weight vector
$v\in\textup{vecm}(\mathbb{W}^{\ast})\times\textup{stk}(\mathbb{B})$. As a
composition of $k$ times continuously differentiable functions
$\widehat{\Phi}$ is not only in $x$ but also in $v$ $k$ times continuously
differentiable. The second partial derivatives
$\frac{\partial^{2}\widehat{\Phi}}{\partial v\partial x}\in\mathbb{R}^{n\times
p}$ of $\widehat{\Phi}$ w.r.t. $x$ and $v$ can be explicitly calculated. First
we calculate the derivatives w.r.t. the components of the biases
$[b_{l}]_{i}$, $l\in\\{1,\ldots,L\\}$, $i\in\\{1,\ldots,m_{l}\\}$. They are
given by

$\displaystyle\frac{\partial^{2}\widehat{\Phi}}{\partial[b_{l}]_{i}\partial
x}=\;$
$\displaystyle\frac{\partial}{\partial[b_{l}]_{i}}\left[W_{1}^{\top}\Psi_{1}(s_{1})\widetilde{W}_{1}^{\top}\ldots
W_{L}^{\top}\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}\right]$ $\displaystyle=\;$
$\displaystyle\sum_{k=l}^{L}W_{1}^{\top}\Psi_{1}(s_{1})\ldots
W_{k}^{\top}\Psi_{k}^{\prime}(s_{k})\textup{ diag}\left(\left[\frac{\partial
s_{k}}{\partial[b_{l}]_{i}}\right]\right)\widetilde{W}_{k}^{\top}W_{k+1}^{\top}\ldots\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}$
$\displaystyle=\;$
$\displaystyle\sum_{k=l}^{L}W_{1}^{\top}\ldots\Psi_{k}^{\prime}(s_{k})\textup{
diag}\left(\left[W_{k}\widetilde{W}_{k-1}\Psi_{k-1}(s_{k-1})\ldots\Psi_{l}(s_{l})\mathrm{e}_{i}^{(m_{l})}\right]\right)\widetilde{W}_{k}^{\top}\ldots\widetilde{W}_{L}^{\top},$

where
$\Psi_{k}^{\prime}(s_{k})=\textup{diag}([\sigma_{k}]_{i}^{\prime\prime}([s_{k}]_{i}))\in\mathbb{R}^{m_{k}\times
m_{k}}$, $i\in\\{1,\ldots,m_{k}\\}$ and $\frac{\partial
s_{k}}{\partial[b_{l}]_{i}}\in\mathbb{R}^{m_{k}}$, $k\in\\{l,\ldots,L\\}$. The
operator diag applied to a vector $y\in\mathbb{R}^{m_{k}}$ defines a diagonal
matrix in $\mathbb{R}^{m_{k}\times m_{k}}$ with the entries $y$ component-wise
on its diagonal. The vector $\mathrm{e}_{i}^{(m_{l})}$ denotes the $i$-th unit
vector in $\mathbb{R}^{m_{l}}$. In the calculation the product rule and the
multidimensional chain rule was used. Analogously it follows for the biases
$[\tilde{b}_{l}]_{i}$, $l\in\\{1,\ldots,L-1\\}$, $i\in\\{1,\ldots,n_{l}\\}$
that

$\displaystyle\frac{\partial^{2}\widehat{\Phi}}{\partial[\tilde{b}_{l}]_{i}\partial
x}=\;$
$\displaystyle\frac{\partial}{\partial[\tilde{b}_{l}]_{i}}\left[W_{1}^{\top}\Psi_{1}(s_{1})\widetilde{W}_{1}^{\top}\ldots
W_{L}^{\top}\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}\right]$ $\displaystyle=\;$
$\displaystyle\sum_{k=l+1}^{L}W_{1}^{\top}\Psi_{1}(s_{1})\ldots
W_{k}^{\top}\Psi_{k}^{\prime}(s_{k})\textup{ diag}\left(\left[\frac{\partial
s_{k}}{\partial[\tilde{b}_{l}]_{i}}\right]\right)\widetilde{W}_{k}^{\top}W_{k+1}^{\top}\ldots\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}$
$\displaystyle=\;$
$\displaystyle\sum_{k=l+1}^{L}W_{1}^{\top}\ldots\Psi_{k}^{\prime}(s_{k})\textup{
diag}\left(\left[W_{k}\widetilde{W}_{k-1}\Psi_{k-1}(s_{k-1})\ldots
W_{l+1}\mathrm{e}_{i}^{(n_{l})}\right]\right)\widetilde{W}_{k}^{\top}\ldots\widetilde{W}_{L}^{\top}$

and

$\frac{\partial^{2}\widehat{\Phi}}{\partial\tilde{b}_{L}\partial
x}=\frac{\partial}{\partial\tilde{b}_{L}}\left[W_{1}^{\top}\Psi_{1}(s_{1})\widetilde{W}_{1}^{\top}\ldots
W_{L}^{\top}\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}\right]=0$

where $\tilde{b}_{L}\in\mathbb{R}$.

The derivatives w.r.t. the matrix entries $[W_{l}]_{ij}$,
$l\in\\{1,\ldots,L\\}$, $i\in\\{1,\ldots,m_{l}\\}$,
$j\in\\{1,\ldots,n_{l-1}\\}$ are given by

$\displaystyle\frac{\partial^{2}\widehat{\Phi}}{\partial[W_{l}]_{ij}\partial
x}=\;$
$\displaystyle\frac{\partial}{\partial[W_{l}]_{ij}}\left[W_{1}^{\top}\Psi_{1}(s_{1})\widetilde{W}_{1}^{\top}\ldots
W_{L}^{\top}\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}\right]$ $\displaystyle=\;$
$\displaystyle\sum_{k=l}^{L}W_{1}^{\top}\Psi_{1}(s_{1})\ldots
W_{k}^{\top}\Psi_{k}^{\prime}(s_{k})\textup{ diag}\left(\left[\frac{\partial
s_{k}}{\partial[W_{l}]_{ij}}\right]\right)\widetilde{W}_{k}^{\top}W_{k+1}^{\top}\ldots\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}$
$\displaystyle+W_{1}^{\top}\Psi_{1}(s_{1})\ldots\Psi_{l-1}(s_{l-1})\widetilde{W}_{l-1}^{\top}\delta_{ij}^{n_{l-1}\times
m_{l}}\Psi_{l}(s_{l})\ldots\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}$
$\displaystyle=\;$
$\displaystyle\sum_{k=l}^{L}W_{1}^{\top}\ldots\Psi_{k}^{\prime}(s_{k})\textup{
diag}\left(\left[W_{k}\widetilde{W}_{k-1}\Psi_{k-1}(s_{k-1})\ldots\Psi_{l}(s_{l})\mathrm{e}_{i}^{(m_{l})}[h_{l}]_{j}\right]\right)\widetilde{W}_{k}^{\top}\ldots\widetilde{W}_{L}^{\top}$
$\displaystyle+W_{1}^{\top}\Psi_{1}(s_{1})\ldots\Psi_{l-1}(s_{l-1})\widetilde{W}_{l-1}^{\top}\delta_{ij}^{n_{l-1}\times
m_{l}}\Psi_{l}(s_{l})\ldots\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}$

where $\delta_{ij}^{n_{l-1}\times m_{l}}$ denotes the matrix in
$\mathbb{R}^{n_{l-1}\times m_{l}}$, which has everywhere zeros, only at the
$i,j$-th entry the number one. Analogously it follows for the weight matrices
$[\widetilde{W}_{l}]_{ij}$, $l\in\\{1,\ldots,L-1\\}$,
$i\in\\{1,\ldots,n_{l}\\}$, $j\in\\{1,\ldots,m_{l}\\}$ that

$\displaystyle\frac{\partial^{2}\widehat{\Phi}}{\partial[\widetilde{W}_{l}]_{ij}\partial
x}=\;$
$\displaystyle\frac{\partial}{\partial[\widetilde{W}_{l}]_{ij}}\left[W_{1}^{\top}\Psi_{1}(s_{1})\widetilde{W}_{1}^{\top}\ldots
W_{L}^{\top}\Psi_{L}(s_{L})\widetilde{W}_{L}^{\top}\right]$ $\displaystyle=\;$
$\displaystyle\sum_{k=l+1}^{L}W_{1}^{\top}\Psi_{1}(s_{1})\ldots
W_{k}^{\top}\Psi_{k}^{\prime}(s_{k})\textup{ diag}\left(\left[\frac{\partial