# A multivariate Riesz basis of ReLU neural networks

Cornelia Schneider111Friedrich-Alexander Universität Erlangen, Applied
Mathematics III, Cauerstr. 11, 91058 Erlangen, Germany. Email:
<EMAIL_ADDRESS>and Jan Vybíral222Department of Mathematics,
Faculty of Nuclear Sciences and Physical Engineering, Czech Technical
University, Trojanova 13, 12000 Praha, Czech Republic. Email:
<EMAIL_ADDRESS>The work of this author has been supported by the
grant P202/23/04720S of the Grant Agency of the Czech Republic

###### Abstract

We consider the trigonometric-like system of piecewise linear functions
introduced recently by Daubechies, DeVore, Foucart, Hanin, and Petrova. We
provide an alternative proof that this system forms a Riesz basis of
$L_{2}([0,1])$ based on the Gershgorin theorem. We also generalize this system
to higher dimensions $d>1$ by a construction, which avoids using (tensor)
products. As a consequence, the functions from the new Riesz basis of
$L_{2}([0,1]^{d})$ can be easily represented by neural networks. Moreover, the
Riesz constants of this system are independent of $d$, making it an attractive
building block regarding future multivariate analysis of neural networks.
Key Words: Riesz basis, Rectified Linear Unit (ReLU), artificial neural
networks, Euler product, Möbius function
MSC2020 Math Subject Classifications: 68T07, 42C15, 11A25.

##  1 Introduction

The last decades observed a tremendous success of artificial neural networks
in many machine learning tasks, including computer vision [16], speech
recognition [11], natural language processing [24], or games solutions [17,
21] to name just few. Despite their wide use, many of their properties are not
fully understood and many aspects of their great practical performance lack a
rigorous explanation. Without any doubt, a deeper insight into the theory of
artificial neural networks could boost their applicability even further.

In the last decade, a growing number of authors investigated why the deep
neural networks with a higher number of hidden layers approximate many
interesting functions more efficiently than the shallow neural networks (with
only one hidden layer) using the same number of parameters. We refer to [1, 7,
8, 10, 12, 18, 22, 25] for a number of mathematically rigorous results in this
direction.

One of the astonishing properties of artificial neural networks is, that they
can approximate extremely well also functions of many variables, which often
allows to avoid the curse of dimensionality [3, 9, 19]. The aim of this work
is to shed new light on the effectiveness of artificial neural networks for
the approximation of multivariate functions by constructing a new system of
functions, which forms a Riesz basis of $L_{2}([0,1]^{d})$ for every $d\geq
1$.

To state the result, we first recall the notion of a Riesz basis (which, in
turn, is a generalization of an orthonormal system and of an orthonormal
basis, cf. [6]).

######  Definition 1.1.

Let $H$ be a real Hilbert space. The (finite or infinite) sequence
$(x_{n})_{n}\subset H$ is called a Riesz sequence if there are two constants
$A,B>0$ such that

$A\sum_{n}\alpha_{n}^{2}\leq\left\|\sum_{n}\alpha_{n}x_{n}\right\|^{2}\leq
B\sum_{n}\alpha_{n}^{2}$ (1)

for every real square summable sequence $(\alpha_{n})_{n}$. If the closed span
of $(x_{n})_{n}$ is the whole space $H$, then we call it a Riesz basis.

The system, which we study in this paper, is a trigonometric-like basis, where
instead of $\cos$ and $\sin$ functions we use their piecewise linear
counterparts $\mathcal{C}$ and $\mathcal{S}$, which are defined as follows
(cf. Figure 1).

######  Definition 1.2.

  1. 1.

For $x\in[0,1]$, we define

${\mathcal{C}}(x)=4\left|x-\frac{1}{2}\right|-1=\begin{cases}1-4x,\
x\in[0,1/2),\\\ 4x-3,\ x\in[1/2,1]\end{cases}$

and

${\mathcal{S}}(x)=\left|2-4\left|x-\frac{1}{4}\right|\right|-1=\begin{cases}4x,\
&x\in[0,1/4),\\\ 2-4x,\ &x\in[1/4,3/4),\\\ 4x-4,&x\in[3/4,1].\end{cases}$

  2. 2.

For $x\in\mathbb{R}$, we extend this definition periodically, i.e.
$\mathcal{C}(x)=\mathcal{C}(x-\lfloor x\rfloor)$ and
$\mathcal{S}(x)=\mathcal{S}(x-\lfloor x\rfloor).$

  3. 3.

If $k\geq 1$ and $x\in\mathbb{R}$, we put $\mathcal{C}_{k}(x)=\mathcal{C}(kx)$
and $\mathcal{S}_{k}(x)=\mathcal{S}(kx).$

Figure 1: The plot of $\mathcal{C}$, $\mathcal{S}$, $\mathcal{C}_{2}$ and
$\mathcal{S}_{2}$.

These functions were introduced and studied in [7], where it was shown that
the system

${\overline{\mathcal{R}}}_{1}:=\\{1\\}\cup\\{\sqrt{3}\,\mathcal{C}_{k},\sqrt{3}\,\mathcal{S}_{k}:k\in\mathbb{N}\\}$
(2)

forms a Riesz basis of $L_{2}([0,1])$ with the constants $A=1/2$ and $B=3/2.$
Let us note that the factor $\sqrt{3}$ in (2) is simply a normalization
factor, which ensures that all the elements of ${\overline{\mathcal{R}}}_{1}$
have unit norm in $L_{2}([0,1])$. The proof given in [7] is implicitly
inspired by the method of analysis and synthesis operators, respectively, used
in the frame theory, cf. [13]. It is one of the aims of our paper (cf. Theorem
2.2) to provide an alternative proof, which first reduces (1) to the study of
spectral properties of the Gram matrix of ${\overline{\mathcal{R}}}_{1}$. The
result then follows from the Gershgorin circle theorem and some elementary
number theory (including Euler products and a certain Ramanujan’s formula).

The main advantage of (2) in contrast to the standard trigonometric system is,
that its elements can be easily identified by artificial neural networks with
the REctified Linear Unit (ReLU) activation function.

Figure 2: Graph of the $\operatorname{ReLU}$ function.

Let us recall, that if $t\in\mathbb{R}$, then the ReLU function is defined as
$\operatorname{ReLU}(t)=\max(0,t)$, cf. Figure 2. On vectors, it acts
component-wise

$\operatorname{ReLU}(x_{1},\dots,x_{n})=(\operatorname{ReLU}(x_{1}),\dots,\operatorname{ReLU}(x_{n})),\quad
x\in\mathbb{R}^{n}.$

If $W\geq 2$ and $L\geq 1$ are integer parameters, then we denote by
$\Upsilon^{W,L}$ the real-valued functions which can be represented by a
$\operatorname{ReLU}$ neural network of width $W$ and depth $L$, see
Definition 4.1 for a precise formulation. Then [7, Theorem 6.2] shows that
$\mathcal{C}_{j}$ and $\mathcal{S}_{j}$ (restricted to $[0,1]$) lie in
$\Upsilon^{W,L}$ for an arbitrary $W\geq 6$ and $L$ of the asymptotic order
$\log_{2}(j).$

The main aim of our work is to generalize the results of [7] to the
multivariate case. There are two crucial issues which prevent us from simply
taking the tensor products of the functions in ${\overline{\mathcal{R}}}_{1}$.
First, the product function $(x,y)\to x\cdot y$ can only be approximated by
the $\operatorname{ReLU}$ neural networks and, second, the ratio of the Riesz
constants $B$ and $A$ gets exponentially large when $d$ grows.

We propose a surprisingly simple and effective solution to these challenges.
We show that (cf. Theorem 3.3) the multivariate analogue of
${\overline{\mathcal{R}}}_{1}$

$\\{1\\}\cup\\{\sqrt{3}\,{\mathcal{C}}(\alpha\cdot
x):\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0\\}\cup\\{\sqrt{3}\,\mathcal{S}(\alpha\cdot
x):\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0\\},$ (3)

forms a Riesz basis of $L_{2}([0,1]^{d})$ for every $d\geq 1$ with the same
constants $A=1/2$ and $B=3/2$ as in the univariate case. Here,
$\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$ means that the first non-zero entry of
$\alpha=(\alpha_{1},\dots,\alpha_{d})\in\mathbb{Z}^{d}$ is positive. Finally,
we show in Section 4 that the functions from (3) can be exactly reproduced by
the $\operatorname{ReLU}$ neural networks of width $W$ and depth $L$ in
essentially the same way as in the univariate case, i.e., there is virtually
no price to pay when $d$ grows.

##  2 Univariate case

It was observed in [7, Section 6], that the system of piecewise linear
functions

$\\{\mathcal{C}_{k},\mathcal{S}_{k}:k\in\mathbb{N}\\},$ (4)

on one hand shares some nice properties with the trigonometric system and on
the other hand can be easily reproduced by artificial neural networks with the
$\operatorname{ReLU}$ activation function. The aim of this section is to
essentially reprove Proposition 6.1 of [7], which states that this system is a
Riesz basis of $L_{2}^{0}([0,1])$, the space of square integrable functions
with mean zero.

Although our proof shares some technical details with [7], its main structure
is different: In particular, we reduce the problem to spectral properties of
the corresponding Gram matrix and then apply the Gershgorin circle theorem.
Interestingly, by using some elementary number theory, we are able to
completely characterize the inner products of the $\mathcal{C}_{i}$ and/or
$\mathcal{S}_{j}$ functions. In contrast to [7], we complement (4) by adding
the constant function, which is orthogonal to all functions from (4).

We denote by $\gcd(i,j)$ the greatest common divisor of $i$ and $j$ and by
$\langle f,g\rangle=\int_{0}^{1}f(t)g(t)dt$ the standard inner product in
$L_{2}([0,1]).$

######  Lemma 2.1.

Let $i,j\in\mathbb{N}.$ Then

  1. 1.

$\langle\mathcal{C}_{i},\mathcal{S}_{j}\rangle=0$;

  2. 2.

$\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle=\langle\mathcal{S}_{i},\mathcal{S}_{j}\rangle=0$
if $i/\gcd(i,j)$ is odd and $j/\gcd(i,j)$ is even (or vice versa), i.e., if
the prime factorizations of $i$ and $j$ contain a different power of 2;

  3. 3.

If $i/\gcd(i,j)$ and $j/\gcd(i,j)$ are both odd, then

$3\cdot\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle=3\cdot|\langle{\mathcal{S}}_{i},{\mathcal{S}}_{j}\rangle|=\frac{\gcd(i,j)^{4}}{i^{2}\cdot
j^{2}}.$

Here, the sign of $\langle{\mathcal{S}}_{i},{\mathcal{S}}_{j}\rangle$ is
negative if, and only if, $(i+j)/(2\gcd(i,j))$ is even.

  4. 4.

In particular, we get
$\langle{\mathcal{C}}_{i},{\mathcal{C}}_{i}\rangle=\langle\mathcal{S}_{i},\mathcal{S}_{i}\rangle=1/3$
for all $i\in\mathbb{N}$.

###### Proof.

We transfer the proof to the Fourier side by exploiting the decomposition of
$\mathcal{C}_{i}$ and $\mathcal{S}_{j}$ into Fourier series, cf. [7, page
166]. Let

$c_{k}(x)=\sqrt{2}\cos(2\pi kx),\quad s_{k}(x)=\sqrt{2}\sin(2\pi kx),\quad
k\in\mathbb{N}_{0},\ x\in\mathbb{R}.$

Then a standard calculation reveals that

$\sqrt{3}\,{\mathcal{C}}_{k}=\mu\sum_{m\geq
0}\frac{1}{(2m+1)^{2}}c_{(2m+1)k}\quad\text{and}\quad\sqrt{3}\,{\mathcal{S}}_{k}=\mu\sum_{m\geq
0}\frac{(-1)^{m}}{(2m+1)^{2}}s_{(2m+1)k},$ (5)

where

$\mu^{2}\sum_{m\geq
0}\frac{1}{(2m+1)^{4}}=1,\quad\text{i.e.}\quad\mu^{2}\frac{\pi^{4}}{96}=1.$
(6)

Using (5), we immediately obtain that
$\langle\mathcal{C}_{i},\mathcal{S}_{j}\rangle=0$. Furthermore,

$\displaystyle 3\langle{{\mathcal{C}}_{i}},{{\mathcal{C}}_{j}}\rangle$
$\displaystyle=\sum_{m,n=0}^{\infty}\frac{\mu^{2}}{(2m+1)^{2}(2n+1)^{2}}\langle
c_{(2m+1)i},c_{(2n+1)j}\rangle$
$\displaystyle=\sum_{m,n=0}^{\infty}\frac{\mu^{2}}{(2m+1)^{2}(2n+1)^{2}}\delta_{(2m+1)i,(2n+1)j},$
(7)

where $\delta_{u,v}=1$ if $u=v$ and zero otherwise. To simplify (7), we have
to find for fixed $i,j\in\mathbb{N}$ all $m,n\in\mathbb{N}_{0}$ such that
$(2m+1)i=(2n+1)j$. First, we observe that if the prime factorizations of $i$
and $j$ contain a different power of two, then also $(2m+1)i$ and $(2n+1)j$
have a different power of two in their prime factorizations and therefore they
differ for all $m,n\in\mathbb{N}_{0}$. Consequently, (7) shows that
$3\langle{{\mathcal{C}}_{i}},{{\mathcal{C}}_{j}}\rangle=0$.

If the prime factorizations of $i$ and $j$ contain the same power of two, then
$i/\gcd(i,j)$ and $j/\gcd(i,j)$ are both odd. We denote $g=\gcd(i,j)$ and note
that $i/g$ and $j/g$ are coprime, i.e., that their greatest common divisor is
one. We then look for all pairs $(m,n)\in\mathbb{N}^{2}_{0}$, which solve the
equation

$(2m+1)\cdot g\cdot\frac{i}{g}=(2n+1)\cdot g\cdot\frac{j}{g}.$

All the solutions are obtained in the form

$2m+1=\frac{j}{g}\cdot(2l+1),\quad 2n+1=\frac{i}{g}\cdot(2l+1),\quad
l\in\mathbb{N}_{0}.$ (8)

We insert (8) into (7) and conclude that

$\displaystyle 3\langle{{\mathcal{C}}_{i}},{{\mathcal{C}}_{j}}\rangle$
$\displaystyle=\sum_{l=0}^{\infty}\frac{\mu^{2}}{\displaystyle\left(\frac{i}{g}(2l+1)\right)^{2}\cdot\left(\frac{j}{g}(2l+1)\right)^{2}}$
$\displaystyle=\mu^{2}\sum_{l=0}^{\infty}\frac{1}{(2l+1)^{4}}\cdot\frac{1}{(i/g)^{2}\cdot(j/g)^{2}}=\frac{1}{(i/g)^{2}\cdot(j/g)^{2}}.$

The calculation of $\langle\mathcal{S}_{i},\mathcal{S}_{j}\rangle$ can be
performed in a very similar way, one only needs to take care about the sign of
the inner product. In particular, instead of (7) we obtain

$3\langle{{\mathcal{S}}_{i}},{{\mathcal{S}}_{j}}\rangle=\sum_{m,n=0}^{\infty}\frac{\mu^{2}(-1)^{n+m}}{(2m+1)^{2}(2n+1)^{2}}\delta_{(2m+1)i,(2n+1)j},$

where $(-1)^{n+m}=-1$ if, and only if, $n+m=\frac{i+j}{2g}(2l+1)-1$ is odd.
Therefore, the sign is negative if, and only if, $\frac{i+j}{2g}$ even. ∎

Next, we combine Lemma 2.1 with the Gershgorin circle theorem and provide an
alternative proof of [7, Theorem 6.2], which we restate as follows.

######  Theorem 2.2.

The system
${\mathcal{R}}_{1}:=\\{1\\}\cup\\{\mathcal{C}_{k},\mathcal{S}_{k}:k\in\mathbb{N}\\}$
is a Riesz basis of $L_{2}([0,1])$.

Before we come to the proof, several remarks seem to be in order.

######  Remark 2.3.

  1. 1.

We will actually show, that the Riesz constants of the $L_{2}$-normalized
system
${\overline{\mathcal{R}}}_{1}:=\\{1\\}\cup\\{\sqrt{3}\,\mathcal{C}_{k},\sqrt{3}\,\mathcal{S}_{k}:k\in\mathbb{N}\\}$
can be chosen as $A=1/2$ and $B=3/2.$

  2. 2.

We divide the proof of Theorem 2.2 into several steps. In the first two steps,
we show that the truncated system
${\overline{\mathcal{R}}}_{1}^{N}:=\\{1\\}\cup\\{\sqrt{3}\,\mathcal{C}_{k},\sqrt{3}\,\mathcal{S}_{k}:k\leq
N\\}$ forms a Riesz sequence (i.e., that it satisfies (1)) with $A=1/2$ and
$B=3/2$ being independent of $N\in\mathbb{N}$. The first step reduces this
question to spectral properties of the Gram matrix of
${\overline{\mathcal{R}}}_{1}^{N}$ and in the second step we apply the
Gershgorin theorem to bound this spectrum. The third step describes how we
pass to the limit $N\to\infty$ to deduce that ${\overline{\mathcal{R}}}_{1}$
is also a Riesz sequence. Finally, the fourth step shows that
${\overline{\mathcal{R}}}_{1}$ is also a basis, i.e., that its closed linear
span is $L_{2}([0,1])$.

  3. 3.

Our proof shows that the spectrum of the Gram matrix of
${\overline{\mathcal{R}}}_{1}^{N}$ (for arbitrary $N\in\mathbb{N}$) is
contained in $[1/2,3/2].$ We leave it as an open problem to find out if these
bounds are actually optimal. Supported by numerical evidence (see Figure 3 for
details), our conjecture is that there is indeed some space for improvement.

Figure 3: The largest (left) and the smallest (right) eigenvalue of
$(\langle\mathcal{C}_{i},\mathcal{C}_{j}\rangle)_{i,j=1}^{N}$ for $1\leq N\leq
3\cdot 10^{4}$.

_Proof of Theorem 2.2: Step 1._
First we reformulate the definition of a (finite) Riesz sequence as an
eigenvalue problem of its Gram matrix. This reformulation is rather
straightforward and by no means new, see [15] or [26, Chapter 1.8]. Let $H$ be
a real Hilbert space and let $\\{x_{i}\\}_{i=1}^{N}\subset H$. Then, for every
$\alpha=(\alpha_{1},\dots,\alpha_{N})^{T}\in\mathbb{R}^{N}$

$\left\|\sum_{i=1}^{N}\alpha_{i}x_{i}\right\|^{2}=\sum_{i,j=1}^{N}\alpha_{i}\alpha_{j}\langle
x_{i},x_{j}\rangle=\alpha^{T}G\alpha,$

where $G=(g_{i,j})_{i,j=1}^{N}$ with $g_{i,j}=\langle x_{i},x_{j}\rangle$ is
the Gram matrix of $\\{x_{i}\\}_{i=1}^{N}$. Therefore, (1) is equivalent to
$A\alpha^{T}\alpha\leq\alpha^{T}G\alpha\leq B\alpha^{T}\alpha$ for every
$\alpha\in\mathbb{R}^{N}$ or simply to $\sigma(G)\subset[A,B].$ To show that
this is indeed true for a given Gram matrix $G$, we will use the Gershgorin
circle theorem [14, Theorem 6.1.1], which states that

$\sigma(G)\subset\bigcup_{i=1}^{N}\left[g_{i,i}-\sum_{j\not=i}|g_{i,j}|,g_{i,i}+\sum_{j\not=i}|g_{i,j}|\right].$

_Proof of Theorem 2.2: Step 2._
In this step, we show that
$\\{1\\}\cup\\{\sqrt{3}\,\mathcal{C}_{k},\sqrt{3}\,\mathcal{S}_{k}:k\leq N\\}$
forms a Riesz sequence for every $N\in\mathbb{N}$ with the Riesz constants
independent on $N$. By Lemma 2.1, its Gram matrix
$G_{N}\in\mathbb{R}^{(2N+1)\times(2N+1)}$ is a block matrix with three blocks.
The first one is just a $1\times 1$ block corresponding to the constant
function, the second and the third block are $N\times N$ matrices of the inner
products
$\big{(}3\langle\mathcal{C}_{i},\mathcal{C}_{j}\rangle\big{)}_{i,j=1}^{N}$ and
$\big{(}3\langle\mathcal{S}_{i},\mathcal{S}_{j}\rangle\big{)}_{i,j=1}^{N}$,
respectively, i.e.,

$G_{N}=\begin{pmatrix}\begin{matrix}{1}\end{matrix}&\dashrule[-0.6ex]{0.4}{31.531.53}&\mbox{\Large
0}&\dashrule[-0.6ex]{0.4}{31.531.53}&\mbox{\Large 0}\\\
\hdashline[2pt/2pt]\mbox{\Large
0}&\dashrule[-9ex]{0.4}{31.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.53}&\begin{matrix}\overbrace{3\langle\mathcal{C}_{1},\mathcal{C}_{1}\rangle}^{=1}&\ldots&3\langle\mathcal{C}_{1},\mathcal{C}_{N}\rangle\\\
\vdots&\ddots&\vdots\\\
3\langle\mathcal{C}_{N},\mathcal{C}_{1}\rangle&\ldots&\underbrace{3\langle\mathcal{C}_{N},\mathcal{C}_{N}\rangle}_{=1}\end{matrix}&\dashrule[-9ex]{0.4}{31.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.53}&\mbox{\Large
0}\\\ \hdashline[2pt/2pt]\mbox{\Large
0}&\dashrule[-9ex]{0.4}{31.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.53}&\mbox{\Large
0}&\dashrule[-9ex]{0.4}{31.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.531.53}&\begin{matrix}\overbrace{3\langle\mathcal{S}_{1},\mathcal{S}_{1}\rangle}^{=1}&\ldots&3\langle\mathcal{S}_{1},\mathcal{S}_{N}\rangle\\\
\vdots&\ddots&\vdots\\\
3\langle\mathcal{S}_{N},\mathcal{S}_{1}\rangle&\ldots&\underbrace{3\langle\mathcal{S}_{N},\mathcal{S}_{N}\rangle}_{=1}\end{matrix}\end{pmatrix}.$

We apply the Gershgorin theorem to $G_{N}$. Therefore, we need to estimate the
row sums of $G_{N}$. For the first row we see that $g_{1,1}=1$ and $g_{1,j}=0$
for all $j\neq 1$.

Next we assume that $i\leq N$ is an odd number, i.e. that

$i=q_{1}^{\alpha_{1}}\dots q_{n}^{\alpha_{n}}$

for some primes $q_{1},\dots,q_{n}\geq 3$ and integers
$\alpha_{1},\dots,\alpha_{n}\geq 1$. For the $(i+1)$-th row ($i=1,\ldots,N$,
corresponding to $\mathcal{C}_{i}$) we conclude

$\langle\sqrt{3}\,{\mathcal{C}_{i}},1\rangle+\sum_{j=1}^{N}3\cdot\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle+\sum_{j=1}^{N}3\cdot\langle{\mathcal{C}}_{i},{\mathcal{S}}_{j}\rangle=\sum_{1\leq
j\leq N,j\
\text{odd}}3\cdot\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle\leq\sum_{j\in\mathbb{N},j\
\text{odd}}3\cdot\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle.$ (9)

Every odd $j$ can be written as $j=q_{1}^{\beta_{1}}\dots
q_{n}^{\beta_{n}}\cdot J$, where $\beta_{1},\dots,\beta_{n}\geq 0$ and $J$ is
an odd integer, not divisible by any of $q_{1},\dots,q_{n}$, i.e., with
$\gcd(J,i)=1$. Observe that with this notation

$\gcd(i,j)=\prod_{u=1}^{n}q_{u}^{\min(\alpha_{u},\beta_{u})}.$

Therefore, we can use Lemma 2.1 and rewrite (9) as

$\displaystyle\sum_{j\in\mathbb{N},\;j\text{
odd}}3\cdot\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle$
$\displaystyle=\sum_{\beta_{1},\dots,\beta_{n}=0}^{\infty}\sum_{\begin{subarray}{c}J\in\mathbb{N},J\
\text{odd}\\\
\gcd(J,i)=1\end{subarray}}\frac{\displaystyle\prod_{u=1}^{n}q_{u}^{4\min(\alpha_{u},\beta_{u})}}{{\left(q_{1}^{\alpha_{1}}\cdots
q_{n}^{\alpha_{n}}\right)^{2}}\cdot\left(q_{1}^{\beta_{1}}\dots
q_{n}^{\beta_{n}}\cdot J\right)^{2}}$
$\displaystyle=\sum_{\begin{subarray}{c}J\in\mathbb{N},J\ \text{odd}\\\
\gcd(J,i)=1\end{subarray}}\frac{1}{J^{2}}\cdot\sum_{\beta_{1}=0}^{\infty}\frac{1}{\left[q_{1}^{\alpha_{1}+\beta_{1}-2\min(\alpha_{1},\beta_{1})}\right]^{2}}\cdots\sum_{\beta_{n}=0}^{\infty}\frac{1}{\left[q_{n}^{\alpha_{n}+\beta_{n}-2\min(\alpha_{n},\beta_{n})}\right]^{2}}.$

Next, we simplify the individual terms.

$\displaystyle\sum_{\begin{subarray}{c}J\in\mathbb{N},J\ \text{odd}\\\
\gcd(J,i)=1\end{subarray}}\frac{1}{J^{2}}$
$\displaystyle=\prod_{\begin{subarray}{c}p\geq 3:p\text{ prime}\\\
p\not\in\\{q_{1},\dots,q_{n}\\}\end{subarray}}\left(1+\frac{1}{p^{2}}+\frac{1}{p^{4}}+\dots\right)=\prod_{\begin{subarray}{c}p\geq
3:p\text{ prime}\\\
p\not\in\\{q_{1},\dots,q_{n}\\}\end{subarray}}\frac{1}{1-1/p^{2}}$

and

$\displaystyle\sum_{\beta=0}^{\infty}\frac{1}{\left[q^{\alpha+\beta-2\min(\alpha,\beta)}\right]^{2}}$
$\displaystyle=\sum_{\beta=0}^{\alpha}\frac{1}{q^{2(\alpha-\beta)}}+\sum_{\beta=\alpha+1}^{\infty}\frac{1}{q^{2(\beta-\alpha)}}$
$\displaystyle\leq\sum_{r=0}^{\infty}\frac{1}{q^{2r}}+\sum_{r=1}^{\infty}\frac{1}{q^{2r}}=\left(1+1/q^{2}\right)\cdot\frac{1}{1-1/q^{2}}.$

Therefore,

$\displaystyle\eqref{eq:C_sum}$ $\displaystyle\leq\prod_{p\geq 3:p\text{
prime}}\frac{1}{1-1/p^{2}}\cdot\prod_{u=1}^{n}\left(1+\frac{1}{q_{u}^{2}}\right)\leq\prod_{p\geq
3:p\text{ prime}}\frac{1+1/p^{2}}{1-1/p^{2}}=\frac{3}{2},$ (10)

where in the last step we used the following Euler product [23, Page 5]
attributed already to Ramanujan

$\prod_{p\text{ prime}}\frac{1+1/p^{2}}{1-1/p^{2}}=\frac{5}{2}.$

Therefore, we get

$\sum_{j\not=i}|(G_{N})_{i,j}|=\sum_{j\not=i}3\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle=\sum_{j=1}^{N}3\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle-3\langle{\mathcal{C}_{i},{\mathcal{C}}_{i}}\rangle\leq\frac{3}{2}-1=\frac{1}{2}.$
(11)

If $i$ is even it follows from Lemma 2.1, assertions 2. and 3., that the
estimates above remain the same since
$3\cdot\langle{\mathcal{C}}_{i},{\mathcal{C}}_{j}\rangle=\frac{\gcd(i,j)^{4}}{i^{2}\cdot
j^{2}}\neq 0$ only for $j$’s with the same power of $2$ in their prime
factorization as $i$, which then cancels out.

If we replace in (9) $\mathcal{C}_{i}$ by $\mathcal{S}_{i}$ (corresponding to
the rows $(N+1)+i$, $i=1,\ldots,N$ of the Gram matrix), we obtain instead the
estimate

$\langle\sqrt{3}\,{\mathcal{S}_{i}},1\rangle+\sum_{j=1}^{N}3\cdot\langle{\mathcal{S}}_{i},{\mathcal{C}}_{j}\rangle+\sum_{j=1}^{N}3\cdot|\langle{\mathcal{S}}_{i},{\mathcal{S}}_{j}\rangle|\leq\sum_{1\leq
j\leq N,j\
\text{odd}}3\cdot|\langle{\mathcal{S}}_{i},{\mathcal{S}}_{j}\rangle|\leq\sum_{j\in\mathbb{N},j\
\text{odd}}3\cdot|\langle{\mathcal{S}}_{i},{\mathcal{S}}_{j}\rangle|.$ (12)

The term on the right hand side of (12) can be bounded by (10) as before and
we again obtain

$\sum_{j\not=i}|(G_{N})_{i,j}|=\sum_{j\not=i}3|\langle{\mathcal{S}}_{i},{\mathcal{S}}_{j}\rangle|=\sum_{j=1}^{N}3|\langle{\mathcal{S}}_{i},{\mathcal{S}}_{j}\rangle|-3\langle{\mathcal{S}_{i},{\mathcal{S}}_{i}}\rangle\leq\frac{3}{2}-1=\frac{1}{2}.$
(13)

By Gershgorin’s theorem, we deduce
$\sigma(G_{N})\subset\\{1\\}\cup[\frac{1}{2},\frac{3}{2}]=[\frac{1}{2},\frac{3}{2}].$

_Proof of Theorem 2.2: Step 3._
The third step of the proof of Theorem 2.2, i.e., the passage to the limit
$N\to\infty$, is quite standard and straightforward (cf. [15] and [4, 5] for
the so-called “projection method”) and is contained in the following lemma.

######  Lemma 2.4.

Let $H$ be a real Hilbert space and let $(x_{n})_{n=1}^{\infty}\subset H$ be
an infinite sequence. If $\\{x_{1},\dots,x_{N}\\}$ is a Riesz sequence for
every $N\in\mathbb{N}$ with Riesz constants $A$ and $B$ independent on $N$,
then $\\{x_{1},x_{2},\dots\\}$ is also a Riesz sequence with Riesz constants
$A$ and $B$.

###### Proof.

Let $\alpha=(\alpha_{1},\alpha_{2},\dots)$ be a square-summable sequence.
Since

$\left\|\sum_{n=n_{0}}^{n_{1}}\alpha_{n}x_{n}\right\|^{2}\leq
B\sum_{n=n_{0}}^{n_{1}}\alpha_{n}^{2},$

the partial sums of $\sum_{n=1}^{\infty}\alpha_{n}x_{n}$ form a Cauchy
sequence and therefore the series is convergent. Furthermore, by the triangle
inequality

$\left\|\sum_{n=1}^{N}\alpha_{n}x_{n}\right\|\to\left\|\sum_{n=1}^{\infty}\alpha_{n}x_{n}\right\|.$

Hence, we can take the limit $N\to\infty$ in

$A\sum_{n=1}^{N}\alpha_{n}^{2}\leq\left\|\sum_{n=1}^{N}\alpha_{n}x_{n}\right\|^{2}\leq
B\sum_{n=1}^{N}\alpha_{n}^{2}$

and the result follows. ∎

_Proof of Theorem 2.2: Step 4._
As the last step, we show that ${\mathcal{R}}_{1}$ is not only a Riesz
sequence but also a Riesz basis, i.e., that its closed linear span is the
whole space $L_{2}([0,1])$. We rely on the fact that the trigonometric system

${\mathcal{T}}_{1}:=\\{1\\}\cup\\{\sqrt{2}\cos(2\pi
kx):k\in\mathbb{N}\\}\cup\\{\sqrt{2}\sin(2k\pi x):k\in\mathbb{N}\\}$ (14)

forms an orthonormal basis of $L_{2}([0,1])$. We show that every function from
(14) lies in the closed linear span of ${\mathcal{R}}_{1}$ and, therefore, the
closed linear span of ${\mathcal{T}}_{1}$ is contained in the closed linear
span of ${\mathcal{R}}_{1}.$

We start with the following lemma, which gives an explicit decomposition of
$\cos(2\pi x)$ and $\sin(2\pi x)$ in ${\mathcal{R}}_{1}$. Its statement
requires the notion of the Möbius function, which is defined for every
positive integer $n\in\mathbb{N}$ as

$\mu(n)=\begin{cases}+1,\quad&\text{if $n$ is a square-free integer with an
even number of prime factors},\\\ -1,\quad&\text{if $n$ is a square-free
integer with an odd number of prime factors},\\\ 0,\quad&\text{if $n$ is not a
square-free integer, i.e., if it is divisible by some squared
prime.}\end{cases}$

######  Lemma 2.5.

For every $l\in\mathbb{N}$, let
$\overline{\mathcal{C}}_{l}(x)=\sqrt{3}\,\mathcal{C}_{l}(x)/\mu$ and
$\overline{\mathcal{S}}_{l}(x)=\sqrt{3}\,\mathcal{S}_{l}(x)/\mu$, where $\mu$
is the constant from (6). Then

$c_{1}(x):=\sqrt{2}\cos(2\pi
x)=\sum_{l=0}^{\infty}\frac{\mu(2l+1)}{(2l+1)^{2}}\,\overline{\mathcal{C}_{2l+1}}(x)$
(15)

and

$s_{1}(x):=\sqrt{2}\sin(2\pi
x)=\sum_{l=0}^{\infty}(-1)^{l}\frac{\mu(2l+1)}{(2l+1)^{2}}\,\overline{\mathcal{S}_{2l+1}}(x)$
(16)

with the convergence being in $L_{2}([0,1])$.

###### Proof.

We first reformulate (5) as

$\overline{\mathcal{C}}_{1}(x)=\frac{\sqrt{3}\,{\mathcal{C}}(x)}{\mu}=\sum_{m=1}^{\infty}\frac{\alpha_{m}}{m^{2}}\cdot
c_{m}(x),$ (17)

where $\alpha_{2m+1}=1$ and $\alpha_{2m}=0$. Note, that (17) converges in
$L_{2}([0,1])$.

We show that there is a unique bounded sequence $(\beta_{l})_{l=1}^{\infty}$,
such that

$c_{1}(x)=\sum_{l=1}^{\infty}\frac{\beta_{l}}{l^{2}}\cdot{\overline{\mathcal{C}}_{l}}(x)$
(18)

with the convergence in $L_{2}([0,1])$ and that

$\beta_{l}=\begin{cases}0&\text{for $l\in\mathbb{N}$ even},\\\
\mu(l)&\text{for $l\in\mathbb{N}$ odd}.\end{cases}$ (19)

Using (17), we observe that (18) holds for bounded sequence
$(\beta_{l})_{l=1}^{\infty}$ if, and only if,

$c_{1}(x)=\sum_{l=1}^{\infty}\sum_{m=1}^{\infty}\frac{\beta_{l}\cdot\alpha_{m}}{l^{2}\cdot
m^{2}}c_{lm}(x).$ (20)

We compare the coefficients of $c_{k}(x)$ on both sides of (20) and observe
that (20) is equivalent to the system of equations

$\displaystyle\begin{split}1&=\beta_{1}\alpha_{1},\\\ 0&=\sum_{(l,m):l\cdot
m=n}\beta_{l}\alpha_{m},\quad n=2,3,\dots.\end{split}$ (21)

This system could be solved by using the Möbius inversion formula [23, p. 3],
but one can also proceed directly. From $1=\beta_{1}\alpha_{1}$ we obtain
$\beta_{1}=1$ and from $\beta_{1}\alpha_{2}+\beta_{2}\alpha_{1}=0$ we get
$\beta_{2}=0$. We show by induction that $\beta_{2n}=0$ also for all $n\geq
1$. Let this be true for all integers smaller than $n$. Then

$0=\sum_{(l,m):l\cdot m=2n}\beta_{l}\alpha_{m}=\sum_{(l,m):l\cdot
m=n}\beta_{2l}\alpha_{m}+\sum_{(l,m):l\cdot
m=n}\beta_{l}\alpha_{2m}=\beta_{2n}\alpha_{1}$

gives $\beta_{2n}=0$ as well. Similarly, from
$0=\beta_{p}\alpha_{1}+\beta_{1}\alpha_{p}$ we get $\beta_{p}=-1$ for every
prime $p\neq 2$.

Let now $p=p_{1}p_{2}$ with odd primes $p_{1},p_{2}$. Then $\beta_{p}=1$
follows from

$0=\beta_{p}\
\alpha_{1}+\beta_{p_{1}}\alpha_{p_{2}}+\beta_{p_{2}}\alpha_{p_{1}}+\beta_{1}\alpha_{p}=\beta_{p}\cdot
1+(-1\cdot 1)+(-1\cdot 1)+1.$

The formula for a general $p=p_{1}\cdot\ldots\cdot p_{k}$, with distinct odd
primes $p_{i}$ follows by induction. Observe that $p$ is divisible by all
$p_{1}^{e_{1}}\cdot\ldots\cdot p_{k}^{e_{k}}$ with
$e=(e_{1},\dots,e_{k})\in\\{0,1\\}^{k}$. Hence

$\displaystyle 0=\sum_{(l,m):l\cdot
m=p}\beta_{l}\alpha_{m}=\sum_{l|p}\beta_{l}=\beta_{p}+\sum_{j=0}^{k-1}\binom{k}{j}(-1)^{j}=\beta_{p}+\sum_{j=0}^{k}\binom{k}{j}(-1)^{j}-(-1)^{k}=\beta_{p}-(-1)^{k}.$

We conclude, that $\beta_{n}=\mu(n)$ for every odd square-free integer $n$.

Finally, we show that $\beta_{n}=0$ for every positive odd integer $n$, which
is not square-free. Therefore, we assume that $n=p_{1}^{u}\cdot q$, where
$p_{1}$ is an odd prime, $q$ is an odd integer not divisible by $p_{1}$,
$u\geq 2$ and that the statement is true for all integers smaller than $n$. We
obtain

$\displaystyle 0=\sum_{(l,m):l\cdot
m=n}\beta_{l}\alpha_{m}=\sum_{l|p_{1}^{u}q}\beta_{l}=\sum_{l|q}(\beta_{l}+\beta_{p_{1}l}+\dots+\beta_{p_{1}^{u}l}).$

If $l<q$ is square-free, then the first two terms in this sum have values $+1$
and $-1$, respectively, and the others vanish by the induction assumption. If
$l<q$ is not square-free, then all the terms vanish again by assumption.
Finally, if $l=q$ the same argument applies leaving us with $\beta_{n}=0$. We
conclude that the sequence $(\beta_{l})_{l=1}^{\infty}$ given by (19) indeed
satisfies the system (21) which in turn gives (18).

Finally, (16) follows from (15) using the simple relation
$\mathcal{S}(x)=\mathcal{C}(x-1/4).$ The factor $(-1)^{l}$ results from the
relation

$\mathcal{C}_{2l+1}\Big{(}x-\frac{1}{4}\Big{)}=(-1)^{l}\mathcal{C}\Big{(}(2l+1)x-\frac{1}{4}\Big{)}=(-1)^{l}\mathcal{S}_{2l+1}(x).$

∎

##  3 Multivariate case

The main aim of this section is to generalize Theorem 2.2 to higher dimensions
$d\geq 1$ and to provide a Riesz basis of $L_{2}([0,1]^{d})$, which is easily
expressed by artificial neural networks with $\operatorname{ReLU}$ activation
function. The most natural approach would be to consider the tensor products
of the functions from ${\mathcal{R}}_{1}$, i.e., a system of functions of the
form $(x,y)\to\mathcal{C}_{k}(x)\cdot\mathcal{C}_{l}(y)$ etc. Indeed, it is
quite easy to show that tensor products of elements of a Riesz sequence form
again a Riesz sequence [2]. This approach is quite classical in analysis and
there exist many multivariate bases and systems with a tensor product
structure. Unfortunately, the Riesz constants of the tensor product system are
in general given as products of the Riesz constants of the univariate Riesz
sequences, cf. [2, Theorem 4.1]. Applying the tensor product construction to
${\mathcal{R}}_{1}$ would therefore lead to an exponential dependence of the
ratio of the Riesz constants on the dimension.

Furthermore, the tensor product approach does not fit really well to
artificial neural networks. The reason is that it is surprisingly difficult to
construct a neural network, which for two real inputs $x$ and $y$ outputs the
product $xy$ (or at least its approximation). In general, one first
approximates the square function $t\to t^{2}$ and then applies the formula
$xy=[(x+y)^{2}-(x-y)^{2}]/4.$ We refer to [10, 20, 25] for details. Therefore,
we are looking for another multivariate Riesz basis of piecewise affine
functions, which can be constructed without the use of (tensor) products, but
where inner products with fixed vectors in $\mathbb{R}^{d}$ are allowed.

Before we state our results, we need some additional notation. If
$\alpha=(\alpha_{1},\dots,\alpha_{d})\in\mathbb{Z}^{d}$, we say that
$\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$ if the first non-zero entry of
$\alpha$ is positive. The multivariate analogue of ${\mathcal{R}}_{1}$ is then
defined simply as

${\mathcal{R}}_{d}:=\\{1\\}\cup\\{{\mathcal{C}}(\alpha\cdot
x):\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0\\}\cup\\{\mathcal{S}(\alpha\cdot
x):\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0\\},$

where we interpret the functions $\mathcal{C}$ and $\mathcal{S}$ as
$1-$periodic functions on $\mathbb{R}$. Note that we need to restrict
ourselves to indices
$\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$ here, since ${\mathcal{C}}(\alpha\cdot
x)={\mathcal{C}}(-\alpha\cdot x)$ and ${\mathcal{S}}(\alpha\cdot
x)=-{\mathcal{S}}(-\alpha\cdot x)$, respectively.

Furthermore, we say that two non-zero $\alpha,\beta\in\mathbb{R}^{d}$ are co-
linear if there is $t\not=0$ such that $\alpha=t\beta.$ Obviously, if
$\alpha,\beta\in\mathbb{Z}^{d}$ with
$\alpha,\beta\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$ are co-linear, then $t>0$. In the rest
of this section, the inner product $\displaystyle\langle
f,g\rangle=\int_{[0,1]^{d}}f(x)g(x)dx$ denotes the inner product in
$L_{2}([0,1]^{d})$, the space of real square integrable functions on
$[0,1]^{d}$.

The multivariate analogue of Lemma 2.1, which characterizes the inner products
of the elements of ${\mathcal{R}}_{d}$ then looks as follows.

######  Lemma 3.1.

Let $\alpha,\beta\in\mathbb{Z}^{d}$ with
$\alpha,\beta\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$. Then

  1. 1.

$\langle\mathcal{C}(\alpha\cdot x),\mathcal{S}(\beta\cdot x)\rangle=0$.

  2. 2.

$\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot
x)\rangle=\langle{\mathcal{S}}(\alpha\cdot x),{\mathcal{S}}(\beta\cdot
x)\rangle=0$ if $\alpha$ and $\beta$ are not co-linear, or if $\alpha=t\beta$,
but $t$ can not be written as a ratio of two odd positive integers.

  3. 3.

If $\displaystyle\alpha=\frac{2p+1}{2q+1}\cdot\beta$ with coprime integers
$2p+1$ and $2q+1$ (i.e., $\gcd(2p+1,2q+1)=1$), then

$3\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot
x)\rangle=\frac{1}{(2p+1)^{2}(2q+1)^{2}}$ (22)

and

$3\langle\mathcal{S}(\alpha\cdot x),\mathcal{S}(\beta\cdot
x)\rangle=\frac{(-1)^{p+q}}{(2p+1)^{2}(2q+1)^{2}}.$ (23)

######  Remark 3.2.

Lemma 3.1 includes Lemma 2.1 as a special case. In particular, if $d=1$ then
$\alpha$ and $\beta$ are always co-linear. Moreover, if the prime
factorizations of $\alpha$ and $\beta$ contain different powers of $2$, then
we have $\alpha\neq\frac{2p+1}{2q+1}\beta$ for all integers $p,q$.

###### Proof of Lemma 3.1.

First, we recall the elementary formulas

$\displaystyle\cos(u_{1}+\dots+u_{d})$
$\displaystyle=\operatorname{Re}(e^{i(u_{1}+\dots+u_{d})})=\operatorname{Re}\left[\prod_{j=1}^{d}(\cos
u_{j}+i\sin u_{j})\right]$ $\displaystyle=\sum_{J\subset\\{1,\dots,d\\},\\#J\
\text{even}}(-1)^{\\#J/2}\prod_{j\not\in J}\cos u_{j}\cdot\prod_{j\in J}\sin
u_{j}$ (24)

and

$\displaystyle\sin(u_{1}+\dots+u_{d})$
$\displaystyle=\operatorname{Im}(e^{i(u_{1}+\dots+u_{d})})=\operatorname{Im}\left[\prod_{j=1}^{d}(\cos
u_{j}+i\sin u_{j})\right]$ $\displaystyle=\sum_{J\subset\\{1,\dots,d\\},\\#J\
\text{odd}}(-1)^{(\\#J-1)/2}\prod_{j\not\in J}\cos u_{j}\cdot\prod_{j\in
J}\sin u_{j}.$ (25)

Next, we proceed to the proof of (22). Let us fix
$\alpha,\beta\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$. We apply (5) followed by (24) and
obtain

$\displaystyle 3$ $\displaystyle\langle{\mathcal{C}}(\alpha\cdot
x),{\mathcal{C}}(\beta\cdot x)\rangle=\sum_{m,n\geq
0}\frac{\mu^{2}}{(2m+1)^{2}(2n+1)^{2}}\int_{[0,1]^{d}}c_{2m+1}(\alpha\cdot
x)c_{2n+1}(\beta\cdot x)dx$ $\displaystyle=\sum_{m,n\geq
0}\sum_{\begin{subarray}{c}J,K\subset\\{1,\dots,d\\}\\\ \\#J,\\#K\
\text{even}\end{subarray}}\frac{2\mu^{2}}{(2m+1)^{2}(2n+1)^{2}}\cdot(-1)^{(\\#J+\\#K)/2}\cdot$
$\displaystyle\qquad\qquad\cdot\frac{1}{2^{d}}\cdot\int_{[0,1]^{d}}\prod_{j\not\in
J}c_{2m+1}(\alpha_{j}x_{j})\prod_{j\in
J}s_{2m+1}(\alpha_{j}x_{j})\prod_{k\not\in
K}c_{2n+1}(\beta_{k}x_{k})\prod_{k\in K}s_{2n+1}(\beta_{k}x_{k})dx$
$\displaystyle=\sum_{m,n\geq
0}\sum_{\begin{subarray}{c}J\subset\\{1,\dots,d\\}\\\ \\#J\
\text{even}\end{subarray}}\frac{2\mu^{2}}{(2m+1)^{2}(2n+1)^{2}}$
$\displaystyle\qquad\qquad\cdot\frac{1}{2^{d}}\cdot\prod_{j\not\in
J}\int_{[0,1]}c_{2m+1}(\alpha_{j}x_{j})c_{2n+1}(\beta_{j}x_{j})dx_{j}\cdot\prod_{j\in
J}\int_{[0,1]}s_{2m+1}(\alpha_{j}x_{j})s_{2n+1}(\beta_{j}x_{j})dx_{j}.$ (26)

Next, we discuss, when the last product vanishes for given $J$. First, this
happens if $\alpha_{j}=0$ or $\beta_{j}=0$ for any $j\in J$. If $j\in J$ and
both $\alpha_{j}$ and $\beta_{j}$ are non-zero, then the last product vanishes
also if $(2m+1)|\alpha_{j}|\not=(2n+1)|\beta_{j}|$. And finally, the product
is zero also if $j\not\in J$ and $(2m+1)|\alpha_{j}|\not=(2n+1)|\beta_{j}|$.

Equivalently, (26) is not equal to zero if
$(2m+1)|\alpha_{j}|=(2n+1)|\beta_{j}|$ for every $j\in\\{1,\dots,d\\}$ and
$\alpha_{j}$ and $\beta_{j}$ are different from zero if $j\in J$. If we denote
$|\alpha|=(|\alpha_{1}|,\dots,|\alpha_{n}|)$ (and similarly for $|\beta|$), we
will therefore restrict ourselves for the rest of the proof to $m,n\geq 0$
with

$(2m+1)|\alpha|=(2n+1)|\beta|.$ (27)

If there is no pair of integers $(m,n)\in\mathbb{N}_{0}^{2}$, such that (27)
holds, then $\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot
x)\rangle=0$. Furthermore, we may consider only sets $J\subset\\{1,\dots,d\\}$
with an even number of elements, which are subsets of
$\operatorname{supp}(\alpha)=\operatorname{supp}(\beta).$

If (27) holds, than the univariate integrals in (26) are equal to one for
$j\not\in J$ and $j\in\operatorname{supp}(\alpha)$. They are equal to two, if
$j\not\in J$ and $j\not\in\operatorname{supp}(\alpha)$. And if $j\in
J\subset\operatorname{supp}(\alpha)$, then the integral is +1 if
$(2m+1)\alpha_{j}=(2n+1)\beta_{j}$ and it is equal to $-1$ if
$(2m+1)\alpha_{j}=-(2n+1)\beta_{j}$.

We denote
$D=\\{j:\operatorname{sign}(\alpha_{j})\cdot\operatorname{sign}(\beta_{j})=-1\\}\subset\operatorname{supp}(\alpha)=\operatorname{supp}(\beta)$,
$\nu=\\#D$ and $n=\\#\operatorname{supp}(\alpha)\geq\nu$. Using this notation,
we obtain

$\displaystyle 3\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot
x)\rangle$ $\displaystyle=\sum_{\begin{subarray}{c}m,n\geq 0\\\
(2m+1)|\alpha|=(2n+1)|\beta|\end{subarray}}\frac{2\mu^{2}}{(2m+1)^{2}(2n+1)^{2}\cdot
2^{n}}\sum_{\begin{subarray}{c}J\subset\operatorname{supp}(\alpha)\\\ \\#J\
\text{even}\end{subarray}}(-1)^{\\#(J\cap D)}.$

If $\nu\geq 1$, we calculate

$\displaystyle\sum_{\begin{subarray}{c}J\subset\operatorname{supp}(\alpha)\\\
\\#J\ \text{even}\end{subarray}}(-1)^{\\#(J\cap D)}$
$\displaystyle=\sum_{\begin{subarray}{c}0\leq a\leq n-\nu\\\ 0\leq b\leq\nu\\\
a+b\text{\ even}\end{subarray}}(-1)^{b}\binom{n-\nu}{a}\binom{\nu}{b}$
$\displaystyle=\sum_{b=0}^{\nu}(-1)^{b}\binom{\nu}{b}\sum_{\begin{subarray}{c}0\leq
a\leq n-\nu\\\ a+b\text{\ even}\end{subarray}}\binom{n-\nu}{a}=0,$

where the last step follows since
$\sum_{b=0}^{\nu}(-1)^{b}\binom{\nu}{b}=(1-1)^{\nu}=0$. Hence,
$\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot x)\rangle=0$ if
there exists $1\leq j\leq d$ with
$\operatorname{sign}(\alpha_{j})\cdot\operatorname{sign}(\beta_{j})=-1$ and we
arrive at

$3\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot
x)\rangle=\sum_{\begin{subarray}{c}m,n\geq 0\\\
(2m+1)\alpha=(2n+1)\beta\end{subarray}}\frac{\mu^{2}}{(2m+1)^{2}(2n+1)^{2}}.$

The last sum is empty if $\alpha$ and $\beta$ are not co-linear or if we can
not write $\alpha=t\beta$, where $t>0$ is a ratio of two odd integers.
Therefore, we assume that $\displaystyle\alpha=\frac{2p+1}{2q+1}\beta$ with
$p,q\in\mathbb{N}_{0}$ and that $2p+1$ and $2q+1$ are coprime integers. All
pairs $(m,n)\in\mathbb{N}_{0}^{2}$ with $(2m+1)\alpha=(2n+1)\beta$ are then of
the form

$2m+1=(2q+1)(2l+1)\quad\text{and}\quad 2n+1=(2p+1)(2l+1),\quad
l\in\mathbb{N}_{0}.$ (28)

This finally leads to

$3\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot
x)\rangle=\sum_{l=0}^{\infty}\frac{\mu^{2}}{(2q+1)^{2}(2p+1)^{2}(2l+1)^{4}},$

which combined with (6) gives (22). As a byproduct, we also showed that
$\langle{\mathcal{C}}(\alpha\cdot x),{\mathcal{C}}(\beta\cdot x)\rangle=0$ if
$\alpha$ and $\beta$ are not co-linear with a real factor $t$, which can be
written as a ration of two odd positive integers.

Applying the same idea to the inner product of $\mathcal{C}(\alpha\cdot x)$
and $\mathcal{S}(\beta\cdot x)$, we get a double sum over
$J,K\subset\\{1,\dots,d\\}$ with $\\#J$ even and $\\#K$ odd. Therefore, it is
not possible to match the univariate integrands and their product always
vanishes. Finally, (23) follows in the same way, the only essential difference
being the $(-1)^{m+n}$ factor coming from (5). And an easy observation shows
that under (28), the parity of $m+n$ is the same as the one of $p+q.$ ∎

We complement Lemma 3.1 by the simple observation that the constant function
is orthogonal to all other elements of ${\mathcal{R}}_{d}$. The multivariate
analogue of Theorem 2.2 then reads as follows.

######  Theorem 3.3.

Let $d\geq 1$. Then the system ${\mathcal{R}}_{d}$ forms a Riesz basis of
$L_{2}([0,1]^{d})$ with the Riesz constants independent of $d$. To be more
specific, the Riesz constants of the normalized system

$\\{1\\}\cup\\{\sqrt{3}\,{\mathcal{C}}(\alpha\cdot
x):\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0\\}\cup\\{\sqrt{3}\,\mathcal{S}(\alpha\cdot
x):\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0\\}$ (29)

can be chosen as $A=1/2$ and $B=3/2$ independently of $d$.

###### Proof.

_Step 1._ Using Lemma 3.1 together with the Gershgorin circle theorem, it is
surprisingly simple to prove Theorem 3.3 with slightly worse constants $A$ and
$B$, cf. Remark 3.4. To improve the Riesz constants to $A=1/2$ and $B=3/2$, we
proceed more carefully. Let us denote by ${\mathbb{P}}$ the set of primes and
by ${\mathbb{P}}^{\prime}={\mathbb{P}}\setminus\\{2\\}$ the set of odd primes.
Then every odd $p\in\mathbb{N}$ can be written as
$p=p_{1}^{k_{1}}\cdot\ldots\cdot p_{n}^{k_{n}}$ with
$p_{1},\dots,p_{n}\in{\mathbb{P}}^{\prime}$ and
$k_{1},\dots,k_{n}\in\mathbb{N}$. If $p=1$, then we choose $n=0$ and
interprete the empty product as one.

We use the following observation. To a fixed
$\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$ and a pair of odd coprimed integers
$2p+1$ and $2q+1$, there exists at most one
$\beta\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$ such that
$\alpha=(2p+1)/(2q+1)\cdot\beta$. Then we obtain

$\displaystyle
3\sum_{\beta\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0}\langle\mathcal{C}(\alpha\cdot
x),\mathcal{C}(\beta\cdot x)\rangle$ $\displaystyle\leq\sum_{2p+1,2q+1\
\text{coprimes}}\frac{1}{(2p+1)^{2}(2q+1)^{2}}=\sum_{p,q\geq 1\ \text{odd
coprimes}}\frac{1}{p^{2}q^{2}}$
$\displaystyle=\sum_{\\{p_{1},\dots,p_{n}\\}\subset{\mathbb{P}}^{\prime}}\sum_{k_{1},\dots,k_{n}=1}^{\infty}\frac{1}{p_{1}^{2k_{1}}\dots
p_{n}^{2k_{n}}}\sum_{\begin{subarray}{c}q\geq 1,q\text{ odd}\\\
\gcd(q,p_{1}\dots p_{n})=1\end{subarray}}\frac{1}{q^{2}}$
$\displaystyle=\sum_{\\{p_{1},\dots,p_{n}\\}\subset{\mathbb{P}}^{\prime}}\prod_{u=1}^{n}\left(\sum_{k_{u}=1}^{\infty}\frac{1}{p_{u}^{2k_{u}}}\right)\prod_{p\in{\mathbb{P}}^{\prime}\setminus\\{p_{1},\dots,p_{n}\\}}\left(\sum_{k=0}^{\infty}\frac{1}{p^{2k}}\right)$
$\displaystyle=\sum_{\\{p_{1},\dots,p_{n}\\}\subset{\mathbb{P}}^{\prime}}\prod_{u=1}^{n}\frac{1}{p_{u}^{2}(1-1/p_{u}^{2})}\prod_{p\in{\mathbb{P}}^{\prime}\setminus\\{p_{1},\dots,p_{n}\\}}\frac{1}{1-1/p^{2}}$
$\displaystyle=\sum_{\\{p_{1},\dots,p_{n}\\}\subset{\mathbb{P}}^{\prime}}\frac{1}{p_{1}^{2}\dots
p_{n}^{2}}\prod_{p\in{\mathbb{P}}^{\prime}}\frac{1}{1-1/p^{2}}$
$\displaystyle=\prod_{p\in{\mathbb{P}}^{\prime}}\frac{1}{1-1/p^{2}}\prod_{p\in{\mathbb{P}}^{\prime}}(1+1/p^{2})=\frac{3}{2},$

where the last step follows from (10). Using the Gershgorin circle theorem in
the same way as in the proof of Theorem 2.2 then gives the bounds $1/2\leq
A\leq B\leq 3/2$, independent of $d$.

_Step 2._ We show that ${\mathcal{R}}_{d}$ is also a Riesz basis. The system

$\\{1\\}\cup\\{c_{k}(x):k\in\mathbb{N}\\}\cup\\{s_{k}(x):k\in\mathbb{N}\\}$
(30)

with $c_{k}(x)=\sqrt{2}\cos(2\pi kx)$ and $s_{k}(x)=\sqrt{2}\sin(2\pi kx)$ is
an orthonormal basis of $L_{2}([0,1])$. Therefore, all possible tensor
products of the functions from (30) form an orthonormal basis of
$L_{2}([0,1]^{d})$. For this system we use the following notation

$\left\\{\prod_{l\in L}c_{k_{l}}(x_{l})\prod_{m\in
M}s_{k_{m}}(x_{m}):L,M\subset\\{1,\dots,d\\}\
\text{disjoint},k_{l},k_{m}\in\mathbb{N}\right\\}.$ (31)

Now we show that every function from (31) can be found in the closed linear
span of ${\mathcal{R}}_{d}$. This will imply the completeness of
${\mathcal{R}}_{d}.$ First, we again recall two simple formulas

$\displaystyle\prod_{u=1}^{n}\cos(\varphi_{u})$
$\displaystyle=\prod_{u=1}^{n}\frac{e^{i\varphi_{u}}+e^{-i\varphi_{u}}}{2}=\frac{1}{2^{n}}\sum_{e\in\\{-1,+1\\}^{n}}\exp(i[e_{1}\varphi_{1}+\dots+e_{n}\varphi_{n}])$
$\displaystyle=\frac{1}{2^{n}}\sum_{e\in\\{-1,+1\\}^{n}}\cos(e_{1}\varphi_{1}+\dots+e_{n}\varphi_{n})$

and, similarly,

$\displaystyle\prod_{u=1}^{n}\sin(\varphi_{u})=\frac{(-1)^{\lfloor\frac{n}{2}\rfloor}}{2^{n}}\cdot\begin{cases}\displaystyle\sum_{e\in\\{-1,+1\\}^{n}}\cos(e_{1}\varphi_{1}+\dots+e_{n}\varphi_{n})\cdot\prod_{j=1}^{n}e_{j}\
\text{if $n$ is even},\\\
\displaystyle\sum_{e\in\\{-1,+1\\}^{n}}\sin(e_{1}\varphi_{1}+\dots+e_{n}\varphi_{n})\cdot\prod_{j=1}^{n}e_{j}\
\text{if $n$ is odd.}\end{cases}$

If $\\#M$ is even, we use the elementary property
$\cos(\alpha)\cos(\beta)=(\cos(\alpha+\beta)+\cos(\alpha-\beta))/2$ and obtain

$\displaystyle\prod_{l\in L}$ $\displaystyle c_{k_{l}}(x_{l})\prod_{m\in
M}s_{k_{m}}(x_{m})=2^{(\\#L+\\#M)/2}\prod_{l\in L}\cos(2\pi
k_{l}x_{l})\prod_{m\in M}\sin(2\pi k_{m}x_{m})$
$\displaystyle=\frac{(-1)^{\lfloor\\#M/2\rfloor}}{2^{(\\#L+\\#M)/2}}\sum_{e\in\\{-1,+1\\}^{\\#L}}\cos\left(\sum_{l\in
L}e_{l}\cdot 2\pi
k_{l}x_{l}\right)\cdot\sum_{e^{\prime}\in\\{-1,+1\\}^{\\#M}}\cos\left(\sum_{m\in
M}e^{\prime}_{m}\cdot 2\pi k_{m}x_{m}\right)\cdot\prod_{m\in M}e^{\prime}_{m}$
$\displaystyle=\frac{(-1)^{\lfloor\\#M/2\rfloor}}{2^{(\\#L+\\#M)/2}}\sum_{e\in\\{-1,+1\\}^{\\#L+\\#M}}\cos\left(\sum_{l\in
L}e_{l}\cdot 2\pi k_{l}x_{l}\right)\cdot\cos\left(\sum_{m\in M}e_{m}\cdot 2\pi
k_{m}x_{m}\right)\cdot\prod_{m\in M}e_{m}$
$\displaystyle=\frac{(-1)^{\lfloor\\#M/2\rfloor}}{2\cdot
2^{(\\#L+\\#M)/2}}\sum_{e\in\\{-1,+1\\}^{\\#L+\\#M}}\cos\left(\sum_{l\in
L}e_{l}\cdot 2\pi k_{l}x_{l}+\sum_{m\in M}e_{m}\cdot 2\pi
k_{m}x_{m}\right)\cdot\prod_{m\in M}e_{m}$
$\displaystyle\qquad+\frac{(-1)^{\lfloor\\#M/2\rfloor}}{2\cdot
2^{(\\#L+\\#M)/2}}\sum_{e\in\\{-1,+1\\}^{\\#L+\\#M}}\cos\left(\sum_{l\in
L}e_{l}\cdot 2\pi k_{l}x_{l}-\sum_{m\in M}e_{m}\cdot 2\pi
k_{m}x_{m}\right)\cdot\prod_{m\in M}e_{m}$
$\displaystyle=\frac{(-1)^{\lfloor\\#M/2\rfloor}}{2^{(\\#L+\\#M)/2}}\sum_{e\in\\{-1,+1\\}^{\\#L+\\#M}}\cos\left(\sum_{u\in
L\cup M}e_{u}\cdot 2\pi k_{u}x_{u}\right)\cdot\prod_{m\in M}e_{m}$
$\displaystyle=\frac{(-1)^{\lfloor\\#M/2\rfloor}}{2^{(\\#L+\\#M)/2}}\sum_{e\in\\{-1,+1\\}^{\\#L+\\#M}}\sum_{l=0}^{\infty}\frac{\mu(2l+1)}{(2l+1)^{2}}\frac{\sqrt{3}}{\sqrt{2}\mu}{\mathcal{C}}_{{2l+1}}\left(\sum_{u\in
L\cup M}e_{u}k_{u}x_{u}\right)\cdot\prod_{m\in M}e_{m},$ (32)

where in the last step we used the Fourier decomposition from (15). If $\\#M$
is odd, we use instead the formula
$\cos(\alpha)\sin(\beta)=(\sin(\alpha+\beta)+\sin(\beta-\alpha))/2$, which
yields

$\displaystyle\prod_{l\in L}$ $\displaystyle c_{k_{l}}(x_{l})\prod_{m\in
M}s_{k_{m}}(x_{m})$
$\displaystyle=\frac{(-1)^{\lfloor\\#M/2\rfloor}}{2^{(\\#L+\\#M)/2}}\sum_{e\in\\{-1,+1\\}^{\\#L+\\#M}}\sum_{l=0}^{\infty}(-1)^{l}\frac{\mu(2l+1)}{(2l+1)^{2}}\frac{\sqrt{3}}{\sqrt{2}\mu}{\mathcal{S}}_{2l+1}\left(\sum_{u\in
L\cup M}e_{u}k_{u}x_{u}\right)\cdot\prod_{m\in M}e_{m}.$

We interprete these formulas as a decomposition of a basis function from (31)
into ${\mathcal{R}}_{d}$, which converges in $L_{2}([0,1]^{d})$. Reasoning
similarly as in the proof of Theorem 2.2, this finishes the argument. ∎

######  Remark 3.4.

We observe that Lemma 3.1 implies for fixed
$\alpha\mathrel{\makebox[7.7778pt]{\raisebox{0.3pt}{\clipbox{.30pt{}
.30pt}{$+$}}\makebox[7.7778pt]{$>$}}}0$

$\displaystyle 3\sum_{\beta\not=\alpha}|\langle\mathcal{C}(\alpha\cdot
x),\mathcal{C}(\beta\cdot x)\rangle|\leq\sum_{p,q\geq
0}\frac{1}{(2p+1)^{2}(2q+1)^{2}}-1=\frac{\pi^{4}}{8^{2}}-1=0.522....$

Using Gershgorin’s theorem similarly as in the proof of Theorem 2.2, we could
have obtained quite easily that (29) is a Riesz sequence with constants
$A=2-\pi^{4}/64$ and $B=\pi^{4}/64.$

##  4 Neural networks

In this section we finally address the question in which classes of neural
networks we can find the elements of the new Riesz basis $\mathcal{R}_{d}$.
Therefore, we first fix some notation and recall what was shown in [7, Sect.
6] (in case $d=1$).

A function $f:\mathbb{R}^{n_{1}}\to\mathbb{R}^{n_{2}}$ is called affine, if it
can be written as $f(x)=Mx+b$, where $M\in\mathbb{R}^{n_{2}\times n_{1}}$ is a
matrix and $b\in\mathbb{R}^{n_{2}}.$ The following definition formalizes the
notion of $\operatorname{ReLU}$ neural networks with width $W$ and depth $L$,
cf. Figure 4 and 5.

######  Definition 4.1.

Let $d,W,L$ be positive integers. Then a feed-forward $\operatorname{ReLU}$
network ${\mathcal{N}}$ with width $W$ and depth $L$ is a collection of $L+1$
affine mappings $A^{(0)},\dots,A^{(L)}$, where
$A^{(0)}:\mathbb{R}^{d}\to\mathbb{R}^{W}$,
$A^{(j)}:\mathbb{R}^{W}\to\mathbb{R}^{W}$ for $j=1,\dots,L-1$ and
$A^{(L)}:\mathbb{R}^{W}\to\mathbb{R}$. Each such a network ${\mathcal{N}}$
generates a function of $d$ variables

$A^{(L)}\circ\operatorname{ReLU}\circ
A^{(L-1)}\circ\cdots\circ\operatorname{ReLU}\circ A^{(0)}.$

Moreover, we denote by $\Upsilon^{W,L}$ the set of all functions, which are
generated in this way by some feed-forward $\operatorname{ReLU}$ network with
width $W$ and depth $L$.

Figure 4: Feed-forward $\mathrm{ReLU}$ network with length $L$, width $W$
Figure 5: Close-up: $\mathrm{ReLU}$ activation function acting in neuron in
1st hidden layer

Every $S\in\Upsilon^{W,L}$ is a continuous piecewise affine function on
${\mathbb{R}}^{d}$. If the affine mappings associated to $S$ are denoted by
$A^{(l)}$ with $l=0,\ldots,L$, then the value $S(x^{(0)})$ is computed for
each input $x:=x^{(0)}\in\mathbb{R}^{d}$ after the calculation of a series of
intermediate vectors
$x^{(l)}:=\operatorname{ReLU}(A^{(l-1)}x^{(l-1)})\in\mathbb{R}^{W}$,
$l=1,\dots,L$, called vectors of activation at layer $l$. Finally the output
$S(x)$ is produced as $S(x):=x^{(L+1)}=A^{(L)}x^{(L)}$.

We collect some properties of the sets $\Upsilon^{W,L}$, which are needed in
the sequel.

######  Proposition 4.2.

Let $W\geq 2$.

  * (i)

Let
$\mathcal{Y}_{1}\in\Upsilon^{W,L_{1}},\ldots,\mathcal{Y}_{k}\in\Upsilon^{W,L_{k}}$.
Then the composition of the $\mathcal{Y}_{i}$ satisfies

$\mathcal{Y}_{k}\circ\dots\circ\mathcal{Y}_{1}\in\Upsilon^{W,L},\qquad
L=L_{1}+\dots+L_{k}.$

  * (ii)

Let $L\geq 1$. Then $\Upsilon^{W,L}\subset\Upsilon^{W,L+1}$.

###### Proof.

The proof of (i) can be found in [7, Prop. 4.2] for $d=1$. The proof for
general $d\geq 1$ follows virtually without any change.

For the proof of (ii), we consider the identity function ${\rm id}(x)=x$ for
$x\in\mathbb{R}$. We rewrite it as

${\rm
id}(x)=\begin{bmatrix}1&-1\end{bmatrix}\operatorname{ReLU}\left\\{\begin{bmatrix}1\\\
-1\end{bmatrix}x\right\\}$ (33)

to conclude that ${\rm id}\in\Upsilon^{2,1}$. An easy modification of (33)
also shows that ${\rm id}\in\Upsilon^{W,1}$ for every $W\geq 2$. The result
then follows by (i). ∎

An important example and building block for our constructions to follow is the
_hat function_ $H:[0,1]\rightarrow\mathbb{R}$

$H(x):=\begin{cases}2x,&0\leq x\leq\frac{1}{2},\\\ 2(1-x),&\frac{1}{2}<x\leq
1,\end{cases}$

which was already used in connection with feed-forward neural networks with
$\operatorname{ReLU}$ activation function by [22], cf. also [7, 20, 25]. From
the representation

$H(x)=\begin{bmatrix}2&-4\end{bmatrix}\mathrm{ReLU}\left\\{\begin{bmatrix}1\\\
1\end{bmatrix}x+\begin{bmatrix}0\\\ -\frac{1}{2}\end{bmatrix}\right\\},\quad
x\in[0,1]$

we see, that $H$ belongs to $\Upsilon^{2,1}$, see Figure 6.

Figure 6: Computational graph showing $H\in\Upsilon^{2,1}$ and usual graph
associated with $H$

Furthermore, since $H\in\Upsilon^{2,1}$, we deduce from Proposition 4.2(i)
that the $k$-fold composition $H^{\circ k}:=H\circ H\circ\dots\circ H$ belongs
to $\Upsilon^{2,k}$, cf. Figure 7.

Figure 7: The graphs of $H$, $H^{\circ 2}$, and $H^{\circ 3}$

In particular, $H^{\circ m}$ is a sawtooth function taking alternatively the
values $0$ and $1$ at its breakpoints $l2^{-m}$, $l=0,1,\ldots,2^{m}$, cf.
[10, Lemma III.1] or [22, Lemma 2.4]. Moreover, since the restriction of the
function $(2^{m}x-\lfloor 2^{m}x\rfloor)$ on each interval
$[l2^{-m},(l+1)2^{-m})$ is a linear function passing through $l2^{-m}$ with
slope $2^{m}$ and $\mathcal{C}(0)=\mathcal{C}(1)$, we have the coincidence

$\mathcal{C}_{2^{m}}(x)=\mathcal{C}(2^{m}x-\lfloor
2^{m}x\rfloor)=\mathcal{C}(H^{\circ m}(x)),\quad x\in[0,1],$

cf. [7, Page 147]. Therefore, since $H$ and $\mathcal{C}=1-2H$ belong to
$\Upsilon^{2,1}$, we obtain from Proposition 4.2(i) that
$\mathcal{C}_{2^{m}}\in\Upsilon^{2,m+1}$ for $m=\mathbb{N}_{0}$. Concerning
$\mathcal{S}$, we deduce $\mathcal{S}\in\Upsilon^{2,2}$ from the identity
$\mathcal{S}(x)=\mathcal{C}_{2}(\frac{x}{2}+\frac{3}{8})$, $x\in[0,1]$, which
ultimately yields $\mathcal{S}_{2^{m}}\in\Upsilon^{2,m+2}$. Moreover, for
arbitrary $j\in\mathbb{N}$, we choose the smallest $m\in\mathbb{N}$ such that
$j\leq 2^{m}$ and in view of
$\mathcal{C}_{j}(x)=\mathcal{C}_{2^{m}}(j2^{-m}x)$, $j\leq 2^{m}$, see that
the following holds.

######  Lemma 4.3.

Let $j\in\mathbb{N}$. Then, restricted to $[0,1]$,

$\mathcal{C}_{j}\in\Upsilon^{2,\lceil\log_{2}j\rceil+1}\quad\text{and}\quad\mathcal{S}_{j}\in\Upsilon^{2,\lceil\log_{2}j\rceil+2}$

and all the entries of weight matrices and the bias vectors are bounded by 8.

This was already observed in the proof of [7, Theorem 6.2]. We now provide a
multivariate version of Lemma 4.3.

######  Lemma 4.4.

Let $d>1$ and $\alpha\in\mathbb{Z}^{d}\setminus\\{0\\}$. Then, restricted to
$x\in[0,1]^{d}$,

$\mathcal{C}(\alpha\cdot
x)\in\Upsilon^{2,\lceil\log_{2}\|\alpha\|_{1}\rceil+2}\quad\text{and}\quad\mathcal{S}(\alpha\cdot
x)\in\Upsilon^{2,\lceil\log_{2}\|\alpha\|_{1}\rceil+3},$

where $\|\alpha\|_{1}=|\alpha_{1}|+\ldots+|\alpha_{d}|$. Also in this case,
the weights and biases are bounded by 8.

###### Proof.

We first extend the functions $\mathcal{C}_{2^{m}}$, $\mathcal{S}_{2^{m}}$
from $[0,1]$ to the interval $[-1,1]$ by putting

$\tilde{\mathcal{C}}_{2^{m}}(x):=\mathcal{C}_{2^{m+1}}\left(\frac{x+1}{2}\right),\quad
x\in[-1,1],$

and deduce that $\tilde{\mathcal{C}}_{2^{m}}\in\Upsilon^{2,m+2}$. Let now
$x\in[0,1]^{d}$, then from $\alpha\cdot
x=\alpha_{1}x_{1}+\ldots+\alpha_{d}x_{d}$ we get

$\alpha\cdot x\in\big{[}-\|\alpha\|_{1},\|\alpha\|_{1}\big{]}.$

Moreover, using the fact that $\mathcal{C}(\alpha\cdot
x)=\tilde{\mathcal{C}}_{2^{m}}(2^{-m}\alpha\cdot x)$, we choose
$m:=\lceil\log_{2}\|\alpha\|_{1}\rceil$ and obtain

$2^{-m}\alpha\cdot
x\in\left[-\frac{\|\alpha\|_{1}}{2^{m}},\frac{\|\alpha\|_{1}}{2^{m}}\right]\subset[-1,1],$

which implies $\mathcal{C}(\alpha\cdot
x)\in\Upsilon^{2,\lceil\log_{2}\|\alpha\|_{1}\rceil+2}$. The result for
$\mathcal{S}(\alpha\cdot x)$ follows by similar considerations. ∎

######  Remark 4.5.

Let us point out that we only have an implicit dependence of the length $L$ of
our approximating neural network on the dimension $d$ (which is displayed by
the fact that it logarithmically depends on the $\ell_{1}$-norm of $\alpha$).

Finally, using Lemma 4.4 we obtain a multivariate analogue of [7, Theorem
6.2], where it was shown that one can reproduce linear combinations of
$\mathcal{C}_{k}$ and $\mathcal{S}_{k}$ via $\mathrm{ReLU}$ networks with a
good control of the depth $L$.

######  Theorem 4.6.

Let $d\geq 1$ and let $k,l\geq 0$ be integers with $k+l\geq 1$. Let
$\\{\alpha_{1},\dots,\alpha_{k},\beta_{1},\dots,\beta_{l}\\}\subset\mathbb{Z}^{d}\setminus\\{0\\}$.
Then the function

$f(x)=\sum_{i=1}^{k}a_{i}\mathcal{C}(\alpha_{i}\cdot
x)+\sum_{j=1}^{l}b_{j}\mathcal{S}(\beta_{j}\cdot x),\quad x\in[0,1]^{d}$

belongs to $\Upsilon^{W,L}$ with

$W=2(k+l)\quad\text{and}\quad L=\max_{\begin{subarray}{c}i=1,\ldots,k;\\\
j=1,\ldots,l\
\end{subarray}}\\{\lceil\log_{2}(\|\alpha_{i}\|_{1})\rceil+2,\lceil\log_{2}(\|\beta_{j}\|_{1})\rceil+3\\}$

and the weights and biases in this network are bounded by
$\max_{\begin{subarray}{c}i=1,\ldots,k;\\\
j=1,\ldots,l\end{subarray}}\\{8|a_{i}|,8|b_{j}|,8\\}$.

###### Proof.

By Proposition 4.2 (ii) and Lemma 4.4, $\mathcal{C}(\alpha_{i}\cdot
x)\in\Upsilon^{2,L}$ and $\mathcal{S}(\beta_{j}\cdot x)\in\Upsilon^{2,L}$ for
every $i=1,\dots,k$ and $j=1,\dots,l$ if we restrict $x$ to $[0,1]^{d}$. By
Definition 4.1 we have the corresponding representations for $x\in[0,1]^{d}$
and all admissible $i$’s and $j$’s

$\displaystyle\mathcal{C}(\alpha_{i}\cdot x)$
$\displaystyle=A_{i}^{(L)}\circ\operatorname{ReLU}\circ
A_{i}^{(L-1)}\circ\cdots\circ\operatorname{ReLU}\circ A_{i}^{(0)}(x)$ (34) and
$\displaystyle\mathcal{S}(\beta_{j}\cdot x)$
$\displaystyle=B_{j}^{(L)}\circ\operatorname{ReLU}\circ
B_{j}^{(L-1)}\circ\cdots\circ\operatorname{ReLU}\circ B_{j}^{(0)}(x).$ (35)

If $z=(z_{1},\dots,z_{n})$ is a vector in $\mathbb{R}^{n}$ and $1\leq u<v\leq
n$ are integers, then we denote by $z_{u,v}=(z_{u},z_{v})$ the restriction of
$z$ to the set $\\{u,v\\}$. Furthermore, we denote
$x^{(0)}=(x_{1},\dots,x_{d})$ and stack the networks (34) and (35) on top of
each other. In this way, we obtain a series of intermediate vectors
$x^{(1)},\dots,x^{(L)}\in\mathbb{R}^{W}$

$\displaystyle x^{(1)}$
$\displaystyle=\operatorname{ReLU}\begin{bmatrix}A_{1}^{(0)}x^{(0)}&\dots&A^{(0)}_{k}x^{(0)}&B_{1}^{(0)}x^{(0)}&\dots&B^{(0)}_{l}x^{(0)}\end{bmatrix}^{T},$
$\displaystyle x^{(2)}$
$\displaystyle=\operatorname{ReLU}\begin{bmatrix}A_{1}^{(1)}x_{1,2}^{(1)}&\dots&A^{(1)}_{k}x_{2k-1,2k}^{(1)}&B_{1}^{(1)}x_{2k+1,2k+2}^{(1)}&\dots&B^{(1)}_{l}x_{2k+2l-1,2k+2l}^{(1)}\end{bmatrix}^{T},$
$\displaystyle\vdots$ $\displaystyle x^{(L)}$
$\displaystyle=\operatorname{ReLU}\begin{bmatrix}A_{1}^{(L-1)}x_{1,2}^{(L-1)}&\dots&A^{(L-1)}_{k}x_{2k-1,2k}^{(L-1)}&B_{1}^{(L-1)}x_{2k+1,2k+2}^{(L-1)}&\dots&B^{(L-1)}_{l}x_{2k+2l-1,2k+2l}^{(L-1)}\end{bmatrix}^{T}.$

Finally, the result follows by observing that

$y=f(x)=\sum_{i=1}^{k}a_{i}A_{i}^{(L)}x^{(L)}_{2i-1,2i}+\sum_{j=1}^{l}b_{j}B_{j}^{(L)}x^{(L)}_{2j-1+2k,2j+2k},$

see Figure 8.

Figure 8: Feed-forward ReLU network producing $y=f(x)$

Since by Lemma 4.4, all the weights and biases used in the calculation of
$x^{(1)},\dots,x^{(L)}$ are bounded by 8, the weights in the last step are
then bounded by $\max_{i=1,\dots,k}8|a_{i}|$ and $\max_{j=1,\dots,l}8|b_{j}|$,
respectively. ∎

Acknowledgment: We would like to thank the authors of [7] for their kind
permission to re-use some of their figures. We also thank Dorothee Haroske
(FSU Jena, Germany) for her hospitality during our stay in Jena, where part of
the work took place.

## References

  * [1] H. Bölcskei, P. Grohs, G. Kutyniok, and P. Petersen, _Optimal approximation with sparsely connected deep neural networks_ , SIAM J. Math. Data Sci. 1 (2019), no. 1, 8–45.
  * [2] A. Bourouihiya, _The tensor product of frames_ , Sampl. Theory Signal Image Process. 7 (2008), no. 1, 65–76.
  * [3] P. Beneventano, P. Cheridito, R. Graeber, A. Jentzen, and B. Kuckuck, _Deep neural network approximation theory for high-dimensional functions_ , available at arXiv:2112.14523.
  * [4] O. Christensen, _Frames and projection method_ , Appl. Comput. Harmon. Anal. 1 (1993), 50–53.
  * [5] O. Christensen, _Frames containing a Riesz basis and approximation of the frame coefficients using finite dimensional methods_ , J. Math. Anal. Appl. 199 (1996), 256–270.
  * [6] O. Christensen, An introduction to frames and Riesz bases, Applied and Numerical Harmonic Analysis. Birkhäuser Boston, Inc., Boston, MA, 2003.
  * [7] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, and G. Petrova, _Nonlinear Approximation and (Deep) ReLU Networks_ , Constr. Appr. 55 (2022), 127–172.
  * [8] R. DeVore, B. Hanin, and G. Petrova, _Neural network approximation_ , Acta Numer. 30 (2021), 327–444.
  * [9] D. Dung and V. K. Nguyen, _Deep ReLU neural networks in high-dimensional approximation_ , Neural Netw. 142 (2021), 619–635.
  * [10] D. Elbrächter, D. Perekrestenko, P. Grohs, and H. Bölcskei, _Deep neural network approximation theory_ , IEEE Trans. Inform. Theory 67 (2021), no. 5, 2581–2623.
  * [11] A. Graves, A.-R. Mohamed, and G. E. Hinton, _Speech recognition with deep recurrent neural networks_ , In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) (2013), 6645–6649.
  * [12] R. Gribonval, G. Kutyniok, M. Nielsen, and F. Voigtlaender, _Approximation spaces of deep neural networks_ , Constr. Approx. 55 (2022), no. 1, 259–367
  * [13] K. Gröchenig, Foundations of time-frequency analysis, Applied and Numerical Harmonic Analysis, Birkhäuser Boston, Inc., Boston, MA, 2001.
  * [14] R. A. Horn and C. R. Johnson, Matrix analysis, Cambridge University Press, Cambridge, 1985.
  * [15] H. O. Kim and J. K. Lim, _New characterizations of Riesz bases_ , Appl. Comput. Harmon. Anal. 4 (1997), no. 2, 222–229.
  * [16] A. Krizhevsky, I. Sutskever, and G. E. Hinton, _Imagenet classification with deep convolutional neural networks_ , In: Advances in Neural Information Processing Systems (NIPS) (2012), 1–9.
  * [17] M. Moravčík, M. Schmid, N. Burch, V. Lisý, D. Morrill, N. Bard, T. Davis, K. Waugh, M. Johanson, and M. Bowling, _Deepstack: Expert-level artificial intelligence in heads-up no-limit poker_ , Science 356, no. 6337 (2017), 508–513.
  * [18] P. Petersen and F. Voigtlaender, _Optimal approximation of piecewise smooth functions using deep ReLU neural networks_ , Neural Netw. 108 (2018), 296–330.
  * [19] T. Poggio, H. Mhaskar, L. Rosasco, B. Miranda, Q. Liao, _Why and when can deep-but dot shallow- networks avoid the curse of dimensionality: a review_ , Int. J. Autom. Comput. 14 (2017), no. 5, 503–519.
  * [20] J. Schmidt-Hieber, _Nonparametric regression using deep neural networks with ReLU activation function_ , Ann. Statist. 48 (2020), no. 4, 1875–1897.
  * [21] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser et al., _Mastering the game of Go with deep neural networks and tree search_ , Nature 529, no. 7587 (2016), 484–489.
  * [22] M. Telgarsky, _Representation benefits of deep feedforward networks_ , available at arXiv 1509.08101.
  * [23] E. C. Titchmarsh, The theory of the Riemann zeta-function, The Clarendon Press, Oxford University Press, New York, 1986.
  * [24] Y. Wu, M. Schuster, Z. Chen, Q. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, et al., _Google’s neural machine translation system: Bridging the gap between human and machine translation_ , available at arXiv:1609.08144.
  * [25] D. Yarotsky, _Error bounds for approximations with deep ReLU networks_ , Neural Netw. 94 (2017), 103–114.
  * [26] R. M. Young, An introduction to nonharmonic Fourier series, Pure and Applied Mathematics 93, Academic Press, Inc., New York-London, 1980.