headers [0][Authors][]Quadratic neural networks0  propositionlemma proposition
corollarylemma corollary theoremlemma theorem definitionlemma definition
examplelemma example assumptionlemma assumption notationlemma notation

# Quadratic neural networks for solving inverse problems

Leon Frischauf1
<EMAIL_ADDRESS>Otmar Scherzer1,2,3
<EMAIL_ADDRESS>Cong Shi1,2,∗
<EMAIL_ADDRESS>
###### Abstract

In this paper we investigate the solution of inverse problems with neural
network ansatz functions with generalized decision functions. The relevant
observation for this work is that such functions can approximate typical test
cases, such as the Shepp-Logan phantom, better, than standard neural networks.
Moreover, we show that the convergence analysis of numerical methods for
solving inverse problems with shallow generalized neural network functions
leads to more intuitive convergence conditions, than for deep affine linear
neural networks.

1Faculty of Mathematics
University of Vienna
Oskar-Morgenstern-Platz 1
A-1090 Vienna, Austria

2Johann Radon Institute for
Computational and Applied
Mathematics (RICAM)
Altenbergerstraße 69
A-4040 Linz, Austria

3Christian Doppler Laboratory for Mathematical Modeling and
Simulation of Next Generations of Ultrasound Devices (MaMSi)
Oskar-Morgenstern-Platz 1
A-1090 Vienna, Austria

††∗Cong Shi is the corresponding author.

Keywords: Inverse problems; generalized neural network functions.
MSC: 65J22; 45Q05; 42C40; 65F20

## 1\. Introduction

We consider an _inverse problem_ , which consists in solving an operator
equation

$F({\bf x})={\bf y}_{0},$ (1.1)

where $F:{\bf X}\rightarrow{\bf Y}$ denotes an operator, mapping between
function spaces $({\bf X},\left\|\cdot\right\|)$ and $({\bf
Y},\left\|\cdot\right\|)$. For the numerical solution of Equation 1.1 an
appropriate set of ansatz-functions ${\bf P}$ has to be selected, on which an
approximate solution of Equation 1.1 is calculated, for instance a function
${\bf p}\in{\bf P}\subseteq{\bf X}$, which solves

$F({\bf p})={\bf y},$ (1.2)

where ${\bf y}$ is an approximation of ${\bf y}_{0}$. The history on the topic
of approximating the solution of Equation 1.1 by discretization and
regularization is long: For linear inverse problems this has been investigated
for instance in [23]. Much later on neural network ansatz functions have been
used for solving Equation 1.1; see for instance [24]. In this paper we
investigate solving Equation 1.2 when ${\bf P}$ is a set of neural network
functions with _generalized_ decision functions. In order to spot the
difference to classical neural network functions we recall the definition of
them first:

######  Definition  (Affine linear neural network functions).

Let $m\geq n\in\mathbb{N}$. Line vectors in $\mathbb{R}^{m}$ and
$\mathbb{R}^{n}$ are denoted by

${\bf w}=(w^{(1)},w^{(2)},\ldots,w^{(m)})^{T}\text{ and
}{\vec{x}}=(x_{1},x_{2},\ldots,x_{n})^{T},\text{ respectively.}$

  * •

A _shallow_ affine linear neural networks (ALNN) is a function (here $m=n$)

${\vec{x}}\in\mathbb{R}^{n}\to{\bf
p}({\vec{x}}):=\Psi[{\vec{p}}]({\vec{x}}):=\sum_{j=1}^{N}\alpha_{j}\sigma\left({\bf
w}_{j}^{T}{\vec{x}}+\theta_{j}\right),$ (1.3)

with $\alpha_{j},\theta_{j}\in\mathbb{R}$, ${\bf w}_{j}\in\mathbb{R}^{n}$;
$\sigma$ is an activation function, such as the sigmoid, ReLUk or Softmax
function. Moreover,

${\vec{p}}=[\alpha_{1},\ldots,\alpha_{N};{\bf w}_{1},\ldots,{\bf
w}_{N};\theta_{1},\ldots,\theta_{N}]\in\mathbb{R}^{n_{*}}\text{ with
}n_{*}=(n+2)N$ (1.4)

denotes the according parametrization of ${\bf p}$. In this context the set of
ALNNs is given by

${\bf P}:=\left\\{{\bf p}\text{ of the form
\autoref{eq:classical_approximation}}:{\vec{p}}\in\mathbb{R}^{n_{*}}\right\\}.$

  * •

More recently _deep_ affine linear neural network functions (DNNs) have become
popular: An $(L+2)$-layer network looks as follows:

$\displaystyle{\vec{x}}\in\mathbb{R}^{n}\to$ $\displaystyle{\bf
p}({\vec{x}}):=$ (1.5)
$\displaystyle\Psi[{\vec{p}}]({\vec{x}}):=\sum_{j_{L}=1}^{N_{L}}\alpha_{j_{L},L}\sigma_{L}\left(p_{j_{L},L}\left(\sum_{j_{L-1}=1}^{N_{L-1}}\ldots\left(\sum_{j_{1}=1}^{N}\alpha_{j_{1},1}\sigma_{1}\left(p_{j_{1},1}({\vec{x}})\right)\right)\right)\right).$

where

$p_{j,l}({\vec{x}})={\bf w}_{j,l}^{T}{\vec{x}}+\theta_{j,l}\text{ with
}\alpha_{j,l},\theta_{j,l}\in\mathbb{R}\text{ and }{\bf
w}_{j,l}\in\mathbb{R}^{n}\text{ for all }l=1,\ldots,L.$

Here $s\in\mathbb{R}\to\sigma_{k}(s)$, $k=1,\ldots,L$, denote activation
functions. Moreover, we denote the parametrizing vector by

${\vec{p}}=[\alpha_{1,1},\ldots,\alpha_{N_{L},L};{\bf w}_{1,1},\ldots,{\bf
w}_{N_{L},L};\theta_{1,1},\ldots,\theta_{N_{L},L}]\in\mathbb{R}^{n_{*}}.$
(1.6)

A shallow linear neural network can also be called a _3-layer network_. The
notation 3-layer network is consistent with the literature because input-and
output are counted on top. Therefore, a general $(L+2)$-layer network has only
$L$ _internal_ layers.

We demonstrate exemplary below (see Section 3.2) that the convergence analysis
of an iterative Gauss-Newton method for solving a linear inverse problem
restricted to a set of deep neural network ansatz functions is involved (see
Section 3.2), while the analysis with shallow neural networks ansatz functions
leads to intuitive conditions (see also [28]). Moreover, it is well-known in
regularization theory that the quality of approximation of the solution of
Equation 1.2 is depending on the approximation qualities of the set ${\bf P}$:
Approximation of functions with shallow affine linear neural networks is a
classical topic of machine learning and in approximation theory, see for
instance [26, 1, 5, 14, 18, 21, 32, 31]. The central result concerns the
_universal approximation property_. Later on the universal approximation
property has been established for different classes of neural networks:
Examples are dropout neural networks (see [34, 20]), convolutional neural
networks (CNN) (see for example [36, 37]), recurrent neural networks (RNN)
(see [27, 13]), networks with random nodes (see [35]), with random weights and
biases (see [25, 15]) and with fixed neural network topology (see [11]), to
name but a few.

In this paper we follow up on this topic and analyze neural network functions
with decision functions, which are higher order polynomials, as specified now:

######  Definition  (Shallow generalized neural network function).

Let $n,m,N\in\mathbb{N}$. Moreover, let

${\bf{f}}_{j}:\mathbb{R}^{n}\to\mathbb{R}^{m},\quad j=1,\ldots,N$

be vector-valued functions. Neural network functions associated to
$\left\\{{\bf{f}}_{j}:j=1,\ldots,N\right\\}$ are defined by

${\vec{x}}\to{\bf
p}({\vec{x}})=\Psi[{\vec{p}}]({\vec{x}}):=\sum_{j=1}^{N}\alpha_{j}\sigma\left({\bf
w}_{j}^{T}{\bf{f}}_{j}({\vec{x}})+\theta_{j}\right)\text{ with
}\alpha_{j},\theta_{j}\in\mathbb{R}\text{ and }{\bf w}_{j}\in\mathbb{R}^{m}.$
(1.7)

Again we denote the parametrization vector, containing all coefficients, with
${\vec{p}}$ and the set of all such functions with ${\bf P}$. We call

$\mathcal{D}:=\left\\{{\vec{x}}\to{\bf
w}^{T}{\bf{f}}_{j}({\vec{x}})+\theta:{\bf
w}\in\mathbb{R}^{m},\theta\in\mathbb{R},j=1,\ldots,N\right\\}$ (1.8)

the set of _decision functions_ associated to Equation 1.7. The composition of
$\sigma$ with a decision function is called _neuron_.

We discuss approximation properties of generalized neural networks (see
Section 2), in particular neural network functions with decision functions,
which are at most _quadratic polynomials_ in ${\vec{x}}$. This idea is not
completely new: In [33] neural networks with _parabolic_ decision functions
have been applied in a number of applications. In [10], the authors proposed
neural networks with radial decision functions, and proved an universal
approximation result for ReLU-activated _deep quadratic networks_.

### Outline of this paper

The motivation for this paper is to solve Equation 1.2 on a set of neural
network functions ${\bf P}$ with iterative algorithms, such as for instance a
Gauss-Newton method. Good approximation properties of functions of interest
(such as the Shepp-Logan phantom) is provided with quadratic _decision
functions_ , which have been suggested already in [21]. We concentrate on
shallow neural networks because the resulting analysis of iterative methods
for solving inverse problems is intuitive (see Section 3.2). We apply
different approximation theorems (such as for instance the universal
approximation theorem of [5]) to cover all situations from Section 2, below.
Moreover, by constructing wavelet frames based on quadratic decision
functions, we give an explicit convergence rate for shallow radial network
approximations; see Section 4, with main result Section 4. In Appendix A the
important conditions of the _approximation to the identity_ (AtI) from [7]
used for proving the convergence rates in Section 4 are verified.

## 2\. Examples of networks with generalized decision functions

The versatility of the network defined in Equation 1.7 is due to the
flexibility of the functions ${\bf{f}}_{j}$, $j=1,\ldots,N$ to chose.

We give a few examples.

######  Definition  (Neural networks with generalized decision functions).

We split them into three categories:

General quadratic neural networks (GQNN): Let

$m=n+1,\quad{\bf{f}}_{j}({\vec{x}})=\begin{pmatrix}f_{j}^{(1)}({\vec{x}})\\\
\vdots\\\ f_{j}^{(n)}({\vec{x}})\\\
f_{j}^{(n+1)}({\vec{x}})\end{pmatrix}=\begin{pmatrix}x_{1}\\\ \vdots\\\
x_{n}\\\ {\vec{x}}^{T}A_{j}{\vec{x}}\end{pmatrix}\text{ for all
}j=1,\ldots,N.$

That is, ${\bf{f}}_{j}$ is a graph of a quadratic function. Then Equation 1.7
reads as follows:

$\displaystyle{\vec{x}}\to{\bf p}({\vec{x}})=\Psi[{\vec{p}}]({\vec{x}})$
$\displaystyle:=\sum_{j=1}^{N}\alpha_{j}\sigma\left({\bf
w}_{j}^{T}{\vec{x}}+{\vec{x}}^{T}A_{j}{\vec{x}}+\theta_{j}\right)$ (2.1)
$\displaystyle\text{ with }\alpha_{j},\theta_{j}\in\mathbb{R},{\bf
w}_{j}\in\mathbb{R}^{n},A_{j}\in\mathbb{R}^{n\times n}.$

${\vec{p}}$ denotes the parametrization of ${\bf p}$:

$\displaystyle{\vec{p}}=[\alpha_{1}\ldots,\alpha_{N};{\bf w}_{1},\ldots,{\bf
w}_{N};A_{1},\ldots,A_{N};\theta_{1},\ldots,\theta_{N}]\in\mathbb{R}^{n_{*}}\text{
with }n_{*}=(n^{2}+n+2)N.$ (2.2)

Note that in Equation 2.1 all parameters of the entries of the matrices
$A_{j}$ are parameters.

Constrained quadratic neural networks (CQNN): These are networks, where the
entries of the matrices $A_{j}$, $j=1,\ldots,N$ are constrained:

  1. (i)

Let

${\bf{f}}({\vec{x}})={\bf{f}}_{j}({\vec{x}})=\begin{pmatrix}f_{j}^{(1)}({\vec{x}})\\\
\vdots\\\ f_{j}^{(n)}({\vec{x}})\\\
f_{j}^{(n+1)}({\vec{x}})\end{pmatrix}=\begin{pmatrix}x_{1}\\\ \vdots\\\
x_{n}\\\ 0\end{pmatrix}\text{ for all }j=1,\ldots,N.$

That is $A_{j}=0$ for all $j=1,\ldots,N$. This set of CQNNs corresponds with
the ALNNs defined in Equation 1.3.

  2. (ii)

Let $A_{j}\in\mathbb{R}^{n\times n}$, $j=1,\ldots,N$ be chosen and fixed. We
denote by MCNN the family of functions

$\displaystyle{\vec{x}}\to{\bf p}({\vec{x}})=\Psi[{\vec{p}}]({\vec{x}})$
$\displaystyle:=\sum_{j=1}^{N}\alpha_{j}\sigma\left({\bf
w}_{j}^{T}{\vec{x}}+\xi_{j}{\vec{x}}^{T}A_{j}{\vec{x}}+\theta_{j}\right)$
(2.3) $\displaystyle\text{ with
}\alpha_{j},\theta_{j},\xi_{j}\in\mathbb{R},{\bf
w}_{j}\in\mathbb{R}^{n},A_{j}\in\mathbb{R}^{n\times n},$

which is parametrized by the vector

$\displaystyle{\vec{p}}=[\alpha_{1}\ldots,\alpha_{N};{\bf w}_{1},\ldots,{\bf
w}_{N};\xi_{1},\ldots,\xi_{N};\theta_{1},\ldots,\theta_{N}]\in\mathbb{R}^{n_{*}}\text{
with }n_{*}=(n+3)N.$ (2.4)

In particular, choosing $A_{j}=\mathcal{I}$ we get:

$\displaystyle{\vec{x}}\to{\bf p}({\vec{x}})=\Psi[{\vec{p}}]({\vec{x}})$
$\displaystyle:=\sum_{j=1}^{N}\alpha_{j}\sigma\left({\bf
w}_{j}^{T}{\vec{x}}+\xi_{j}\left\|{\vec{x}}\right\|^{2}+\theta_{j}\right)$
(2.5) $\displaystyle\text{ with }\alpha_{j},\theta_{j}\in\mathbb{R},{\bf
w}_{j}\in\mathbb{R}^{n},\xi_{j}\in\mathbb{R}.$

Radial quadratic neural networks (RQNN)s: For $\xi_{j}\neq 0$ the argument in
Equation 2.5 rewrites to

$\displaystyle\nu_{j}({\vec{x}}):=\xi_{j}\left\|{\vec{x}}\right\|^{2}+\hat{{\bf
w}}_{j}^{T}{\vec{x}}+\theta_{j}=\xi_{j}\left\|{\vec{x}}-{\vec{y}}\right\|^{2}+\kappa_{j}$
(2.6)

with

${\vec{y}}_{j}=-\frac{1}{2\xi_{j}}\hat{{\bf w}}_{j}^{T}\text{ and
}\kappa_{j}=\theta_{j}-\frac{\left\|\hat{{\bf w}}_{j}\right\|^{2}}{4\xi_{j}}.$
(2.7)

We call the set of functions from Equation 2.5, which satisfy

$\xi_{j}\geq 0\text{ and }\kappa_{j}\leq 0\text{ for all }j=1,\ldots,N,$ (2.8)

RQNNs, radial neural network functions, because the level sets of $\nu_{j}$
are circles. These are _radial basis functions_ (see for instance [3] for a
general overview).

Sign based quadratic (SBQNN) and cubic neural networks (CUNN): Let $m=n$.

  1. (i)

(SBQNN): Let

$f^{(i)}({\vec{x}})=\text{sgn}(x_{i})x_{i}^{2}\text{ for }i=1,\ldots,n,$ (2.9)

or alternatively

$f^{(i)}({\vec{x}})=\left\|{\vec{x}}\right\|^{2}\text{sgn}(x_{i})\text{ for
}i=1,\ldots,n.$

In the first case, and in the second case similarly, we obtain the family of
functions

$\Psi[{\vec{p}}]({\vec{x}}):=\sum_{j=1}^{N}\alpha_{j}\sigma\left(\sum_{i=1}^{n}w_{j}^{(i)}\text{sgn}(x_{i})x_{i}^{2}+\theta_{j}\right)\text{
with }\alpha_{j},\theta_{j}\in\mathbb{R}\text{ and }{\bf
w}_{j}\in\mathbb{R}^{n}.$ (2.10)

We call these functions _signed squared neural networks_. Note, here
${\vec{p}}\in\mathbb{R}^{n_{*}}$ with $n_{*}=(n+2)N$.

  2. (ii)

(CUNN): Let

$f^{(i)}({\vec{x}})=x_{i}^{3}\text{ for }i=1,\ldots,n.$ (2.11)

We obtain the family of functions

$\Psi[{\vec{p}}]({\vec{x}}):=\sum_{j=1}^{N}\alpha_{j}\sigma\left(\sum_{i=1}^{n}w_{j}^{(i)}x_{i}^{3}+\theta_{j}\right)\text{
with }\alpha_{j},\theta_{j}\in\mathbb{R}\text{ and }{\bf
w}_{j}\in\mathbb{R}^{n}.$ (2.12)

We call these functions _cubic neural networks_. Again
${\vec{p}}\in\mathbb{R}^{n_{*}}$ with $n_{*}=(n+2)N$.

######  Remark 1.

  1. (i)

It is obvious that generalized quadratic neural network functions and matrix
constrained neural networks are more versatile than affine linear works, and
thus they satisfy the universal approximation property (see [5]).

  2. (ii)

The constraint Equation 2.8 does not allow to use the universal approximation
theorem in a straight forward manner. In fact we prove an approximation result
indirectly via a convergence rates result (see Section 4).

  3. (iii)

Sign based quadratic and cubic neural networks satisfy the universal
approximation property, which is proven below in Section 2 by reducing it to
the classical result from [5].

In order to prove the universal approximation property of SBQNNs and CUNNs we
review the _universal approximation theorem_ as formulated by [5] first. It is
based discriminatory properties of the functions $\sigma$.

######  Definition  (Discriminatory function).

A function $\sigma:\mathbb{R}\to\mathbb{R}$ is called _discriminatory_ (see
[5]) if every measure $\mu$ on $[0,1]^{n}$, which satisfies

$\int_{[0,1]^{n}}\sigma({\bf
w}^{T}{\vec{x}}+\theta)\,d\mu({\vec{x}})=0\quad\text{ for all }{\bf
w}\in\mathbb{R}^{n}\text{ and }\theta\in\mathbb{R}$

implies that $\mu\equiv 0$.

######  Example .

Note that every non-polynomial function is _discriminatory_ (this follows from
the results in [18]). Therefore the choices of activation function in Section
1 are discriminatory for the Lebesgue-measure.

With these basic concepts we are able to recall Cybenko’s universal
approximation result.

######  Theorem  ([5]).

Let $\sigma:\mathbb{R}\to\mathbb{R}$ be a continuous discriminatory function.
Then, for every function $g\in C([0,1]^{n})$ and every $\epsilon>0$, there
exists a function

$G_{\epsilon}({\vec{x}})=\sum_{j=1}^{N}\alpha_{j}\sigma({\bf
w}_{j}^{T}{\vec{x}}+\theta_{j})\qquad\text{ with
}N\in\mathbb{N},\alpha_{j},\theta_{j}\in\mathbb{R},{\bf
w}_{j}\in\mathbb{R}^{n},$ (2.13)

satisfying

$|G_{\epsilon}({\vec{x}})-g({\vec{x}})|<\epsilon\text{ for all
}{\vec{x}}\in[0,1]^{n}.$

In the following we formulate and prove a modification of Cybenko’s universal
approximation result [5] for shallow _generalized_ neural networks as
introduced in Section 1.

######  Theorem  (Generalized universal approximation theorem).

Let $\sigma:\mathbb{R}\to\mathbb{R}$ be a continuous discriminatory function
and assume that ${\bf{f}}_{j}:[0,1]^{n}\to\mathbb{R}^{m}$, $j=1,\ldots,N$ are
injective (this in particular means that $n\leq m$) and continuous,
respectively. We denote ${\bf{f}}=({\bf{f}}_{1},\ldots,{\bf{f}}_{N})$.

Then for every $g\in C([0,1]^{n})$ and every $\epsilon>0$ there exists some
function

$\Psi^{\bf{f}}({\vec{x}}):=\sum_{j=1}^{N}\alpha_{j}\sigma\left({\bf
w}_{j}^{T}{\bf{f}}_{j}({\vec{x}})+\theta_{j}\right)\text{ with
}\alpha_{j},\theta_{j}\in\mathbb{R}\text{ and }{\bf w}_{j}\in\mathbb{R}^{m}$

satisfying

$\left|\Psi^{\bf{f}}({\vec{x}})-g({\vec{x}})\right|<\epsilon\text{ for all
}{\vec{x}}\in[0,1]^{n}.$

######  Proof.

We begin the proof by noting that since ${\vec{x}}\to{\bf{f}}_{j}({\vec{x}})$
is injective, the inverse function on the range of ${\bf{f}}_{j}$ is well-
defined, and we write
${\bf{f}}_{j}^{-1}:{\bf{f}}_{j}([0,1]^{n})\subseteq\mathbb{R}^{m}\to[0,1]^{n}\subseteq\mathbb{R}^{n}$.
The proof that ${\bf{f}}_{j}^{-1}$ is continuous relies on the fact that the
domain $[0,1]^{n}$ of ${\bf{f}}_{j}$ is compact, see for instance [9, Chapter
XI, Theorem 2.1]. Then applying the Tietze–Urysohn–Brouwer extension theorem
(see [16]) to the continuous function
$g\circ{\bf{f}}_{j}^{-1}:{\bf{f}}_{j}([0,1]^{n})\to\mathbb{R}$, we see that
this function can be extended continuously to $\mathbb{R}^{m}$. This extension
will be denoted by $g^{*}:\mathbb{R}^{m}\to\mathbb{R}$.

We apply Section 2 to conclude that there exist
$\alpha_{j},\theta_{j}\in\mathbb{R}$ and ${\bf w}_{j}\in\mathbb{R}^{m}$,
$j=1,\ldots,N$ such that

$\Psi^{*}({\bf{z}}):=\sum_{j=1}^{N}\alpha_{j}\sigma({\bf
w}_{j}^{T}{\bf{z}}+\theta_{j})\text{ for all }{\bf{z}}\in\mathbb{R}^{m},$

which satisfies

$\left|\Psi^{*}({\bf{z}})-g^{*}({\bf{z}})\right|<\epsilon\text{ for all
}{\bf{z}}\in[0,1]^{m}.$ (2.14)

Then, because ${\bf{f}}_{j}$ maps into $\mathbb{R}^{m}$ we conclude, in
particular, that

$\displaystyle\Psi^{*}({\bf{f}}_{j}({\vec{x}}))$
$\displaystyle=\sum_{j=1}^{N}\alpha_{j}\sigma({\bf
w}_{j}^{T}{\bf{f}}_{j}({\vec{x}})+\theta_{j})$

and

$\displaystyle\left|\Psi^{*}({\bf{f}}_{j}({\vec{x}}))-g({\vec{x}})\right|=\left|\Psi^{*}({\bf{f}}_{j}({\vec{x}}))-g^{*}({\bf{f}}_{j}({\vec{x}}))\right|<\epsilon.$

Therefore $\Psi^{\bf{f}}(\cdot):=\Psi^{*}({\bf{f}}_{j}(\cdot))$ satisfy the
claimed assertions. $\square$

It is obvious that the full variability in ${\bf w}$ is the key to bring our
proof and the universal approximation theorem in context. That is, if ${\bf
w}_{j}$, $\theta_{j}$, $j=1,\ldots,N$ are allowed to vary over
$\mathbb{R}^{n}$, $\mathbb{R}$, respectively. RQNNs are constrained to
$\theta_{j}<\left\|\vec{w}_{j}\right\|^{2}/(4\xi_{j})$ in Equation 2.7 and
thus Section 2 does not apply. Interestingly Section 4 applies and allows to
approximate functions in $\mathcal{L}^{1}(\mathbb{R}^{n})$ (even with rates).

######  Corollary  (Universal approximation properties of SBQNNs and CUNNs).

Let the discriminatory function $\sigma:\mathbb{R}\to\mathbb{R}$ be Lipschitz
continuous. All families of neural network functions from Section 2 satisfy
the universal approximation property on $[0,1]^{n}$.

######  Proof.

The proof follows from Section 2 and noting that all our functions
$\bf{f}_{j}$, $j=1,\ldots,N$ defined in Section 2 are injective. $\square$

## 3\. Motivation

### 3.1. Motivation 1: The Shepp-Logan phantom

Almost all tomographic algorithms are tested with the Shepp-Logan phantom (see
[30]). It is obvious that it can be exactly represented with a GQNN with 10
coefficients, while we conjecture that it can neither be exactly represented
with an ALNN or a DNN with a finite number of coefficients. This observation
extends immediately to all function that contains “localized” features. In
this sense sparse approximations with linear neural networks would be more
costly in practice.

### 3.2. Motivation 2: The Gauss-Newton iteration

Let us assume that $F:{\bf X}\to{\bf Y}$ is a linear operator. We consider the
solution $\bf p$ of Equation 1.2 to be an element of an ALNN or DNN, as
defined in Section 1. Therefore $\bf p$ can be parameterized by a vector
${\vec{p}}$ as in Equation 1.4 (for shallow linear neural networks) or
Equation 1.6 (for deep neural networks). For GQNNs the adequate
parametrization can be read out from Section 2. In other words, we can write
every searched for function $\bf p$ via an operator $\Psi$ which maps a
parameter ${\vec{p}}\in\mathbb{R}^{n_{*}}$ to a function in ${\bf X}$, i.e.,

${\vec{x}}\to{\bf p}({\vec{x}})=\Psi[{\vec{p}}]({\vec{x}}).$

Therefore, we aim for solving the _nonlinear_ operator equation

$\mathcal{N}({\vec{p}}):=F\circ\Psi[{\vec{p}}]={\bf y}.$ (3.1)

For ALNNs we have proven in [28] that the Gauss-Newton method (see Equation
3.7, below) is locally, quadratically convergent under conditions, which
guarantee that during the iteration the gradients of $\Psi$ does not
degenerate, i.e., that ${\bf P}$ is a finite-dimensional manifold. Let us now
calculate derivatives of the radial neural network operators $\Psi$ (see
Equation 2.5), which are the basis to prove that also the Gauss-Newton with
RQNNs is convergent:

######  Example .

Let $\sigma:\mathbb{R}\to\mathbb{R}$ be continuous activation function, where
all derivatives up to order $2$ are uniformly bounded, i.e., in formulas

$\sigma\in
C^{2}(\mathbb{R};\mathbb{R})\cap\mathcal{B}^{2}(\mathbb{R};\mathbb{R}),$ (3.2)

such as the sigmoid function. Then, the derivatives of a radial neural network
(RQNN) $\Psi$ as in Equation 2.5 with respect to the coefficients of
${\vec{p}}$ in Equation 2.2 are given by the following formulas, where
$\nu_{s}$ is defined in Equation 2.6:

  * •

Derivative with respect to $\alpha_{s}$, $s=1,\ldots,N$:

$\displaystyle\frac{\partial\Psi}{\partial\alpha_{s}}[{\vec{p}}]({\vec{x}})$
$\displaystyle=\sigma(\nu_{s})\text{ for }s=1,\ldots,N.$ (3.3)

  * •

Derivative with respect to $w_{s}^{(t)}$ where $s=1,\ldots,N$, $t=1,\ldots,n$:

$\displaystyle\frac{\partial\Psi}{\partial w_{s}^{(t)}}[{\vec{p}}]({\vec{x}})$
$\displaystyle=\sum_{j=1}^{N}\alpha_{j}\sigma^{\prime}(\nu_{j})\delta_{s=j}x_{t}=\alpha_{s}\sigma^{\prime}(\nu_{s})x_{t}\;.$
(3.4)

  * •

Derivative with respect to $\theta_{s}$ where $s=1,\ldots,N$:

$\displaystyle\frac{\partial\Psi}{\partial\theta_{s}}[{\vec{p}}]({\vec{x}})$
$\displaystyle=\sum_{j=1}^{N}\alpha_{j}\sigma^{\prime}(\nu_{j})\delta_{s=j}=\alpha_{s}\sigma^{\prime}(\nu_{s}).$
(3.5)

  * •

Derivative with respect $\xi_{s}$:

$\frac{\partial\Psi}{\partial\xi_{s}}[{\vec{p}}]({\vec{x}})=\alpha_{s}\sigma^{\prime}(\nu_{s})\left\|{\vec{x}}\right\|^{2}.$
(3.6)

Note, that all the derivatives above are functions in ${\bf
X}=L^{2}([0,1]^{n})$.

For formulating a convergence result for the Gauss-Newton method (see Equation
3.7) below) we need to specify the following assumptions, which were
postulated first in [28] to prove local convergence of a Gauss-Newton method
on a set of shallow affine linear network functions. Here we verify
convergence of the Gauss-Newton method on a set of RQNNs, as defined in
Equation 2.1. The proof is completely analogous as in [28].

######  Assumption .

  * •

$F:{\bf X}=L^{2}([0,1]^{n})\to{\bf Y}$ be a linear, bounded operator with
trivial nullspace and dense range.

  * •

$\Psi:\mathcal{D}\left(\Psi\right)\subseteq\mathbb{R}^{(n+2)N}\to{\bf X}$ is a
shallow RQNN generated by a strictly monotonic activation function $\sigma$
which satisfies Equation 3.2, like a sigmoid function.

  * •

All derivatives in Equation 3.3 \- Equation 3.6 are locally linearly
independent functions.

Now, we recall a local convergence result:

######  Theorem  (Local convergence of Gauss-Newton method with RQNNs).

Let $\mathcal{N}$ be as in Equation 3.1 be the composition of a linear
operator $F$ and the RQNN network operator as defined in Equation 2.5, which
satisfy Section 3.2. Moreover, let
${\vec{p}}^{0}\in\mathcal{D}\left(\Psi\right)$, which is open, be the starting
point of the Gauss-Newton iteration

$\displaystyle{\vec{p}}^{k+1}={\vec{p}}^{k}-\mathcal{N}^{\prime}({\vec{p}}^{k})^{\dagger}(\mathcal{N}({\vec{p}}^{k})-{\bf
y})\quad k\in\mathbb{N}_{0},$ (3.7)

where $\mathcal{N}^{\prime}({\vec{p}}^{k})^{\dagger}$ denotes the Moore-
Penrose inverse of $\mathcal{N}^{\prime}({\vec{p}}^{k})$.111For a detailed
exposition on generalized inverses see [22].

Moreover, let ${\vec{p}}^{\dagger}\in\mathcal{D}\left(\Psi\right)$ be a
solution of Equation 3.1, i.e.,

$\mathcal{N}({\vec{p}}^{\dagger})={\bf y}.$ (3.8)

Then the Gauss-Newton iterations are locally, that is if ${\vec{p}}^{0}$ is
sufficiently close to ${\vec{p}}^{\dagger}$, and quadratically converging.

######  Remark 2.

The essential condition in Section 3.2 is that all derivatives of $\Psi$ with
respect to ${\vec{p}}$ are linearly independent, which is a nontrivial
research question. In [28] we studied convergence of the Gauss-Newton method
on a set of shallow affine linear neural networks, where the convergence
result required linear independence of the derivatives specified in Equation
3.3 \- Equation 3.5. Here, for RQNNs, on top, linear independence of the 2nd
order moment function Equation 3.6 needs to hold. Even linear independence of
neural network functions (with derivatives) is still a challenging research
topic (see [17]).

Under our assumptions the ill–posedness of $F$ does not affect convergence of
the Gauss-Newton method. The generalized inverse completely annihilates $F$ in
the iteration. The catch however is, that the data has to be attained in a
finite dimensional space spanned by neurons (that is Equation 3.8 holds). This
assumption is in fact restrictive: Numerical tests show that convergence of
Gauss-Newton methods becomes arbitrarily slow if it is violated. Here the ill-
posedness of $F$ enters. The proof of Section 3.2 is based on the _affine
covariant_ condition (see for instance [8]).

In the following we show the complexity of the convergence condition of a
Gauss-Newton method in the case when affine linear _deep neural network
functions_ are used for coding.

######  Example  (Convergence conditions of deep neural networks).

We restrict our attention to the simple case $n=1$. We consider a 4-layer DNN
(consisting of two internal layers) with $\sigma_{1}=\sigma_{2}=\sigma$, which
reads as follows:

$x\to\Psi[{\vec{p}}](x):=\sum_{j_{2}=1}^{N_{2}}\alpha_{j_{2},2}\sigma\left(w_{j_{2},2}\left(\sum_{j_{1}=1}^{N_{1}}\alpha_{j_{1},1}\sigma\left(w_{j_{1},1}x+\theta_{j_{1},1}\right)\right)+\theta_{j_{2},2}\right).$
(3.9)

Now, we calculate by chain rule $\frac{\partial\Psi}{\partial
w_{1,1}}[{\vec{p}}](x)$. For this purpose we define

$w_{1,1}\to\rho(w_{1,1}):=\sum_{j_{1}=1}^{N_{1}}\alpha_{j_{1},1}\sigma\left(w_{j_{1},1}x+\theta_{j_{1},1}\right).$

With this definition we rewrite Equation 3.9 to

$x\to\Psi[{\vec{p}}](x):=\sum_{j_{2}=1}^{N_{2}}\alpha_{j_{2},2}\sigma\left(w_{j_{2},2}\rho(w_{1,1})+\theta_{j_{2},2}\right),$

Since

$\rho^{\prime}(w_{1,1}):=\alpha_{j_{1},1}\sigma^{\prime}\left(w_{1,1}x+\theta_{1,1}\right)x,$

we therefore get

$\displaystyle\frac{\partial\Psi}{\partial w_{1,1}}$
$\displaystyle=\sum_{j_{2}=1}^{N_{2}}\alpha_{j_{2},2}\sigma^{\prime}\left(w_{j_{2},2}\rho(w_{1,1})+\theta_{j_{2},2}\right)w_{j_{2},2}\rho^{\prime}(w_{1,1})$
(3.10)
$\displaystyle=\alpha_{j_{1},1}x\sum_{j_{2}=1}^{N_{2}}\alpha_{j_{2},2}w_{j_{2},2}\sigma^{\prime}\left(w_{j_{2},2}\rho(w_{1,1})+\theta_{j_{2},2}\right)\sigma^{\prime}\left(w_{1,1}x+\theta_{1,1}\right).$

Note that $\Psi[{\vec{p}}]$ is a function of $x$ depending on the parameter
${\vec{p}}$, which contains $w_{1,1}$ as one component.

The complicating issue in a potential convergence analysis concerns the last
identity, Equation 3.10, where evaluations of $\sigma^{\prime}$ at different
arguments appear simultaneously, which makes it complicated to analyze and
interpret linear independence of derivatives of $\Psi$ with respect to the
single elements of ${\vec{p}}$. Note that for proving convergence of the
Gauss-Newton method, according to Equation 3.10, we need to verify linear
independence of then functions

$\displaystyle x\to$
$\displaystyle\sigma^{\prime}\left(w_{j_{2},2}\rho(w_{1,1})+\theta_{j_{2},2}\right)\sigma^{\prime}\left(w_{1,1}x+\theta_{1,1}\right)$
$\displaystyle=\sigma^{\prime}\left(w_{j_{2},2}\left(\sum_{j_{1}=1}^{N_{1}}\alpha_{j_{1},1}\sigma\left(w_{j_{1},1}x+\theta_{j_{1},1}+\theta_{j_{2},2}\right)\right)\right)\sigma^{\prime}\left(w_{1,1}x+\theta_{1,1}\right).$

In other word, the potential manifold of quadratic neural networks is
extremely complex.

The conclusion of this section is that the analysis of iterative
regularization methods, like a Gauss-Newton method, gets significantly more
complicated if deep neural networks are used as ansatz functions. In contrast
using neural network with higher order nodes (such as radial) results in
transparent moment conditions. So the research question discussed in the
following is whether shallow higher order neural networks have similar
approximation properties than deep neural network functions, which would
reveal clear benefits of such for analyzing iterative methods for solving
ill–posed problems.

## 4\. Convergence rates for universal approximation of RQNNs

In the following we prove convergence rates of RQNNs (as defined in Equation
2.5) in the $\mathcal{L}^{1}$-norm. To be precise we specify a subclass on
RQNNs for which we prove convergence rates results. This is a much finer
result than the standard universal approximation result, Section 2, since it
operates on a subclass and provides convergence rates. However, it is the only
approximation result so far, which we can provide. We recall that the
constraints, $\xi_{j}\neq 0$ and $\kappa_{j}/\xi_{j}<0$ (see Equation 2.7),
induce that the level-sets of the neurons are compact (circles) and not
unbounded, as they are for shallow affine linear neurons. Therefore we require
a different analysis (and different spaces) than in the most advanced and
optimal convergence rates results for affine linear neural networks as for
instance in [32, 31]. In fact the analysis is closer to an analysis of compact
wavelets.

The convergence rate will be expressed in the following norm:

######  Definition .

$\mathcal{L}^{1}$ denotes the space of square integrable functions on
$[0,1]^{n}$, which satisfy [2, (1.10)]

$\|f\|_{\mathcal{L}^{1}}:=\inf\left\\{\sum_{g\in D}|c_{g}|:f=\sum_{g\in
D}c_{g}g\right\\}<\infty.$

Here $c_{g}$ are the coefficients of an wavelet expansion and $D$ is a
countable, general set of wavelet functions. A discrete wavelet basis (see,
for example, [6, 12, 19, 4]) is a (not necessarily orthonormal) basis of the
space of square integrable functions, where the basis elements are given by
dilating and translating a mother wavelet function.

######  Remark 3.

Notice that the notation $\mathcal{L}^{1}$ does not refer to the common
$L^{1}$-function space of absolutely integrable functions and depends on the
choice of the wavelet system. For more properties and details on this space
see [29, Remark 3.11].

######  Definition  (Circular scaling function and wavelets).

Let $r>0$ be a fixed constant and $\sigma$ be a discriminatory function as
defined in Section 2 such that
$\left|\int_{\mathbb{R}^{n}}\sigma(r^{2}-\|{\vec{x}}\|^{2})d{\vec{x}}\right|<\infty$.
Then let

${\vec{x}}\in\mathbb{R}^{n}\to\varphi({\vec{x}}):=C_{n}\sigma(r^{2}-\left\|{\vec{x}}\right\|^{2}),$
(4.1)

where $C_{n}$ is a normalizing constant such that
$\int_{\mathbb{R}^{n}}\varphi({\vec{x}})d{\vec{x}}=1$.
Then we define for $k\in\mathbb{Z}$ the _radial scaling functions_ and
_wavelets_

$\displaystyle({\vec{y}},{\vec{y}})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\to
S^{C}_{k}({\vec{x}},{\vec{y}})$
$\displaystyle:=2^{k}\varphi(2^{k/n}({\vec{x}}-{\vec{y}}))\text{ and }$ (4.2)
$\displaystyle({\vec{y}},{\vec{y}})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\to\psi^{C}_{k}({\vec{x}},{\vec{y}})$
$\displaystyle:=2^{-k/2}(S^{C}_{k}({\vec{x}},{\vec{y}})-S^{C}_{k-1}({\vec{x}},{\vec{y}})).$

Often ${\vec{y}}\in\mathbb{R}^{n}$ is considered a parameter and we write
synonymously

$\displaystyle{\vec{x}}\to
S^{C}_{k,{\vec{y}}}({\vec{x}})=S^{C}_{k}({\vec{x}},{\vec{y}})\text{ and
}{\vec{x}}\to\psi^{C}_{k,{\vec{y}}}({\vec{x}})=\psi^{C}_{k}({\vec{x}},{\vec{y}}).$
(4.3)

In particular, this notation means that $S^{C}_{k,{\vec{y}}}$ and
$\psi^{C}_{k,{\vec{y}}}$ are considered solely functions of the variable
${\vec{x}}$.

We consider the following subset of RQNNs

$\mathcal{S}^{C}_{d}:=\left\\{S^{C}_{k,{\vec{y}}}:k\in\mathbb{Z}\text{ and
}{\vec{y}}\in 2^{-k/n}\mathbb{Z}^{n}\right\\}.$ (4.4)

This is different to standard universal approximation theorems, where an
uncountable number of displacements are considered. Moreover, we define the
discrete Wavelet space

$\mathcal{W}^{C}_{d}:=\left\\{\psi^{C}_{k,{\vec{y}}}:=2^{-k/2}\left(S^{C}_{k,{\vec{y}}}-S^{C}_{k-1,{\vec{y}}}\right):k\in\mathbb{Z}\text{
and }{\vec{y}}\in 2^{-k/n}\mathbb{Z}^{n}\right\\}.$ (4.5)

According to Appendix A, in order to prove the following approximation result,
we only require to verify that $\mathcal{S}_{d}^{C}$ satisfies the
blueconditions for symmetric AtI and the double Lipschitz condition (see
Appendix A), which originate from [7, Def. 3.4].

######  Corollary .

$\mathcal{W}_{d}^{C}$ is a frame and for every function
$f\in\mathcal{L}^{1}(\mathbb{R}^{n})$ there exists a linear combination of $N$
elements of $\mathcal{W}_{d}^{C}$, denoted by $f_{N}$, satisfying

$\left\|f-f_{N}\right\|_{L^{2}}\leq\left\|f\right\|_{\mathcal{L}^{1}}(N+1)^{-1/2}.$
(4.6)

For proving the approximation to identity, AtI, property of the functions
$S^{C}_{k}$, $k\in\mathbb{Z}$, we use the following basic inequality.

######  Lemma 4.1.

Let $h:\mathbb{R}^{n}\to\mathbb{R}$ be a twice differentiable function, which
can be expressed in the following way:

$h({\vec{x}})=h_{s}(\left\|{\vec{x}}\right\|^{2})\text{ for all
}{\vec{x}}\in\mathbb{R}^{n}.$

Then the spectral norm of the Hessian of $h$ can be estimated as follows:222In
the following $\nabla$ and $\nabla^{2}$ (without subscripts) always denote
derivatives with respect to an $n$-dimensional variable such as ${\vec{x}}$. ′
and ′′ denotes derivatives of a one-dimensional function.

$\left\|\nabla^{2}h({\vec{x}})\right\|\leq\max\left\\{\left|4\left\|{\vec{x}}\right\|^{2}h_{s}^{\prime\prime}(\left\|{\vec{x}}\right\|^{2})+2h_{s}^{\prime}(\left\|{\vec{x}}\right\|^{2})\right|,\left|2h_{s}^{\prime}(\left\|{\vec{x}}\right\|^{2})\right|\right\\}.$
(4.7)

######  Proof.

Since $\nabla^{2}h({\vec{x}})$ is a symmetric matrix, its operator norm is
equal to its spectral radius, namely the largest absolute value of an
eigenvalue. By routine calculation we can see that

$\nabla_{x_{i}x_{j}}h({\vec{x}})=4x_{i}x_{j}h_{s}^{\prime\prime}(\left\|{\vec{x}}\right\|^{2})+2\delta_{ij}h_{s}^{\prime}(\left\|{\vec{x}}\right\|^{2}).$
$4h_{s}^{\prime\prime}(\left\|\vec{x}\right\|^{2})C\vec{z}=(-2h_{s}^{\prime}(\left\|{\vec{x}}\right\|^{2})+\lambda)\vec{z}.$

Or in other words
$\frac{-2h_{s}^{\prime}(\left\|{\vec{x}}\right\|^{2})+\lambda}{4h_{s}^{\prime\prime}(\left\|x\right\|^{2})}$
is an eigenvalue of $C$. Moreover, $C={\vec{x}}{\vec{x}}^{T}$ is a rank one
matrix and thus the spectral values are $0$ with multiplicity $(n-1)$ and
$\left\|{\vec{x}}\right\|^{2}$. This in turn shows that the eigenvalues of the
Hessian are $+2h_{s}^{\prime}(\left\|{\vec{x}}\right\|^{2})$ (with
multiplicity $n-1$) and
$4\left\|{\vec{x}}\right\|^{2}h_{s}^{\prime\prime}(\left\|{\vec{x}}\right\|^{2})+2h_{s}^{\prime}(\left\|{\vec{x}}\right\|^{2})$,
which proves Equation 4.7.

$\square$

In the following lemma, we will prove that the kernels
$(S^{C}_{k})_{k\in\mathbb{Z}}$ are an AtI.

######  Lemma 4.2.

Let $r>0$ be fixed. Suppose that the activation function
$\sigma:\mathbb{R}\to\mathbb{R}$ is monotonically increasing and satisfies for
the $i$-th derivative ($i=0,1,2$)

$\left|\sigma^{i}(r^{2}-t^{2})\right|\leq
C_{\sigma}(1+\left|t\right|^{n})^{-1-{(2i+1)/n}}\text{ for all
}t\in\mathbb{R}.$ (4.8)

Then the kernels $(S^{C}_{k})_{k\in\mathbb{Z}}$ as defined in Equation 4.2
form an AtI as defined in Appendix A that also satisfy the double Lipschitz
condition Equation A.4.

######  Proof.

We verify the three conditions from Appendix A as well as Equation A.4. First
of all, we note that

$\left|\sigma^{i}(r^{2}-\left\|{\vec{x}}\right\|^{2})\right|\leq
C_{\sigma}(1+\left\|{\vec{x}}\right\|^{n})^{-1-{(2i+1)/n}}\text{ for all
}{\vec{x}}\in\mathbb{R}^{n}.$ (4.9)

  * •

Verification of item (i) in Appendix A: Equation 4.1 and Equation 4.8 imply
that

$0\leq\varphi({\vec{x}}-{\vec{y}})=C_{n}\sigma(r^{2}-\left\|{\vec{x}}-{\vec{y}}\right\|^{2})\leq
C_{\sigma}C_{n}(1+\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{-1-1/n}\text{ for
all }{\vec{x}},{\vec{y}}\in\mathbb{R}^{n}.$ (4.10)

Therefore

$\displaystyle S^{C}_{k}({\vec{x}},{\vec{y}})$
$\displaystyle=2^{k}\varphi(2^{k/n}({\vec{x}}-{\vec{y}}))\leq
C_{\sigma}C_{n}2^{k}(1+2^{k}\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{-1-1/n}$
$\displaystyle=C_{\sigma}C_{n}2^{-k/n}(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{-1-1/n}.$

Thus item (i) in Appendix A holds with $\epsilon=1/n$ and $C_{\rho}=1$ and
$C=C_{n}C_{\sigma}$.

  * •

Verification of item (ii) in Appendix A with $C_{\rho}=1$ and $C_{A}=2^{-n}$:
Because $\sigma$ is monotonically increasing it follows from Equation 4.1 and
the fact that $S_{0}(\vec{x},\vec{y})=\varphi(\vec{x}-\vec{y})$ (see Equation
4.2) and Section 4 that

$F_{\vec{y}}({\vec{x}}):=\left\|\nabla_{\vec{x}}(S_{0}({\vec{x}},{\vec{y}}))\right\|=2C_{n}\left\|{\vec{x}}-{\vec{y}}\right\|\sigma^{\prime}(r^{2}-\left\|{\vec{x}}-{\vec{y}}\right\|^{2})\text{
for all }{\vec{y}}\in\mathbb{R}^{n}.$

Then Equation 4.9 implies that

$\displaystyle F_{\vec{y}}({\vec{x}})$ $\displaystyle\leq
2C_{n}C_{\sigma}(1+\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{-1-3/n}\left\|{\vec{x}}-{\vec{y}}\right\|$
$\displaystyle\leq
2C_{n}C_{\sigma}(1+\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{-1-3/n}(1+\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{\frac{1}{n}}$
$\displaystyle=2C_{n}C_{\sigma}(1+\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{-1-{2/n}}.$

From the definition of $S^{C}_{k}({\vec{x}},{\vec{y}})$, it follows

$\displaystyle\left\|\nabla_{\vec{x}}(S^{C}_{k}({\vec{x}},{\vec{y}}))\right\|$
$\displaystyle=\left\|\nabla_{\vec{x}}(2^{k}\varphi(2^{{k/n}}({\vec{x}}-{\vec{y}})))\right\|=2^{k}\left\|\nabla_{\vec{x}}S_{0}(2^{{k/n}}{\vec{x}},2^{{k/n}}{\vec{y}})\right\|$
(4.11) $\displaystyle=2^{k+{k/n}}F_{2^{{k/n}}{\vec{y}}}(2^{{k/n}}{\vec{x}})$
$\displaystyle\leq
2^{-k/n}C_{n}C_{\sigma}(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{-1-{2/n}}.$

From the mean value theorem it therefore follows from Equation 4.11 and
Equation A.6 that

$\displaystyle\frac{\left|S^{C}_{k}({\vec{x}},{\vec{y}})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}})\right|}{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|}$
(4.12) $\displaystyle\leq$
$\displaystyle\max_{\left\\{\vec{z}=t{\vec{x}}^{\prime}+(1-t){\vec{x}}:t\in[0,1]\right\\}}\left\|\nabla_{\vec{x}}(S^{C}_{k}(\vec{z},{\vec{y}}))\right\|$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}C_{n}C_{\sigma}\max_{\left\\{\vec{z}={\vec{x}}+t({\vec{x}}^{\prime}-{\vec{x}}):t\in[0,1]\right\\}}(2^{-k}+\left\|\vec{z}-{\vec{y}}\right\|^{n})^{-1-{2/n}}$
$\displaystyle=$ $\displaystyle
2^{-k/n}C_{n}C_{\sigma}\left(2^{-k}+\min_{\left\\{\vec{z}={\vec{x}}+t({\vec{x}}^{\prime}-{\vec{x}}):t\in[0,1]\right\\}}\left\|\vec{z}-{\vec{y}}\right\|^{n}\right)^{-1-{2/n}}.$

Then application of Equation A.6 and noting that $\frac{1-2^{-n}}{2^{-n}}\geq
1$ gives

$\displaystyle\frac{\left|S^{C}_{k}({\vec{x}},{\vec{y}})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}})\right|}{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|}$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}C_{n}C_{\sigma}\left((1-2^{-n})2^{-k}+2^{-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{-1-{2/n}}$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}\left(2^{-n}\right)^{-1-{2/n}}C_{n}C_{\sigma}\left(\frac{(1-2^{-n})}{2^{-n}}2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{-1-{2/n}}$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}2^{n+2}C_{n}C_{\sigma}\left(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{-1-{2/n}}.$

Therefore item (ii) is satisfied with $C_{\rho}=1$, $\zeta=1/n$,
$\epsilon=1/n$ and $C=2^{n+2}C_{n}C_{\sigma}$.

  * •

Verification of item (iii) in Appendix A: From the definition of $S^{C}_{k}$
(see Equation 4.2) it follows that for every $k\in\mathbb{Z}$ and
${\vec{y}}\in\mathbb{R}^{n}$

$1=\int_{\mathbb{R}^{n}}S^{C}_{k}({\vec{x}},{\vec{y}})d{\vec{x}}=\int_{\mathbb{R}^{n}}2^{k}\varphi(2^{k/n}({\vec{x}}-{\vec{y}}))d{\vec{x}}.$

  * •

Verification of the double Lipschitz condition Equation A.4 in Appendix A: By
using the integral version of the mean value theorem, we have

$\displaystyle
S^{C}_{k}({\vec{x}},{\vec{y}})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}})-S^{C}_{k}({\vec{x}},{\vec{y}}^{\prime})+S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}}^{\prime})$
$\displaystyle=S^{C}_{k}({\vec{x}},{\vec{y}})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}})-(S^{C}_{k}({\vec{x}},{\vec{y}}^{\prime})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}}^{\prime}))$
$\displaystyle=\int_{0}^{1}\langle\nabla_{\vec{y}}S^{C}_{k}({\vec{x}},{\vec{y}}^{\prime}+t({\vec{y}}-{\vec{y}}^{\prime})),{\vec{y}}-{\vec{y}}^{\prime}\rangle
dt$
$\displaystyle\qquad-\int_{0}^{1}\langle\nabla_{\vec{y}}S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}}^{\prime}+t({\vec{y}}-{\vec{y}}^{\prime})),{\vec{y}}-{\vec{y}}^{\prime}\rangle
dt$
$\displaystyle=\int_{0}^{1}\int_{0}^{1}\langle\nabla_{{\vec{x}},{\vec{y}}}S^{C}_{k}({\vec{x}}^{\prime}+s({\vec{x}}-{\vec{x}}^{\prime}),{\vec{y}}^{\prime}+t({\vec{y}}-{\vec{y}}^{\prime}))({\vec{x}}-{\vec{x}}^{\prime}),{\vec{y}}-{\vec{y}}^{\prime}\rangle
dtds.$

Following this identity, we get

$\displaystyle\frac{\left|S^{C}_{k}({\vec{x}},{\vec{y}})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}})+S^{C}_{k}({\vec{x}},{\vec{y}}^{\prime})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}}^{\prime})\right|}{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|\left\|{\vec{y}}-{\vec{y}}^{\prime}\right\|}$
(4.13) $\displaystyle\leq$
$\displaystyle\max_{\texttt{I}}\left\|\nabla_{\vec{y}}\left(\frac{S^{C}_{k}({\vec{x}},\vec{z})-S^{C}_{k}({\vec{x}}^{\prime},\vec{z})}{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|}\right)\right\|\leq\max_{\texttt{Q}}\left\|\nabla^{2}_{{\vec{x}}{\vec{y}}}S^{C}_{k}(\vec{z}^{\prime},\vec{z})\right\|,$

where

I
$\displaystyle:=\left\\{\vec{z}=t{\vec{y}}+(1-t){\vec{y}}^{\prime}:t\in[0,1]\right\\},$
Q
$\displaystyle:=\left\\{(\vec{z}=t_{{\vec{y}}}{\vec{y}}+(1-t_{{\vec{y}}}){\vec{y}}^{\prime},\vec{z}^{\prime}=t_{{\vec{x}}}{\vec{x}}+(1-t_{{\vec{x}}}){\vec{x}}^{\prime}):t_{{\vec{y}}}\in[0,1],t_{{\vec{x}}}\in[0,1]\right\\},$

and
$\left\|\nabla^{2}_{{\vec{x}}{\vec{y}}}S^{C}_{k}(\vec{z}^{\prime},\vec{z})\right\|$
denotes again the spectral norm of
$\nabla^{2}_{{\vec{x}}{\vec{y}}}S^{C}_{k}(\vec{z}^{\prime},\vec{z})$.

Now, we estimate the right hand side of Equation 4.13: From the definition of
$S^{C}_{k}$, Equation 4.2, and the definition of $\varphi$, Equation 4.1, it
follows with the abbreviation
$\vec{\omega}=2^{{k/n}}(\vec{z}^{\prime}-\vec{z})$:

$\displaystyle\left\|\nabla^{2}_{{\vec{x}}{\vec{y}}}S^{C}_{k}(\vec{z}^{\prime},\vec{z})\right\|$
$\displaystyle=2^{k}\left\|\nabla^{2}_{{\vec{x}}{\vec{y}}}(\varphi\circ(2^{{k/n}}\cdot))(\vec{z}^{\prime}-\vec{z}))\right\|=2^{k(1+2/n)}\left\|\nabla^{2}\varphi(\vec{\omega}))\right\|.$

Applications of Lemma 4.1 with ${\vec{x}}\to h({\vec{x}})=\varphi({\vec{x}})$
and

$t\to h_{s}(t)=C_{n}\sigma(r^{2}-t)$

shows that (note that $h_{s}^{\prime}(t)=-C_{n}\sigma^{\prime}(r^{2}-t)$)

$\displaystyle\left\|\nabla^{2}\varphi(\vec{\omega})\right\|$ (4.14)
$\displaystyle\leq$ $\displaystyle
C_{n}\max\left\\{\left|4\left\|\vec{\omega}\right\|^{2}\sigma^{\prime\prime}(r^{2}-\left\|\vec{\omega}\right\|^{2})-2\sigma^{\prime}(r^{2}-\left\|\vec{\omega}\right\|^{2})\right|,\left|2\sigma^{\prime}(r^{2}-\left\|\vec{\omega}\right\|^{2})\right|\right\\}$
$\displaystyle\leq$ $\displaystyle
2^{2}C_{n}\max\left\\{2\left\|\vec{\omega}\right\|^{2}\left|\sigma^{\prime\prime}(r^{2}-\left\|\vec{\omega}\right\|^{2})\right|,\left|\sigma^{\prime}(r^{2}-\left\|\vec{\omega}\right\|^{2})\right|\right\\}.$

Thus from Equation 4.9 it follows that

$\displaystyle\left\|\nabla^{2}_{{\vec{x}}{\vec{y}}}S^{C}_{k}(\vec{z}^{\prime},\vec{z})\right\|\leq$
$\displaystyle
2^{2}2^{k(1+2/n)}C_{n}C_{\sigma}\max\left\\{2\left\|\vec{\omega}\right\|^{2}(1+\left\|\vec{\omega}\right\|^{n})^{-1-{5/n}},(1+\left\|\vec{\omega}\right\|^{n})^{-1-3/n}\right\\}$
$\displaystyle\leq$ $\displaystyle
2^{3}2^{k(1+2/n)}C_{n}C_{\sigma}(1+\left\|\vec{\omega}\right\|^{n})^{-1-3/n}$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}2^{3}C_{n}C_{\sigma}(2^{-k}+\left\|\vec{z}^{\prime}-\vec{z}\right\|^{n})^{-1-3/n}.$

In the next step we note that from Equation A.7 it follows that

$\left\|\vec{z}^{\prime}-\vec{z}\right\|^{n}\geq
3^{-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-3^{-n}2^{1-k}.$ (4.15)

Thus we get because $\frac{1-3^{-n}2}{3^{-n}}\geq 1$

$\displaystyle\frac{\left|S^{C}_{k}({\vec{x}},{\vec{y}})-S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}})-S^{C}_{k}({\vec{x}},{\vec{y}}^{\prime})+S^{C}_{k}({\vec{x}}^{\prime},{\vec{y}}^{\prime})\right|}{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|\left\|{\vec{y}}-{\vec{y}}^{\prime}\right\|}$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}2^{3}C_{n}C_{\sigma}\left((1-3^{-n}2)2^{-k}+3^{-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{-1-3/n}$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}2^{3}(3^{-n})^{-1-3/n}C_{n}C_{\sigma}\left(\frac{1-3^{-n}2}{3^{-n}}2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{-1-3/n}$
$\displaystyle\leq$ $\displaystyle
2^{-k/n}2^{3}3^{n+3}C_{n}C_{\sigma}\left(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{-1-3/n}.$

Therefore item (iii) is satisfied with $C_{\rho}=1$,
$\tilde{C}=2^{3}3^{n+3}C_{n}C_{\sigma}$, $\zeta=1/n$, and $\epsilon=1/n$.

$\square$

We have shown with Lemma 4.2 that the functions
$\left\\{S^{C}_{k}:k\in\mathbb{Z}\right\\}$ form an AtI, which satisfies the
double Lipschitz condition (see Appendix A). Moreover, for activations
functions, like the sigmoid function, Equation 4.8 it follows that

$\lim_{t\to\pm\infty}(1+\left|t\right|^{n})^{1+{(2i+1)/n}}\left|\sigma^{i}(r^{2}-t^{2})\right|=0,$
(4.16)

which shows Equation 3.2. The limit result is an easy consequence of the fact
that $t\to\mathrm{e}^{-t^{2}}$ and its derivative are faster decaying to
$zero$ than the functions $t\to(1+\left|t\right|^{n})^{-1-{(2i+1)/n}}$.
Therefore, it follows from Appendix A that the set $\mathcal{W}_{d}^{C}$ is a
wavelet frame and satisfies the estimate Equation A.14. We summarize this
important result:

######  Theorem  ($\mathcal{L}^{1}$-convergence of radial wavelets).

Let $\sigma$ be an activation function that satisfies the conditions in Lemma
4.2. Then, for every function $f\in\mathcal{L}^{1}(\mathbb{R}^{n})$ (see
Section 4 for a definition of the space) and every $N\in\mathbb{N}$, there
exists a function

$f_{N}\in\text{span}_{N}(\mathcal{W}^{C}_{d})\subseteq\mathcal{L}^{1}(\mathbb{R}^{n}),$

and $\text{span}_{N}$ denotes linear combinations of at most $N$ terms in the
set, such that

$\left\|f-f_{N}\right\|_{L^{2}}\leq\left\|f\right\|_{\mathcal{L}^{1}}(N+1)^{-1/2}.$
(4.17)

Using Section 4 we are able to formulate the main result of this paper:

######  Corollary  ($\mathcal{L}^{1}$-convergence of RQNNs).

Let the assumptions of Section 4 be satisfied. Then, for every function
$f\in\mathcal{L}^{1}(\mathbb{R}^{n})$ (see Section 4) and every
$N\in\mathbb{N}$, there exists a parametrization vector

$\vec{p}=[\alpha_{1},\ldots,\alpha_{2N};{\bf w}_{1},\ldots,{\bf
w}_{2N};\xi_{1},\ldots,\xi_{2N};\theta_{1},\ldots,\theta_{2N}].$

such that

$\left\|f-\Psi[{\vec{p}}]\right\|_{L^{2}}\leq\left\|f\right\|_{\mathcal{L}^{1}}(N+1)^{-1/2},$
(4.18)

where $\Psi[{\vec{p}}]$ is a RQNN from Equation 2.5.

######  Proof.

From Section 4 it follows that there exists
$f_{N}\in\text{span}_{N}(\mathcal{W}^{C}_{d})$, which satisfies Equation 4.17.
By definition,

$f_{N}({\vec{x}})=\sum_{k\in\mathbb{Z}}\sum_{\vec{j}\in\mathbb{Z}^{n}}\chi_{f,N}(k,\vec{j})\beta_{k,\vec{j}}\psi^{C}_{k,2^{-k/n}\vec{j}}({\vec{x}}),$

where $\chi_{f,N}$ denotes the characteristic function of a set of indices of
size $N$. Using the definition of $\psi^{C}_{k}$ we get from Equation 4.2 and
Equation 4.1

$\displaystyle f_{N}({\vec{x}})$
$\displaystyle=\sum_{k\in\mathbb{Z}}\sum_{\vec{j}\in\mathbb{Z}^{n}}\chi_{f,N}(k,\vec{j})\beta_{k,\vec{j}}2^{-k/2}\left(S^{C}_{k,2^{-k/n}\vec{j}}({\vec{x}})-S^{C}_{k-1,2^{-k/n}\vec{j}}({\vec{x}})\right)$
$\displaystyle=\sum_{k\in\mathbb{Z}}\sum_{\vec{j}\in\mathbb{Z}^{n}}\chi_{f,N}(k,\vec{j})\beta_{k,\vec{j}}2^{-k/2}\left(2^{k}\varphi(2^{k/n}({\vec{x}}-2^{-k/n}\vec{j}))-2^{k-1}\varphi(2^{(k-1)/n}({\vec{x}}-2^{-k/n}\vec{j}))\right)$
$\displaystyle=\sum_{k\in\mathbb{Z}}\sum_{\vec{j}\in\mathbb{Z}^{n}}\chi_{f,N}(k,\vec{j})C_{n}\beta_{k,\vec{j}}2^{-k/2}$
$\displaystyle\qquad\left(2^{k}\sigma\left(r^{2}-\left\|2^{k/n}\left({\vec{x}}-2^{-k/n}\vec{j}\right)\right\|^{2}\right)-2^{k-1}\sigma\left(r^{2}-\left\|2^{(k-1)/n}\left({\vec{x}}-2^{-k/n}\vec{j}\right)\right\|^{2}\right)\right).$

The arguments where $\sigma$ is evaluated are in general different, and thus
we get

$\displaystyle f_{N}({\vec{x}})$
$\displaystyle=\sum_{k\in\mathbb{Z}}\sum_{\vec{j}\in\mathbb{Z}^{n}}\underbrace{\chi_{f,N}(k,\vec{j})C_{n}\beta_{k,\vec{j}}2^{k/2}}_{=\alpha_{j}}\sigma\left(\underbrace{r^{2}}_{=\theta_{j}}\underbrace{-4^{k/n}}_{=\xi_{j}}\|{\vec{x}}-\underbrace{2^{-k/n}\vec{j}}_{={\vec{y}}_{j}}\|^{2}\right)$
$\displaystyle\qquad+\sum_{k\in\mathbb{Z}}\sum_{\vec{j}\in\mathbb{Z}^{n}}\underbrace{\chi_{f,N}(k,\vec{j})C_{n}\beta_{k,\vec{j}}2^{k/2-1}}_{\alpha_{j}}\sigma\left(\underbrace{r^{2}}_{\theta_{j}}\underbrace{-4^{(k-1)/n}}_{=\xi_{j}}\|{\vec{x}}-\underbrace{2^{-k/n}\vec{j}}_{{\vec{y}}_{j}}\|^{2}\right)$

from which the coefficients can be read out. Note that for the sake of
simplicity we have not explicitly stated the exact index in the subscript of
the coefficients $(\vec{\alpha},\vec{\theta},\vec{\xi},{\bf y})$, or in other
words we use the formal relation $j=(k,\vec{j})$ to indicate the dependencies.
This shows the claim if we identify $\theta_{j}=r^{2}$ and

${\bf w}^{T}=2^{1+{2k/n}}{\vec{y}}.$

$\square$

######  Remark 4.

Our results in section 4 are proved using “similar” methods as in [29], but
can not be used directly. Because the main ingredient of the proof is the
construction of _localizing_ functions as wavelets. This task requires two
layers of affine linear decision functions to accomplish, since the linear
combinations of functions of the form
${\vec{x}}\to\varphi({\vec{x}}):=C_{n}\sigma(\vec{w}^{T}{\vec{x}}+\theta)$ are
not localized; they _cannot_ satisfy item (iii) in Appendix A, as they are not
integrable on $\mathbb{R}^{n}$. In comparison, some quadratic decision
functions - such as those used in Section 4 - naturally gives localized
functions, and therefore can work as wavelets on their own.

We mention that there exists a zoo of approximation rates results for neural
network functions (see for instance [32, 31], where best-approximation results
in dependence of the space-dimension $n$ have been proven). We have based our
analysis on convergence rates results of [29] and [7]. This choice is
motivated by the fact that the AtI property from [7] is universal, and allows
a natural extension of their results to quadratic neural network functions.
The motivation here is not to give the optimal convergence rates result for
quadratic neural networks, but to verify that convergence rates results are
possible. We believe that AtI is a very flexible and elegant tool.

## 5\. Conclusion

In this paper we studied generalized neural networks functions for solving
inverse problems. We proved a universal approximation theorem and we have
proven convergence rates of radial neural networks, which are the same order
as the classical affine linear neural network functions, but with vastly
reduced numbers of elements (in particular it spares one layer). The paper
presents a proof of concept and thus we restrict attention only to radial
neural networks although generalizations to higher order neural networks (such
as cubic) is quite straightforward.

We also make the remark about the convergence of the actual training process
of a neural network, i.e. optimization of the parameters of each decision
function. This is usually done by gradient descent or Gauss-Newton-type
methods. From the analysis in [28] the convergence conditions of Newton’s
method become very complicated for DNNs, but are transparent for quadratic
neural networks, which is fact a matter of the complicated chain rule, when
differentiating DNNs with respect to the parameters. For such an analysis
there is a clear preference to go higher with the degree of polynomials than
increasing the number of layers.

##  Appendix A Approximation to the identity (AtI)

######  Definition  (Approximation to the identity [7]).

A sequence of _symmetric kernel functions_
$(S_{k}:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R})_{k\in\mathbb{Z}}$ is
said to be an _approximation to the identity (AtI)_ if there exist a quintuple
$(\epsilon,\zeta,C,C_{\rho},C_{A})$ of positive numbers satisfying the
additional constraints

$0<\epsilon\leq\frac{1}{n},0<\zeta\leq\frac{1}{n}\text{ and }C_{A}<1$ (A.1)

the following three conditions are satisfied for all $k\in\mathbb{Z}$:

  1. (i)

$\left|S_{k}({\vec{x}},{\vec{y}})\right|\leq
C\frac{2^{-k\epsilon}}{\left(2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{1+\epsilon}}$
for all ${\vec{x}},{\vec{y}}\in\mathbb{R}^{n}$;

  2. (ii)

$\left|S_{k}({\vec{x}},{\vec{y}})-S_{k}({\vec{x}}^{\prime},{\vec{y}})\right|\leq
C\left(\frac{C_{\rho}\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|^{n}}{2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}}\right)^{\zeta}\frac{2^{-k\epsilon}}{\left(2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)^{1+\epsilon}}$
for all triples
$({\vec{x}},{\vec{x}}^{\prime},{\vec{y}})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{n}$
which satisfy

$C_{\rho}\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|^{n}\leq
C_{A}\left(2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right);$
(A.2)

  3. (iii)

$\int_{\mathbb{R}^{n}}S_{k}({\vec{x}},{\vec{y}})d{\vec{y}}=1$ for all
${\vec{x}}\in\mathbb{R}^{n}$.

Moreover, we say that the AtI satisfies the _double Lipschitz condition_ if
there exist a triple $(\tilde{C},\tilde{C}_{A},\zeta)$ of positive constants
satisfying

$\tilde{C}_{A}<\frac{1}{2},$ (A.3)

such that for all $k\in\mathbb{Z}$

$\displaystyle\left|S_{k}({\vec{x}},{\vec{y}})-S_{k}({\vec{x}}^{\prime},{\vec{y}})-S_{k}({\vec{x}},{\vec{y}}^{\prime})+S_{k}({\vec{x}}^{\prime},{\vec{y}}^{\prime})\right|$
(A.4) $\displaystyle\leq$
$\displaystyle\tilde{C}\left(\frac{C_{\rho}\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|^{n}}{2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}}\right)^{\zeta}\left(\frac{C_{\rho}\left\|{\vec{y}}-{\vec{y}}^{\prime}\right\|^{n}}{2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}}\right)^{\zeta}\frac{2^{-k\epsilon}}{(2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n})^{1+\epsilon}}$

for all quadruples
$({\vec{x}},{\vec{x}}^{\prime},{\vec{y}},{\vec{y}}^{\prime})\in\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{n}\times\mathbb{R}^{n}$
which satisfy

$C_{\rho}\max\left\\{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|^{n},\left\|{\vec{y}}-{\vec{y}}^{\prime}\right\|^{n}\right\\}\leq\tilde{C}_{A}\left(2^{-k}+C_{\rho}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right).$
(A.5)

The conditions item (ii) and Equation A.5 are essential for our analysis. We
characterize now geometric properties of these constrained sets:

######  Lemma A.1.

  * Let $C_{\rho}=1$, $C_{A}=2^{-n}$ and $\tilde{C}_{A}=3^{-n}$.

  * •

Then set of triples $({\vec{x}},{\vec{x}}^{\prime},{\vec{y}})$ which satisfy
Equation A.2 and for which $\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\geq 2^{-k}$
and all $t\in[0,1]$ satisfy

$\left\|{\vec{x}}+t({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}\right\|^{n}\geq
2^{-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-2^{-n}2^{-k}.$ (A.6)

  * •

The set of quadrupels
$({\vec{x}},{\vec{x}}^{\prime},{\vec{y}},{\vec{y}}^{\prime})$ which satisfy
Equation A.5 and for which $\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\geq 2^{-k}$
satisfy

$\left\|{\vec{x}}+t_{\vec{x}}({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}-t_{\vec{y}}({\vec{y}}^{\prime}-{\vec{y}})\right\|^{n}\geq
3^{-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-3^{-n}2^{1-k}$ (A.7)

for all $t_{\vec{x}},t_{\vec{y}}\in[0,1]$.

######  Proof.

  * •

With the concrete choice of parameters $C_{A}$, $C_{\rho}$ Equation A.2 reads
as follows

$\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|^{n}\leq
2^{-n}\left(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right).$ (A.8)

Since we assume that $\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\geq 2^{-k}$ it
follows from Equation A.8 that

$\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|\leq
2^{-1}\left\|{\vec{x}}-{\vec{y}}\right\|.$

In particular
$\left\|{\vec{x}}-{\vec{y}}\right\|-\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|\geq
0$.

We apply Jensen’s inequality, which states that for $a,b\geq 0$

$a^{n}+b^{n}\geq 2^{1-n}(a+b)^{n}.$ (A.9)

We use $a=\left\|{\vec{x}}+t({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}\right\|$
and $b=\left\|t({\vec{x}}^{\prime}-{\vec{x}})\right\|$, which then (along with
the triangle inequality) gives

$\left\|{\vec{x}}+t({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}\right\|^{n}+\left\|t({\vec{x}}^{\prime}-{\vec{x}})\right\|^{n}\geq
2^{1-n}\left(\left\|{\vec{x}}-{\vec{y}}\right\|\right)^{n}.$

In other words, it follows from Equation A.8 that

$\displaystyle\left\|{\vec{x}}+t({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}\right\|^{n}$
$\displaystyle\geq
2^{1-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-t^{n}\left\|{\vec{x}}^{\prime}-{\vec{x}}\right\|^{n}$
$\displaystyle\geq
2^{1-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-\left\|{\vec{x}}^{\prime}-{\vec{x}}\right\|^{n}$
$\displaystyle\geq
2^{1-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-2^{-n}\left(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)$
$\displaystyle=2^{-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-2^{-n}2^{-k}.$

  * •

With the concrete choice of parameters $\tilde{C}_{A}$, $C_{\rho}$ Equation
A.5 reads as follows

$\max\left\\{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|^{n},\left\|{\vec{y}}-{\vec{y}}^{\prime}\right\|^{n}\right\\}\leq
3^{-n}\left(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right).$ (A.10)

Since we assume that $\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\geq 2^{-k}$ it
follows from Equation A.10 that

$\max\left\\{\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|,\left\|{\vec{y}}-{\vec{y}}^{\prime}\right\|\right\\}\leq
3^{-1}\left\|{\vec{x}}-{\vec{y}}\right\|.$

This in particular shows that

$\left\|{\vec{x}}-{\vec{y}}\right\|-\left\|{\vec{x}}-{\vec{x}}^{\prime}\right\|-\left\|{\vec{y}}-{\vec{y}}^{\prime}\right\|\geq
0.$

We apply Jensen’s inequality, which states that for $a,b,c\geq 0$

$a^{n}+b^{n}+c^{n}\geq 3^{1-n}(a+b+c)^{n}.$ (A.11)

We use
$a=\left\|{\vec{x}}+t_{\vec{x}}({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}-t_{\vec{y}}({\vec{y}}^{\prime}-{\vec{y}})\right\|$,
$b=\left\|t_{\vec{x}}({\vec{x}}^{\prime}-{\vec{x}})\right\|$ and
$c=\left\|t_{\vec{y}}({\vec{y}}^{\prime}-{\vec{y}})\right\|$, which then
(along with the triangle inequality) gives

$\left\|{\vec{x}}+t_{\vec{x}}({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}-t_{\vec{y}}({\vec{y}}^{\prime}-{\vec{y}})\right\|^{n}+\left\|t_{\vec{x}}({\vec{x}}^{\prime}-{\vec{x}})\right\|^{n}+\left\|t_{\vec{y}}({\vec{y}}^{\prime}-{\vec{y}})\right\|^{n}\geq
3^{1-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}.$

In other words, it follows from Equation A.10 that

$\displaystyle\left\|{\vec{x}}+t_{\vec{x}}({\vec{x}}^{\prime}-{\vec{x}})-{\vec{y}}-t_{\vec{y}}({\vec{y}}^{\prime}-{\vec{y}})\right\|^{n}$
$\displaystyle\geq
3^{1-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-t_{\vec{x}}^{n}\left\|{\vec{x}}^{\prime}-{\vec{x}}\right\|^{n}-t_{\vec{y}}^{n}\left\|{\vec{y}}^{\prime}-{\vec{y}}\right\|^{n}$
$\displaystyle\geq
3^{1-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-\left\|{\vec{x}}^{\prime}-{\vec{x}}\right\|^{n}-\left\|{\vec{y}}^{\prime}-{\vec{y}}\right\|^{n}$
$\displaystyle\geq
3^{1-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-3^{-n}2\left(2^{-k}+\left\|{\vec{x}}-{\vec{y}}\right\|^{n}\right)$
$\displaystyle=3^{-n}\left\|{\vec{x}}-{\vec{y}}\right\|^{n}-3^{-n}2^{1-k}.$

$\square$

The approximation to the identity in Appendix A can be used to construct
_wavelet frames_ that can approximate arbitrary functions in
$\mathcal{L}^{1}(\mathbb{R}^{n})$, as shown in the theorem below.

######  Remark 5.

When $\left\|{\vec{x}}-{\vec{y}}\right\|^{n}<2^{-k}$, Equation A.6 also holds
since the right hand side of Equation A.6 is negative, so this inequality is
trivial.

######  Theorem  ([29]).

Let $(S_{k}:\mathbb{R}^{n}\times\mathbb{R}^{n}\to\mathbb{R})_{k\in\mathbb{Z}}$
be a symmetric AtI which satisfies the double Lipschitz condition (see
Equation A.4). Let

$\psi_{k,{\vec{y}}}({\vec{x}}):=2^{-k/2}\left(S_{k}({\vec{x}},{\vec{y}})-S_{k-1}({\vec{x}},{\vec{y}})\right)\text{
for all }{\vec{x}},{\vec{y}}\in\mathbb{R}^{n}\text{ and }k\in\mathbb{Z}.$
(A.12)

Then the set of functions

$\mathcal{W}:=\left\\{{\vec{x}}\to\psi_{k,\vec{b}}({\vec{x}}):k\in\mathbb{Z},\vec{b}\in
2^{-k/n}\mathbb{Z}^{n}\right\\},$ (A.13)

is a frame and for every function $f\in\mathcal{L}^{1}(\mathbb{R}^{n})$ there
exists a linear combination of $N$ elements of $\mathcal{W}$, denoted by
$f_{N}$, satisfying

$\left\|f-f_{N}\right\|_{L^{2}}\leq\left\|f\right\|_{\mathcal{L}^{1}}(N+1)^{-1/2}.$
(A.14)

### Acknowledgements

This research was funded in whole, or in part, by the Austrian Science Fund
(FWF) 10.55776/P34981 (OS & LF) – New Inverse Problems of Super-Resolved
Microscopy (NIPSUM), SFB 10.55776/F68 (OS) “Tomography Across the Scales”,
project F6807-N36 (Tomography with Uncertainties), and 10.55776/T1160 (CS)
“Photoacoustic Tomography: Analysis and Numerics”. For open access purposes,
the author has applied a CC BY public copyright license to any author-accepted
manuscript version arising from this submission. The financial support by the
Austrian Federal Ministry for Digital and Economic Affairs, the National
Foundation for Research, Technology and Development and the Christian Doppler
Research Association is gratefully acknowledged.

The authors would like to thank some referees for their valuable suggestions
and their patience.

## References

## References

  * [1] A.. Barron  “Universal approximation bounds for superpositions of a sigmoidal function”  In _IEEE Transactions on Information Theory_ 39.3, 1993, pp. 930–945  DOI: 10.1109/18.256500
  * [2] A.. Barron, A. Cohen, W. Dahmen and R.. DeVore  “Approximation and learning by greedy algorithms”  In _Annals of Statistics_ 36.1, 2008  DOI: 10.1214/009053607000000631
  * [3] M.. Buhmann  “Radial Basis Functions”, 2003  DOI: 10.1017/cbo9780511543241
  * [4] C.K. Chui  “An Introduction to Wavelets”  Academic Press, 1992
  * [5] G. Cybenko  “Approximation by superpositions of a sigmoidal function”  In _Mathematics of Control, Signals, and Systems_ 2.4, 1989, pp. 303–314  DOI: 10.1007/bf02551274
  * [6] I. Daubechies  “Ten Lectures on Wavelets”  Philadelphia, PA: SIAM, 1992  DOI: 10.1137/1.9781611970104
  * [7] D. Deng and Y. Han  “Harmonic Analysis on Spaces of Homogeneous Type”  Springer Berlin Heidelberg, 2009  DOI: 10.1007/978-3-540-88745-4
  * [8] P. Deuflhard and A. Hohmann  “Numerical Analysis. A First Course in Scientific Computation” Transl. from the German by F.A. Potra and F. Schulz  Berlin: De Gruyter, 1991
  * [9] J. Dugundji  “Topology” Reprinting of the 1966 original  AllynBacon, Inc., 1978
  * [10] F. Fan, J. Xiong and G. Wang  “Universal approximation with quadratic deep networks”  In _Neural Networks_ 124, 2020, pp. 383–392  DOI: 10.1016/j.neunet.2020.01.007
  * [11] E. Gelenbe, Zhi-Wong Mao and Yan-Da Li  “Approximation by random networks with bounded number of layers”  In _Neural Networks for Signal Processing IX: Proceedings of the 1999 IEEE Signal Processing Society Workshop (Cat. No.98TH8468)_ , 1999  DOI: 10.1109/nnsp.1999.788135
  * [12] A. Graps  “An introduction to wavelets”  In _IEEE Computational Science and Engineering_ 2.2, 1995, pp. 50–61  DOI: 10.1109/99.388960
  * [13] B. Hammer  “Learning with Recurrent Neural Networks”, Lecture Notes in Control and Information Sciences  Springer London, 2000  URL: https://books.google.li/books?id=8IjKhLs8siwC
  * [14] K. Hornik, M. Stinchcombe and H. White  “Multilayer feedforward networks are universal approximators”  In _Neural Networks_ 2.5, 1989, pp. 359–366  DOI: 10.1016/0893-6080(89)90020-8
  * [15] B. Igelnik and Yoh-Han Pao  “Stochastic choice of basis functions in adaptive function approximation and the functional-link net”  In _IEEE Transactions on Neural Networks_ 6.6, 1995, pp. 1320–1329  DOI: 10.1109/72.471375
  * [16] J.. Kelley  “General Topology”  Toronto-New York-London: D. Van Nostrand Company, 1955
  * [17] A. Lamperski  “Neural Network Independence Properties with Applications to Adaptive Control”  In _2022 IEEE 61st Conference on Decision and Control (CDC)_ , 2022  DOI: 10.1109/cdc51059.2022.9992994
  * [18] M. Leshno, V.. Lin, A. Pinkus and S. Schocken  “Multilayer feedforward networks with a nonpolynomial activation function can approximate any function”  In _Neural Networks_ 6.6, 1993, pp. 861–867  DOI: 10.1016/s0893-6080(05)80131-5
  * [19] A.K. Louis, P. Maass and A. Rieder  “Wavelets. Theorie und Anwendungen”  Stuttgart: Teubner, 1998
  * [20] O. Manita et al.  “Universal Approximation in Dropout Neural Networks”  In _Journal of Machine Learning Research_ 23.19, 2022, pp. 1–46  URL: http://jmlr.org/papers/v23/20-1433.html
  * [21] H.. Mhaskar  “Approximation properties of a multilayered feedforward artificial neural network”  In _Advances in Computational Mathematics_ 1.1 Springer US, 1993, pp. 61–80  DOI: 10.1007/bf02070821
  * [22] “Generalized inverses and applications”  In _Proceedings of an Advanced Seminar sponsored by the Mathematics Research Center at the University of Wisconsin, Madison, Wis., October 8-10, 1973_ New York: Academic Press [Harcourt Brace Jovanovich Publishers], 1976, pp. xiv+1054
  * [23] F. Natterer  “Regularisierung schlecht gestellter Probleme durch Projektionsverfahren”  In _Numerische Mathematik_ 28.3, 1977, pp. 329–341  DOI: 10.1007/bf01389972
  * [24] D. Obmann, J. Schwab and M. Haltmeier  “Deep synthesis network for regularizing inverse problems”  In _Inverse Problems_ 37.1, 2021, pp. 015005  DOI: 10.1088/1361-6420/abc7cd
  * [25] Y.-H. Pao, G.-H. Park and D.. Sobajic  “Learning and generalization characteristics of the random vector functional-link net”  In _Neurocomputing_ 6.2, 1994, pp. 163–180  DOI: 10.1016/0925-2312(94)90053-1
  * [26] A. Pinkus  “Approximation theory of the MLP model in neural networks”  In _Acta Numerica_ 8, 1999, pp. 143–195  DOI: 10.1017/s0962492900002919
  * [27] A.. Schäfer and H.-G. Zimmermann  “Recurrent Neural Networks are universal approximators”  In _International Journal of Neural Systems_ 17.4, 2007, pp. 253–263  DOI: 10.1142/s0129065707001111
  * [28] O. Scherzer, B. Hofmann and Z. Nashed  “Gauss–Newton method for solving linear inverse problems with neural network coders”  In _Sampling Theory, Signal Processing, and Data Analysis_ 21.2, 2023  DOI: 10.1007/s43670-023-00066-6
  * [29] U. Shaham, A. Cloninger and R.. Coifman  “Provable approximation properties for deep neural networks”  In _Applied and Computational Harmonic Analysis_ 44.3, 2018, pp. 537–557  DOI: 10.1016/j.acha.2016.04.003
  * [30] L.. Shepp and B.. Logan  “The Fourier reconstruction of a head section”  In _IEEE Transactions on Nuclear Science_ 21.3, 1974, pp. 21–43  DOI: 10.1109/tns.1974.6499235
  * [31] J.. Siegel and J. Xu  “Characterization of the Variation Spaces Corresponding to Shallow Neural Networks”  In _Constructive Approximation_ 57.3, 2023, pp. 1109–1132  DOI: 10.1007/s00365-023-09626-4
  * [32] J.. Siegel and J. Xu  “Sharp Bounds on the Approximation Rates, Metric Entropy, and n-Widths of Shallow Neural Networks”  In _Foundations of Computational Mathematics_ , 2022  DOI: 10.1007/s10208-022-09595-3
  * [33] N. Tsapanos, A. Tefas, N. Nikolaidis and I. Pitas  “Neurons With Paraboloid Decision Boundaries for Improved Neural Network Classification Performance”  In _IEEE Transactions on Neural Networks and Learning Systems_ 30.1, 2019, pp. 284–294  DOI: 10.1109/tnnls.2018.2839655
  * [34] S Wager, S Wang and P Liang  “Dropout Training as Adaptive Regularization”  In _Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1_ Curran Associates Inc., 2013, pp. 351–359
  * [35] White  “An additional hidden unit test for neglected nonlinearity in multilayer feedforward networks”  In _International Joint Conference on Neural Networks_ , 1989  DOI: 10.1109/ijcnn.1989.118281
  * [36] D.-X. Zhou  “Deep distributed convolutional neural networks: Universality”  In _Analysis and Applications_ 16.6, 2018, pp. 895–919  DOI: 10.1142/s0219530518500124
  * [37] D.-X. Zhou  “Universality of deep convolutional neural networks”  In _Applied and Computational Harmonic Analysis_ 48.2, 2020, pp. 787–794  DOI: 10.1016/j.acha.2019.06.004


explore some of these questions in future research.

There is still much work to do with general continuous stability, as well.
What can we learn by studying measured laminations of other surfaces? For
example, can we connect a continuous type $\mathbb{D}$ quiver to measured
laminations of the punctured (Poincaré) disk? In the present paper, we
consider stability conditions in the sense of King. What about other kinds of
stability conditions? Furthermore, can the connections between stability
conditions and moduli spaces be generalized to the continuous case?

## References

  * [1] S. Abeasis.  Codimension 1 orbits and semi-invariants for the representations of an oriented graph of type $A_{n}$.  Transactions of the American Mathematical Society, 282(2):463–485, 1984.
  * [2] S. Asai.  The wall-chamber structures of the real Grothendieck groups.  Adv. Math., 381, 2021.
  * [3] M. Auslander, M. I. Platzeck, and I. Reiten.  Coxeter functors without diagrams.  Transactions of the American Mathematical Society, 250:1–46, 1979\.
  * [4] M. B. Botnan and W. Crawley-Boevey.  Decomposition of persistence modules.  Proc. Amer. Math. Soc., 148(11):4581–4596, 2020.
  * [5] A. B. Buan, B. R. Marsh, M. Reineke, I. Reiten, and G. Todorov.  Tilting theory and cluster combinatorics.  Advances in mathematics, 204(2):572–618, 2006.
  * [6] T. Büstle, D. Smith, and H. Treffinger.  Wall and chamber structure for finite-dimensional algebras.  Adv. Math., 354, 2019.
  * [7] P. Caldero and F. Chapoton.  Cluster algebras as hall algebras of quiver representations.  Commentarii Mathematici Helvetici, 81(3):595–616, 2006.
  * [8] S. Fomin and A. Zelevinsky.  Cluster algebras I: foundations.  Journal of the American mathematical society, 15(2):497–529, 2002\.
  * [9] K. Igusa.  Linearity of stability conditions.  Communications in Algebra, 48(4):1671–1696, 2020.
  * [10] K. Igusa, J. D. Rock, and G. Todorov.  Continuous quivers of type $A$ (I) foundations.  Rendiconti del Circolo Matematico di Palermo Series 2, 2022.
  * [11] K. Igusa, J. D. Rock, and G. Todorov.  Continuous quivers of type $A$ (III) embeddings of cluster theories.  Nagoya Mathematical Journal, 2022.
  * [12] K. Igusa and G. Todorov.  Continuous cluster categories I.  Algebras and Reresentation Theory, 2015.
  * [13] A. D. King.  Moduli of representations of finite dimensional algebras.  QJ Math, 45(2):515–530, 1994.
  * [14] Y. Liu and M. Zhao.  Reflection functors for continuous quivers of type a.  arXiv:2208.07112 [math.RT], 2022.  Preprint.
  * [15] R. Maresca.  Five lectures on cluster theory.  arXiv:2210.05717 [math.RT], 2022.  Preprint.
  * [16] J. D. Rock.  Continuous quivers of type $A$ (II).  arXiv:1910.04140 [math.RT], 2019.  Preprint.
  * [17] J. D. Rock.  Continuous quivers of type $A$ (IV).  Algebras and Representation Theory, 2022.


unitaries for each dimension $j=1,2,\cdots,D$, i.e.

$\displaystyle S_{f}\ket{{\bf 0}}\bra{{\bf
0}}S_{f}^{\dagger}=\bigotimes_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}\beta_{i_{j}}U_{i_{j}},\quad\textnormal{where
$U_{i_{j}}$ are unitary operators}.$ (90)

The normalized state is

$\displaystyle\ket{\psi}$
$\displaystyle=\bigg{(}\sum_{j_{1}=0}^{n_{m}-1}\sum_{j_{2}=0}^{n_{m}-1}\cdots\sum_{j_{D}=0}^{n_{m}-1}\mathbb{P}^{2}[X_{1}(t)=x_{j_{1}},X_{2}(t)=x_{j_{2}},\cdots,X_{D}(t)=x_{j_{D}}]\bigg{)}^{-1/2}\ket{\tilde{\psi}}$
$\displaystyle=\bigg{(}\sum_{j_{1}=0}^{n_{m}-1}\sum_{j_{2}=0}^{n_{m}-1}\cdots\sum_{j_{D}=0}^{n_{m}-1}\mathbb{P}^{2}_{j_{1},j_{2},\cdots,j_{D}}\bigg{)}^{-1/2}\ket{\tilde{\psi}}.$
(91)

The error $\varepsilon^{\prime}$ is defined as the error of the expectation
value of each term in a state $\ket{\psi}$. This implies that the estimated
expectation value of each term $\tilde{u}_{i_{1},i_{2},\cdots,i_{D}}$
satisfies

$\displaystyle\bigg{|}\tilde{u}_{i_{1},i_{2},\cdots,i_{D}}-\bra{\psi}\bigotimes_{j=1}^{D}U_{i_{j}}\ket{\psi}\bigg{|}\leq\varepsilon^{\prime}$
(92)

The error in the linear combination of expectation values is determined using
(92)

$\displaystyle\bigg{|}\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}\beta_{i_{j}}\tilde{u}_{i_{1},i_{2},\cdots,i_{D}}-\bra{\psi}\bigotimes_{j=1}^{D}\sum_{i=1}^{N_{U_{j}}}\beta_{i_{j}}U_{i_{j}}\ket{\psi}\bigg{|}$
$\displaystyle=\bigg{|}\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}\beta_{i_{j}}(\tilde{u}_{i_{1},i_{2},\cdots,i_{D}}-\bra{\psi}\bigotimes_{j=1}^{D}U_{i_{j}}\ket{\psi})\bigg{|}$
$\displaystyle\leq\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}\bigg{|}\beta_{i_{j}}(\tilde{u}_{i_{1},i_{2},\cdots,i_{D}}-\bra{\psi}\bigotimes_{j=1}^{D}U_{i_{j}}\ket{\psi})\bigg{|}$
$\displaystyle\leq\varepsilon^{\prime}\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}|\beta_{i_{j}}|.$
(93)

If we write $\tilde{E}$ for the estimation of the expectation $E$, then by the
use of (G) and (G) we arrive at

$\displaystyle|\tilde{E}-E|$
$\displaystyle\leq\bigg{(}\sum_{j_{1}=0}^{n_{m}-1}\sum_{j_{2}=0}^{n_{m}-1}\cdots\sum_{j_{D}=0}^{n_{m}-1}\mathbb{P}^{2}_{j_{1},j_{2},\cdots,j_{D}}\bigg{)}\frac{\varepsilon^{\prime}}{\tilde{E}+E}\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}|\beta_{i_{j}}|$
$\displaystyle\sim\bigg{(}\sum_{j_{1}=0}^{n_{m}-1}\sum_{j_{2}=0}^{n_{m}-1}\cdots\sum_{j_{D}=0}^{n_{m}-1}\mathbb{P}^{2}_{j_{1},j_{2},\cdots,j_{D}}\bigg{)}\frac{\varepsilon^{\prime}}{2E}\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}|\beta_{i_{j}}|.$
(94)

Therefore, in order to obtain an upper bound for $\varepsilon$ in the
expectation $E$, the error $\varepsilon^{\prime}$ must be such that

$\displaystyle\varepsilon^{\prime}\leq\frac{2E}{(\sum_{j_{1}=0}^{n_{m}-1}\sum_{j_{2}=0}^{n_{m}-1}\cdots\sum_{j_{D}=0}^{n_{m}-1}\mathbb{P}^{2}_{j_{1},j_{2},\cdots,j_{D}})\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}|\beta_{i_{j}}|}\varepsilon=:\gamma\varepsilon.$
(95)

In terms of the Hadamard test circuit above, one requires
$\mathcal{O}(1/\varepsilon^{\prime 2})$ measurements to bound the error in the
expectation value to $\varepsilon^{\prime}$. Up to the preparation of the
state, the depth of the unitaries in the circuit is $\mathcal{O}(1)$. The
tradeoff with QPE is that the same accuracy in the expectation is
$\mathcal{O}(\log 1/\varepsilon^{\prime})$ but the depth is now
$\mathcal{O}(1/\varepsilon^{\prime})$. With the $L$th order Taylor
approximation, one has that $N_{U_{j}}=\mathcal{O}(d^{2}n^{2L+2})$ for
$j=1,2,\cdots,D$, where $d$ was the number of intervals. Moreover, the total
number of measurements is the number of measurements for each term affected by
a multiplication by $N_{U_{j}}$. Effectively, this yields that the total
number of measurements by Hadamard test is
$\mathcal{O}((\prod_{j=1}^{D}d^{2}n^{2L+2})/(\gamma\varepsilon^{2}))$, whereas
using QPE, one would need
$\mathcal{O}((\prod_{j=1}^{D}d^{2}n^{2L+2})\log(1/\gamma\varepsilon))$, but
QPE needs $\mathcal{O}(1/\gamma\varepsilon)$ many $U$ gates.

Lastly, we need the bound for $\gamma$ from (95). Since
$\sum_{j_{1}=0}^{n_{m}-1}\sum_{j_{2}=0}^{n_{m}-1}\cdots\sum_{j_{D}=0}^{n_{m}-1}\mathbb{P}^{2}_{j_{1},j_{2},\cdots,j_{D}}\leq
1$, we see that $\gamma\geq
2E/(\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}|\beta_{i_{j}}|)$. Next, using
(69) we get

$\displaystyle\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}|\beta_{i_{j}}|=2^{D}\prod_{j=1}^{D}\sum_{\ell_{j},\ell^{\prime}_{j}}|\xi_{\ell_{j}}\xi_{\ell^{\prime}_{j}}^{*}|=2^{D}\prod_{j=1}^{D}\sum_{\ell_{j},\ell^{\prime}_{j}}|\xi_{\ell_{j}}||\xi_{\ell^{\prime}_{j}}|.$
(96)

Moreover, from (30) we see that
$(D(n))^{|\beta|}=\mathcal{O}(2^{n|\beta|})=\mathcal{O}(x_{\max}^{|\beta|})$.
For an interval in a given dimension $S_{\chi\alpha_{k}}$ is a linear
combination of operators $S_{\chi_{\ell}^{\alpha}}$, therefore
$|S_{\chi\alpha_{k}}|=\mathcal{O}(2^{(k_{a_{i}}-1)/2})=\mathcal{O}(x_{\max}^{1/2})$
since $k_{a_{i}}$ was such that $0<k_{a_{i}}\leq\lfloor n/D\rfloor$. This
implies that the largest $|\xi_{\ell_{j}}|$ is as large
$[\max_{k_{j}}\max_{|\beta|}|f_{j,k_{j},\beta}|x_{\max}^{|\beta|}]\mathcal{O}(x_{\max}^{1/2})$.
Therefore, we get

$\displaystyle\prod_{j=1}^{D}\sum_{i_{j}=1}^{N_{U_{j}}}|\beta_{i_{j}}|=\mathcal{O}\bigg{(}\prod_{j=1}^{D}[\max_{k_{j}}\max_{|\beta|}|f_{j,k_{j},|\beta|}|x_{\max}^{|\beta|}]^{2}d^{2}n^{2L+2}x_{\max}\bigg{)},$
(97)

which is the last bound we needed for $\gamma$.

The operator $S_{f}\ket{{\bf 0}}\bra{{\bf 0}}S_{f}^{\dagger}$ will be the sum
of $\mathcal{O}(d^{2D}n^{2D(L+1)})$ unitaries and each $Q_{k}$ will be
composed of $\mathcal{O}(n^{4})$ gates. The number of gates will grow
exponentially with the dimensions and this is a universal problem in many
algorithms, such as the use of QAE when computing moments when the arguments
of the function are multidimensional. In such cases one needs exponentially
many resources to build a multidimensional oracle.

As $L$ grows, $\varepsilon^{-\tfrac{2}{D(L+1)}}$ from (G) becomes smaller
while $d^{2D}n^{D(2L+2)}$ grows larger. This means that the number of
unitaries is not monotonic with respect to $L$ and thus there could be an
optimal $L$ for the desired accuracy. In [12], the authors point out that the
expectation values of those unitaries could be computed in parallel with a
second quantum device.

##  Appendix H Future work

###  H.1 Stochastic volatility and stochastic interest rates

A key weakness in the Black-Scholes is that the volatility term $\sigma$ is
constant. One can go around this problem by defining two SDEs: geometric
Brownian motion for the underlying stock $S$

$\displaystyle dS_{t}=\mu S_{t}dt+\sigma_{t}S_{t}dW_{1,t},$ (98)

where $dW_{1}$ is standard Brownian motion, as well as another SDE for
$\sigma$

$\displaystyle d\sigma_{t}=p(S,\sigma,t)dt+q(S,\sigma,t)dW_{2,t},$ (99)

where $dW_{2}$ is another Brownian motion whose correlation with $dW_{1}$ is
given $\rho$, i.e. $dW_{1}dW_{2}=\rho dt$. Let $V(S,\sigma,t)$ be the value of
an option on the underlying $S$ at time $t$ and with stochastic volatility
$\sigma$. Portfolio replication coupled with Itô’s lemma and non-arbitrage
arguments yields the partial differential equation

$\displaystyle\frac{\partial V}{\partial t}+rS\frac{\partial V}{\partial
S}+\frac{1}{2}\sigma^{2}S^{2}\frac{\partial^{2}V}{\partial
S^{2}}+(p-\lambda)q\frac{\partial
V}{\partial\sigma}+\frac{1}{2}q^{2}\frac{\partial^{2}V}{\partial\sigma^{2}}+\rho\sigma
Sq\frac{\partial^{2}V}{\partial S\partial\sigma}-rV=0.$ (100)

Here $\lambda(S,\sigma,t)$ is a universal function that is used in portfolio
replication to ensure that options are only dependent on the variables
$S,\sigma$ and $t$. The function $\lambda$ is called the market price of
volatility risk. Comparing (100) with Black-Scholes

$\displaystyle\frac{\partial V}{\partial t}+rS\frac{\partial V}{\partial
S}+\frac{1}{2}\sigma^{2}S^{2}\frac{\partial^{2}V}{\partial S^{2}}-rV=0,$ (101)

we see the appearance of the additional linear and second order partial
derivatives with respect to $\sigma$ coming from (99) as well as the presence
of the mixed term in $S$ and $\sigma$ due to the correlation $\rho$ of the two
Brownian motions $dW_{1}$ and $dW_{2}$. Note that if the volatility were to be
constant, then (100) would reduce to (101). Different choices of $p$ and $q$
lead to different named models, e.g.

  * •

Hull and White: $d(\sigma^{2})=a(b-\sigma^{2})dt+c\sigma^{2}dW_{2}$,

  * •

Square-root model / Heston:
$d(\sigma^{2})=(a-b\sigma^{2})dt+c\sqrt{\sigma^{2}}dW_{2}$,

  * •

3/2 model: $d(\sigma^{2})=(a\sigma^{2}-b\sigma^{4})dt+c\sigma^{3/2}dW_{2}$,

  * •

Ornstein–Uhlenbeck: $d(\log\sigma^{2})=(a-b\log\sigma^{2})dt+cdW_{2}$.

see [35, p. 861]. Similar equations also exist for stochastic interest rates
[35].

###  H.2 American and decision-embedded options

The American option is also an involved one to price. Unlike in the European
set-up, the holder of an American option may exercise at any time prior and up
to expiration. The details of this set up can be found in [52,
$\mathsection$2]. We are dealing with our usual geometric Brownian motion (98)
as well as the additional SDE

$\displaystyle dX_{t}^{q}=q_{t}dS_{t}+\mu(X_{t}^{q}-q_{t}S_{t})dt,\quad
X_{0}^{q}=X_{0},$ (102)

where $q_{t}$ is the number of shares held at time $t$. The strategy of
$q_{t}$ is subject to the contractual constraint
$q_{t}\in[\alpha_{t},\beta_{t}]$, where $\alpha_{t}\leq\beta_{t}$. Financial
arguments lead us to the conditional expectation

$\displaystyle
V^{[\alpha,\beta]}(t,S_{t},X_{t}^{q})=\max_{q_{u}\in[\alpha,\beta]}e^{-r(T-t)}\mathbb{E}[\max(x_{T}^{q},0)\;|\;\mathcal{F}_{t}],\quad
t\in[0,T].$

These expectations arise naturally in stochastic optimal control and are
characterized by the corresponding Hamilton-Jacobi-Bellman equation

$\displaystyle-rV+\frac{\partial V}{\partial t}+rs\frac{\partial V}{\partial
s}$ $\displaystyle+\max_{q\in[\alpha,\beta]}\bigg{[}(\mu
x+qs(r-u))\frac{\partial V}{\partial
x}+\frac{1}{2}\sigma^{2}s^{2}\bigg{(}\frac{\partial^{2}V}{\partial
s^{2}}+2q\frac{\partial^{2}V}{\partial s\partial
x}+q^{2}\frac{\partial^{2}V}{\partial x^{2}}\bigg{)}\bigg{]}=0,$

with associated boundary condition $V(T,s,x)=\max(x,0)$. Note the typo in [52,
Eq. (2.4)]. To model the American option using (102), one sets $\mu=0$ and one
allows only one switch in $q_{t}$, either from 1 to 0 for the American call,
or from $-1$ to 0 for the American put.

###  H.3 The Poisson and wave equations

The heat equation is not the only candidate for this algorithm. In one of its
simplest forms the Poisson equation reads as follows

$\displaystyle\nabla^{2}u(x,y,z)=f(x,y,z),$

where $\nabla^{2}$ is the Cartesian Laplacian in three dimensions. Note the
similarity with the heat equation, except for the absence of the time
derivative. Itô’s lemma can be used [39, $\mathsection$4.1.1] to transform the
conditional expectation

$\displaystyle w({\bf
x})=\mathbb{E}\bigg{[}\int_{0}^{\infty}\exp\bigg{(}-\int_{0}^{s}c({\bf
X}_{\tau})d\tau\bigg{)}\;f({\bf X}_{s})\;|\;{\bf X}_{t}={\bf x}\bigg{]}$

arising from the vectorized SDE

$\displaystyle d{\bf X}_{t}=b({\bf X}_{t})dt+\sum_{j}\sigma_{ij}({\bf
X}_{t})dW_{t}^{j}$

into the solution of the PDE

$\displaystyle\sum_{i,j}\frac{1}{2}\Sigma_{ij}(x)\frac{\partial^{2}w}{\partial
x_{i}\partial x_{j}}+\sum_{j}b_{j}\frac{\partial w}{\partial x_{j}}-c({\bf
x})w=f({\bf x}).$

Here $\Sigma_{ij}=\sum_{k}\sigma_{ik}\sigma_{kj}$. Note the absence of $t$ in
$w$, as $w$ is now only a function of space ${\bf x}$.

Another venue would be to consider the wave or Klein-Gordon equations (or in
general, other type of hyperbolic differential equations). In its simplest
form the wave equation is written as

$\displaystyle\frac{\partial^{2}u}{\partial t^{2}}=c^{2}\nabla^{2}u(x,y,z).$
(103)

The time derivative is now of second order, unlike in the heat equation, which
was of first order. In these cases, other types of probability distributions
and Brownian motions need to be added, specially by considering jumps and
Poisson processes, see [53].

In these situations, different variational principles will be needed to
account for the different orders of the time derivative that appears in the
PDE. For example, when it comes to the wave equation (103), we will need a
varitational principle of the type

$\displaystyle\delta\;\bigg{|}\bigg{|}\frac{d^{2}}{dt^{2}}\ket{\tilde{v}(\bm{\theta}(t))}-\mathcal{O}(t)\ket{\tilde{v}(\bm{\theta}(t))}\bigg{|}\bigg{|},$

as opposed to (25). This procedure, along with more generalizations of the
time derivative and related differential operators, will be carried out in
subsequent research.