# Neural Network Approximation of Refinable Functions

Ingrid Daubechies, Ronald DeVore, Nadav Dym, Shira Faigenbaum-Golovin, Shahar
Z. Kovalsky,
Kung-Ching Lin, Josiah Park, Guergana Petrova, Barak Sober This research was
supported by the NSF grants DMS 18-17603 (RD-GP), Tripods Grant CCF-1934904
(RD-KL-JP-GP), ONR Contract N00014-20-1-278 (RD-GP), THEORINET Simons award
814643 (ND).

###### Abstract

In the desire to quantify the success of neural networks in deep learning and
other applications, there is a great interest in understanding which functions
are efficiently approximated by the outputs of neural networks. By now, there
exists a variety of results which show that a wide range of functions can be
approximated with sometimes surprising accuracy by these outputs. For example,
it is known that the set of functions that can be approximated with
exponential accuracy (in terms of the number of parameters used) includes, on
one hand, very smooth functions such as polynomials and analytic functions
(see e.g. [9, 11, 13]) and, on the other hand, very rough functions such as
the Weierstrass function (see e.g. [10, 4]), which is nowhere differentiable.
In this paper, we add to the latter class of rough functions by showing that
it also includes refinable functions. Namely, we show that refinable functions
are approximated by the outputs of deep ReLU networks with a fixed width and
increasing depth with accuracy exponential in terms of their number of
parameters. Our results apply to functions used in the standard construction
of wavelets as well as to functions constructed via subdivision algorithms in
Computer Aided Geometric Design.

##  1 Introduction

Neural Network Approximation (NNA) is concerned with how efficiently a
function, or a class of functions, is approximated by the outputs of neural
networks. One overview of NNA is given in [7] but there are other noteworthy
expositions on this subject such as [10, 12]. The main theme of NNA is to
understand for specific functions, or classes of functions, how fast the
approximation error tends to zero as the number $n$ of parameters of the
neural net grows. In this paper, we prove bounds on the rate of NNA for
univariate refinable functions (see (1.2)) when using deep networks with ReLU
activation.

We follow the notation and use the results in [7] for neural networks. In
particular, we denote by $\Upsilon^{W,L}({\rm ReLU};d,N)$ the set of outputs
of a fully-connected neural network with width $W$, depth $L$, input dimension
$d$, output dimension $N$, and the Rectified Linear Unit (ReLU) as the
activation function. Since we shall use deep networks for the approximation of
univariate functions, we introduce the notation

$\Sigma_{n}:={\Sigma_{n}(C^{\prime},C):=\Upsilon^{C^{\prime},Cn}}({\rm
ReLU};1,1),\quad n\geq 1,$ (1.1)

where $C^{\prime}$ and $C$ are fixed. The set $\Sigma_{n}$ is a nonlinear
parameterized set depending on at most $\tilde{C}n$ parameters, where
$\tilde{C}=\tilde{C}(C^{\prime},C)$ depends only on $C^{\prime}$ and $C$. The
elements in $\Sigma_{n}$ are known to be Continuous Piecewise Linear (CPwL)
(vector valued) functions on $\mathbb{R}$. While each $S\in\Sigma_{n}$ is
determined by ${\cal O}(n)$ parameters, the number of breakpoints of a given
$S$ may be exponential in $n$. However, as shown in [8], not all CPwL
functions with an exponential number of breakpoints are in $\Sigma_{n}$, and
indeed, the membership of $S$ in $\Sigma_{n}$ imposes strong dependencies
between the linear pieces.

We consider a univariate function $\phi:\mathbb{R}\to\mathbb{R}$ which is
refinable in the sense that there are constants $c_{j}\in\mathbb{R}$,
$j=0,\dots,N$, such that

$\phi(x)=\sum_{j=0}^{N}c_{j}\phi(2x-j),\quad x\in\mathbb{R}.$ (1.2)

The sequence $\bar{c}:=(c_{j})_{j=0}^{N}$ is called the mask of the refinement
equation (1.2). Because of (1.2), refinable functions $\phi$ are self-similar.
Note that the functions satisfying (1.2) are not unique since, for example,
any multiple of $\phi$ also satisfies the same equation. However, under very
minimal requirements on the mask $\bar{c}$, there is a unique solution to
(1.2) up to scaling.

There is by now a vast literature on refinable functions (see for example [1])
which derives various properties of the function $\phi$ from assumptions on
the mask $\bar{c}$. In our presentation, we describe our assumptions as
properties imposed on $\phi$ and thus, if the reader wishes to know which
properties of the mask will guarantee our assumptions, they must refer to the
existing literature, in paricular [1, 5, 6].

Refinable functions are of particular interest in approximation theory because
they provide the natural framework for every practical wavelet basis in which
the basic wavelets have bounded support. One and several dimensional refinable
functions are also the underlying mathematical constructs in subdevision
schemes used in Computer Aided Geometric Design (CAGD).

We rely heavily on the results and techniques from [5, 6]. To keep our
presentation as transparent as possible, we only consider refinable functions
that satisfy the two scale relationship (1.2). There are various
generalizations of (1.2), including the replacement of the dilation factor $2$
by $k$ as well as generalizations of the definition of refinablity to the
multivariate settings where the dilation is given by general linear mappings
(matrices). Generalizations of the results of the present paper to these
broader settings is left to future work.

We next introduce the Banach space $C(\Omega)$ of continuous and bounded
functions $f:\Omega\to\mathbb{R}$, defined on an interval
$\Omega\subset\mathbb{R}$ (which can be all of $\mathbb{R}$), and the uniform
norm

$\|f\|_{C(\Omega)}:=\sup_{x\in\Omega}|f(x)|,\quad f\in C(\Omega).$ (1.3)

We consider the linear operator $V=V_{\bar{c}}$ , $V:C(\mathbb{R})\to
C(\mathbb{R})$, given by

$Vg(x):=\sum_{j=0}^{N}c_{j}g(2x-j),\quad g\in C(\mathbb{R}),$ (1.4)

and its composition with itself $n$ times

$V^{n}g:=\underbrace{V\circ V\circ\ldots\circ V}_{n\ \text{{\rm times}}}g.$
(1.5)

The main contribution of our article is described formally in the following
theorem.

######  Theorem 1.1.

Let $\bar{c}=(c_{j})_{j=0}^{N}$ be any refinement mask, let $g$ be any CPwL
function which vanishes outside of $[0,N]$, and let $V$ be the linear operator
of (1.4). Then, the function $V^{n}g$ is in
$\Sigma_{n}=\Upsilon^{C^{\prime},Cn}({\rm ReLU};1,1)$ with $C,C^{\prime}$
depending only on $N$ and the number $m$ of breakpoints of $g$.

As a corollary, under certain standard assumptions on $\bar{c}$, we show in
Section 4 that a refinable function $\phi$ can be approximated by the elements
of $\Upsilon^{C^{\prime},Cn}({\rm ReLU};1,1)$ with exponential accuracy. More
precisely, we prove that under certain assumptions on the mask $\bar{c}$, the
normalized solution $\phi$ of (1.2) satisfies the following for $n=1,2,\dots$

$E_{n}(\phi):=\mathop{\rm dist}(\phi,\Upsilon^{C^{\prime},Cn}({\rm
ReLU};1,1))_{C(\mathbb{R})}\leq\tilde{C}\lambda^{n},$ (1.6)

where $0<\lambda<1$ and $\tilde{C}$ depend on the mask.

Our main vehicle for proving these results is the cascade algorithm which is
used to compute $V^{n}g$. We describe this algorithm in Section 2. Note that
in [5] the term cascade algorithm was used more narrowly to indicate that as a
consequence of (1.2), the numerical values of $f(\ell 2^{-j})$ could be
computed easily from a few $f(k2^{-j+1})$, where $2k$ is close to $\ell$. Now
we are using this terminology in a more general sense, including also what in
[5] was given the more cumbersome name of two-scale difference equation.
Notice that the cascade algorithm cannot be directly implemented by ReLU NNs
and so various modifications in this algorithm need to be made. These are
given in the proofs of the theorem as portrayed in Section 3.

We wish to stress here that some of the lemmas we use in our proofs may be
applicable to other settings of NNA. In particular, we draw the reader’s
attention to the result of §3.3 and its utilization, which show that in some
cases we can describe a multiplication of two functions from $\Sigma_{n}$ as a
function in $\Sigma_{n}$.

It is well-known that the solutions to refinement equations are used in the
construction of wavelets with compact support (see [3]) and in subdivision
algorithms in CAGD. In Section 4, we discuss how our main theorem can be
combined with the existing theory of refinable functions and the existing
convergence results for the cascade algorithm to prove that under standard
conditions on $\bar{c}$, the solution $\phi$ to the refinement equation can be
approximated to exponential accuracy by the elements of $\Sigma_{n}$. Finally,
in Section 5, we discuss how our results relate to $n$-term wavelet
approximation.

##  2 Preliminaries

In this section, we touch upon some of the necessary tools that describe the
cascade algorithm as outlined in the works of Daubechies-Lagarias [5, 6].

###  2.1 The operator $V$

We consider the action of $V$ on any continuous function $g$ supported on
$[0,N]$. It is hard to do a direct analysis of $Vg$ because the points $2x-j$,
$j=0,\dots,N$, are spread out. However, note two important facts. The first is
that the points appearing in (1.4) are all equal to $2x$ modulo one. This
means that there is at most one point from each interval $[j,j+1]$ and all
these points differ by an integer amount. Secondly, since $g$ is supported on
$[0,N]$, only the points $2x-j$ that land in $[0,N]$ appear in (1.4). More
precisely, the following statement about $Vg$ holds.

######  Remark 2.1.

If $g:\mathbb{R}\to\mathbb{R}$ is a CPwL function supported on $[0,N]$, then
$Vg$ is also a CPwL supported on $[0,N]$. Moreover, each breakpoint
$\xi^{\prime}$ of $Vg$ satisfies $2\xi^{\prime}=j+\xi$, $j=0,\ldots,N$, where
$\xi$ is a breakpoint of $g$. In particular, given a CPwL function $g_{0}$
supported on $[0,N]$ with breakpoints at the integers $\\{0,\dots,N\\}$,
$V^{n}g_{0}$ has breakpoints at $j/2^{n}$, $j=0,1,\dots,N2^{n}$.

Indeed, the fact that $Vg$ is supported on $[0,N]$ follows from the
observation that each of the functions $g(2x-j)$, $j=0,\dots,N$, is supported
on $[j/2,(N+j)/2]\subset[0,N]$.

It follows from Remark 2.1 that if $g_{0}$ is a CPwL function supported on
$[0,N]$ and has breakpoints at the integers $\\{0,\dots,N\\}$, then
$V^{n}g_{0}$ is a CPwL supported on $[0,N]$ with breakpoints $j/2^{n}$,
$j=0,1,\dots,N2^{n}$, and as such, $V^{n}g_{0}\in\Upsilon^{3,N2^{n}}({\rm
ReLU};1,1)$. We shall show that $V^{n}g_{0}$ is actually an output of an NN
with much smaller depth.

In going forward, we put ourselves in the setting of the works of Daubechies-
Lagarias [5, 6], where a better understanding of $Vg$ is facilitated by the
introduction of the operator Vec. It assigns to each $g\in C(\mathbb{R})$ a
vector valued function $G:=\text{{\bf Vec}}(g)$, where
$G:=(g_{1},\dots,g_{N})^{T}$ with

$g_{k}(x):=g(x+k-1),\quad x\in\mathbb{R},\ k=1,2,\ldots,N.$ (2.1)

Even though $\text{{\bf Vec}}(g)$ is defined on all of $\mathbb{R}$, we are
mainly concerned with its values on $[0,1]$. Note that the solution $\phi$ of
(1.2) turns out to be supported on $[0,N]$. Therefore, knowing the restriction
to $[0,1]$ of $\text{{\bf Vec}}(\phi)$ is equivalent to knowing $\phi$ on its
full support. On that interval, $g_{k}$ is the piece of $g$ living on
$[k-1,k]$, reparameterized to live on $[0,1]$. Note that

$g_{k}(1)=g_{k+1}(0),\quad k=1,\ldots,N-1.$ (2.2)

Further, we define for $x\in\mathbb{R}$ and $n\geq 1$

$G_{n}(x):=\text{{\bf Vec}}(V^{n}g)(x):=(V^{n}g(x),\dots,V^{n}g(x+N-1))^{T},$
(2.3)

Before describing the cascade algorithm which represents $G_{n}$ via bit
extraction, we recall in the next subsection how we find the binary bits of a
number $x\in[0,1]$.

###  2.2 Binary bits and quantization

Any $x\in[0,1]$, can be represented as

$x=\sum_{k=1}^{\infty}B_{k}(x)2^{-k},$

where the bits $B_{k}(x)\in\\{0,1\\}$. While such a representation of $x$ is
not unique, we shall use one particular representation where the bits are
found using the quantizer function

$Q(x):=\chi_{[1/2,1]}(x),\quad x\in[0,1],$

with $\chi_{I}$ denoting the characteristic function of a set $I$. The first
bit of $x$ and its residual are defined as

$\begin{split}B_{1}(x)&=Q(x),\\\ R(x):&=R_{1}(x):=2x-B_{1}(x)\\\
&=2x-Q(x)\in[0,1],\end{split}$ (2.4)

respectively. The graph of $R$ has two linear pieces, one on $[0,1/2)$ and the
other on $[1/2,1]$ and a jump discontinuity at $x=1/2$. Each linear piece for
$R$ has slope $2$.

While for the most part we consider $R(x)$ only for $x\in[0,1]$, there are
occasions where we need $R$ to be defined for $x$ outside this interval. For
such $x$, we define $R(x):=0$ when $x\leq 0$ and $R(x):=1$ when $x\geq 1$.
Figure 2.1 shows the graphs of $Q$ and $R$.

(a) The graph of $Q$.

(b) The graph of $R$.

Figure 2.1: The graphs of $Q$ and $R$.

We find the later bits and residuals recursively as

$\begin{split}B_{j}(x)&=Q(R_{j-1}(x)),\\\ R_{j}(x):&=2R_{j-1}(x)-B_{j}(x)\\\
&=2R_{j-1}(x)-Q(R_{j-1}(x)),\quad j=2,3,\ldots.\end{split}$ (2.5)

Note that on $[0,1]$

$R^{j}:=\underbrace{R\circ\ldots\circ R}_{j\text{\,\,{\rm times}}}=R_{j},\quad
B_{j+1}=B_{1}\circ R^{j},\quad j=1,2,\ldots.$ (2.6)

The $R_{j}$’s are piecewise linear functions with jump discontinuities at the
dyadic integers $k2^{-j}$, $k=1,2,\ldots,2^{j}-1$, see for example, Figure 2.2
for the graph of $R^{3}=R_{3}$. Note that, as in the case of $R_{1}$, we
define $R_{j}(x):=0$ for $x\leq 0$ and $R_{j}(x):=1$ for $x\geq 1$. Then we
will have that $R^{j}=R_{j}$ on the whole real line.

Figure 2.2: Graph of $R^{3}$.

###  2.3 The cascade algorithm

We now look at the computation of $G_{1}=((Vg)_{1},\dots,(Vg)_{N})^{T}$ on
$[0,1]$ for general continuous functions $g$ supported on $[0,N]$. Since for
$x\in[0,1]$, and $k=1,\ldots,N$ we have

$\begin{split}(Vg)_{k}(x):&=(Vg)(x+k-1)\\\
&=\sum_{j=0}^{N}c_{j}g(2x+2k-2-j),\end{split}$ (2.7)

we can write

$\begin{split}g(2x+2k-j-2)&=g(R(x)+Q(x)+2k-j-2)\\\
&=\begin{cases}g_{2k-j-1}(R(x)),\quad x\in[0,1/2),\\\ \\\
g_{2k-j}(R(x)),\quad\quad x\in[1/2,1].\end{cases}\end{split}$ (2.8)

In this way, we get two different formulas depending on whether $x\in[0,1/2)$
or $x\in[1/2,1]$. For example, when $x\in[0,1/2)$, using the fact that
$c_{k}=0$ if $k$ is not in $\\{0,\dots,N\\}$ and that $g_{j}(x):=g(x+j-1)=0$
for $x\in[0,1]$ when $j\leq 0$ or $j\geq N+1$, we have for $k=1,\ldots,N$,

$\begin{split}(Vg)_{k}(x)&=\sum_{j=0}^{N}c_{j}g_{2k-j-1}(R(x))\\\
&=\sum_{j=2k-N-1}^{2k-1}c_{2k-j-1}g_{j}(R(x))\\\ &=(T_{0}G(R(x)))_{k},\quad
x\in[0,1/2),\end{split},$

where $T_{0}$ is the $N\times N$ matrix with $(i,j)$-th entry equal to
$c_{2i-j-1}$,

$T_{0}=(c_{2i-j-1})_{ij},\quad i,j=1,\ldots,N.$ (2.9)

A similar derivation gives

$(Vg)_{k}(x)=(T_{1}G(R(x)))_{k},\quad x\in[1/2,1],\quad k=1,\ldots,N,$

where now $T_{1}$ is the $N\times N$ matrix with $(i,j)$-th entry equal to
$c_{2i-j}$,

$T_{1}=(c_{2i-j})_{ij},\quad i,j=1,\ldots,N.$ (2.10)

More succinctly, we have for $x\in[0,1]$

$G_{1}(x)=\text{{\bf Vec}}(Vg)(x)=T_{Q(x)}G(R(x))=T_{B_{1}(x)}G(R(x)).$ (2.11)

Then, using (2.5) we get

$\displaystyle G_{2}(x)$ $\displaystyle=$ $\displaystyle\text{{\bf
Vec}}(V(Vg))(x)$ $\displaystyle=$ $\displaystyle T_{B_{1}(x)}\text{{\bf
Vec}}(Vg)(R(x))$ $\displaystyle=$ $\displaystyle
T_{B_{1}(x)}T_{B_{1}(R(x))}G(R^{2}(x))$ $\displaystyle=$ $\displaystyle
T_{B_{1}(x)}T_{B_{2}(x)}G(R^{2}(x)),\quad x\in[0,1],$

and if we iterate this computation we get the cascade algorithm. Since
$B_{1}(R^{j}(x))=B_{j+1}(x)$, we have for $x\in[0,1],\ n=1,2,\dots$

$G_{n}(x)=T_{B_{1}(x)}\cdots T_{B_{n}(x)}G(R^{n}(x)).$ (2.13)

It is useful to keep in mind what $T_{B_{n}(x)}$ looks like as $x$ traverses
$[0,1]$. It alternately takes the values $T_{0}$ and $T_{1}$ with the switch
coming at the dyadic integers $j2^{-n}$, $1\leq j<2^{n}$.

##  3 Proof of the main theorem

Before we start proving Theorem 1.1, we observe a simple fact regarding how
$V^{n}$ behaves with respect to the translation operator. This fact, which is
described in the following lemma, will help us simplify the proof of Theorem
1.1.

######  Lemma 3.1.

Let $g$ be a continuous function on $\mathbb{R}$ and for any $\delta$,
consider the translated function

$\tilde{g}(\cdot):=g(\cdot-\delta).$

Then, for each $n\geq 1$,

$V^{n}(g)(x)=[V^{n}(\tilde{g})](x+2^{-n}\delta),\quad x\in\mathbb{R}.$ (3.1)

Proof: Let us first see the action of $V$ on $g$. Since
$g(x)=\tilde{g}(x+\delta)$, we have

$\displaystyle Vg(x)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{N}c_{k}g(2x-k)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{N}c_{k}\tilde{g}(2x-k+\delta)$ $\displaystyle=$
$\displaystyle\sum_{k=0}^{N}c_{k}\tilde{g}(2(x+\delta/2)-k)$ $\displaystyle=$
$\displaystyle[V\tilde{g}](x+\delta/2).$

This proves the case $n=1$ in (3.1). We next complete the proof of (3.1) for
all $n\geq 1$ by induction. Suppose that we have established the result for a
given value of $n$. Consider the function $h:=V^{n}(g)$. Formula (3.1) says
that $\overline{h}:=V^{n}(\tilde{g})$ satisfies

$\overline{h}(x)=h(x-2^{-n}\delta),\quad x\in\mathbb{R}.$ (3.3)

So we can apply (3) with $h$ in place of $g$ and obtain

$\displaystyle V^{n+1}g(x)$ $\displaystyle=$ $\displaystyle V(h)(x)$
$\displaystyle=$ $\displaystyle V(\overline{h})(x+2^{-n-1}\delta)$
$\displaystyle=$ $\displaystyle V^{n+1}(\tilde{g})(x+2^{-n-1}\delta).$

This advances the induction and proves (3.1). $\Box$

We turn now to discuss the proof of Theorem 1.1. We first show how to prove
the theorem when $g=g_{0}$, where $g_{0}$ is any CPwL function that has
support in $[0,N]$ and has breakpoints at the integers. We make this
assumption on the breakpoints $g$ only for transparency of the proof. We
remark later how the same method of proof gives the theorem for arbitrary CPwL
functions $g$.

We represent $g_{0}$ as a linear combination of hat functions each of which
has a translate with support in $[1/8,7/8]$. The fact that these functions are
supported on this sub-interval will be pivotal in many of the lemmas and
theorems below and we will therefore use the following terminology throughout
the paper. We call a univariate function $g$ special if:

  * •

$g$ is a non-negative CPwL function defined on $\mathbb{R}$.

  * •

the support of $g\subset[1/8,7/8].$

Therefore, the translates of the hat functions in the representation of $g$
are special functions and all our results below, proven for special functions,
can be applied to these translates.

Let $H$ be the ’hat function’ with break points at $\\{3/8,1/2,5/8\\}$ and
$H(\frac{1}{2})=1$, see Figure 3.3. That is, $H$ is given by the formula

$\displaystyle H(x)=\begin{cases}0,\quad\quad\quad\quad
x\leq\frac{3}{8},\,\,x\geq\frac{5}{8},\\\ 8x-3,\quad\quad\frac{3}{8}\leq
x\leq\frac{1}{2},\\\ -8x+5,\quad\frac{1}{2}\leq x\leq\frac{5}{8}.\end{cases}$
(3.4)

Figure 3.3: The graph of ${H}:=H_{4}$.

Clearly $H$ is a special function with $m=3$ break points. Although the
function under investigation $g_{0}$ is not special, it can be written as a
linear combination of shifts of the special function $H$,

$g_{0}(x)=\sum_{j=1}^{8N-1}g_{0}(j/8)H_{j}(x),\quad
H_{j}(\cdot):=H(\cdot-\frac{j-4}{8}).$ (3.5)

Therefore, from (3.5), Lemma 3.1 and the fact that $V^{n}$ is a linear
operator it follows that

$\displaystyle V^{n}g_{0}(x)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{8N-1}g_{0}(j/8)V^{n}(H(\cdot-\frac{j-4}{8}))(x)$
(3.6) $\displaystyle=$
$\displaystyle\sum_{j=1}^{8N-1}g_{0}(j/8)V^{n}H(x-2^{-n-3}(j-4)).$

Accordingly, the discussion in the following subsections concentrate on
special functions. We will come back to finalize the proof of the main theorem
in the closing subsection.

###  3.1 The function $g(R^{n})$ is an output of an NN for special functions
$g$

In this section, we shall show that for certain choices of $g$, the function
$g(R^{n})$ is in the set $\Upsilon^{C,n+1}({\rm ReLU};1,1)$, where $C$ depends
only on the mask $\bar{c}$ and the function $g$. If $g$ is a special function,
then the corresponding vector function $G$, viewed as a function on $[0,1]$,
is

$G=\text{{\bf Vec}}(g)=(g,0,\ldots,0)^{T}.$

Namely, all its coordinates are zero except the first one, which is the
nonzero function $g$ supported on $[1/8,7/8]$. Therefore
$G(R^{n}(x))=(g(R^{n}(x)),0,\ldots,0)^{T}$, when considered as a function on
$[0,1]$, and is the zero vector when $R^{n}(x)$ takes a value outside
$[1/8,7/8]$. Since the formula for $R^{n}$ is $R^{n}(x)=2^{n}x-k$ on
$[k2^{-n},(k+1)2^{-n}]$, $0\leq k<2^{n}$, this gives

$g(R^{n}(x))=0,\quad x\in\Lambda,$ (3.7)

where

$\Lambda:=[0,1]\cap\bigcup_{0\leq j\leq
2^{n}}[j2^{-n}-2^{-n-3},j2^{-n}+2^{-n-3}].$

In particular, the support of $g(R^{n}(x))$ is contained in
$[2^{-n-3},1-2^{-n-3}]$.

The first step in our argument to prove that $g(R^{n})$ is an output of an NN
is to replace the discontinuous functions $R^{j}$ by the CPwL function
$\hat{R}^{j}:=\hat{R}^{j}_{\alpha,\beta}$. We shall give a family of possible
replacements which depend on the choice of two parameters $\alpha,\beta$
satisfying

$7/16<\alpha<\beta<1/2.$ (3.8)

Definition of $\hat{R}_{\alpha,\beta}$: We let
$\hat{R}:=\hat{R}_{\alpha,\beta}$ be the CPwL function defined on
$\mathbb{R}$, see Figure 3.4(a), with breakpoints at
$\\{0,\alpha,\beta,1/2,1\\}$ which satisfies:

  * •

$\hat{R}(x)=0$, $x\leq 0$;

  * •

$\hat{R}(x)=R(x)$, for $0\leq x\leq\alpha$ and for $x\geq 1/2$;

  * •

on $[\alpha,\beta]$, $\hat{R}$ is the linear function that interpolates
$R(\alpha)$ at $\alpha$ and interpolates $0$ at $\beta$;

  * •

$\hat{R}(x)=0$ on $[\beta,1/2]$.

In the next lemma, we summarize the properties of
$\hat{R}^{n}:=\underbrace{\hat{R}\circ\ldots\circ\hat{R}}_{n\text{\,\,{\rm
times}}}$ that we will need in going forward. For its statement, we introduce
for $\delta:=1/2-\alpha$ the sets

$\displaystyle E_{j}$ $\displaystyle:=$
$\displaystyle\bigcup_{0<i<2^{j}}[i2^{-j}-\delta 2^{-j+1},i2^{-j}],\quad
j=1,2,,\dots,$ $\displaystyle\Omega_{k}$ $\displaystyle:=$
$\displaystyle[0,1]\setminus\bigcup_{j=1}^{k}E_{j},\quad k=1,2,\dots.$ (3.9)

(a) Graph of $\hat{R}_{\alpha,\beta}$.

(b) Graph of $\hat{R}^{4}_{\alpha,\beta}$.

Figure 3.4: The graphs of $\hat{R}_{\alpha,\beta}$ and its composition
$\hat{R}^{4}_{\alpha,\beta}$ for $\alpha=0.42$, $\beta=0.47$.

######  Lemma 3.2.

For each $n\geq 1$, the function $\hat{R}^{n}$ has the following properties:
(i) $\hat{R}^{n}\in\Upsilon^{5,n}({\rm ReLU};1,1)$; (ii)
$\hat{R}^{n}(x)=R^{n}(x)$ for $x\in\Omega_{n}$; (iii) For
$\delta^{\prime}:=1/2-\beta$, we have $\hat{R}^{n}(x)=0$, at least at every
$x\in[k2^{-n}-\delta^{\prime}2^{-n+1},k2^{-n}]$, $0<k<2^{n}$.

Proof: Since $\hat{R}$ is in $\Upsilon^{5,1}({\rm ReLU};1,1)$ we have that the
composition $\hat{R}^{n}$ is in $\Upsilon^{5,n}({\rm ReLU};1,1)$, see page 10
in [7]. This proves (i).

We prove (ii) by induction on $n$. From the definition of $\hat{R}$, we have
that $\hat{R}=R$ except for the interval $E_{1}=[1/2-\delta,1/2]$ and
therefore we have proved the case $n=1$. Suppose we have established (ii) for
a value of $n\geq 1$. Let $x\in\Omega_{n+1}$. Then, $\hat{R}^{n}(x)=R^{n}(x)$
because $\Omega_{n+1}\subset\Omega_{n}$. Therefore, we only need to check that
$\hat{R}(y)=R(y)$ when $y=R^{n}(x)$, $x\in\Omega_{n+1}$. Any such $x$ is in an
interval $[k2^{-n},(k+1)2^{-n}]$ for some $0\leq k<2^{n}$ and
$y=R^{n}(x)=2^{n}x-k$. If $R(y)\neq\hat{R}(y)$ then $y\in[1/2-\delta,1/2]$ and
therefore $x\in E_{n+1}$. Therefore, we have proved (ii).

Finally, we prove (iii) also by induction on $n$. This statement is clear from
the definition of $\hat{R}$ when $n=1$. Suppose that we have proved (iii) for
a value of $n\geq 1$ and consider the statement for $n+1$. We consider two
cases depending on the parity of $k$. If $k=2j$ is even, then the interval
under consideration is $2^{-n-1}[2j-2\delta^{\prime},2j]\subset
2^{-n}[j-2\delta^{\prime},j]$. Hence, we know $\hat{R}^{n}(x)$ vanishes on
this interval and since $\hat{R}(0)=0$, we get that $\hat{R}^{n+1}$ also
vanishes on this interval. Consider now the case that $k=2j+1$. Then, the
interval under consideration is

$\displaystyle 2^{-n-1}[2j+1-2\delta^{\prime},2j+1]$ $\displaystyle=$
$\displaystyle 2^{-n}[j+\beta,j+1/2]\textbf{}$ $\displaystyle\subset$
$\displaystyle 2^{-n}[j,j+2\alpha]$ $\displaystyle\subset$
$\displaystyle\Omega_{n},$

since $\alpha>7/16>1/4$. For $x$ in that interval, because of (ii), we have

$\hat{R}^{n}(x)=R^{n}(x)=2^{n}x-j\in[1/2-\delta^{\prime},1/2].$

Hence, $\hat{R}^{n+1}(x)=\hat{R}(\hat{R}^{n}(x))=0$. $\Box$

######  Remark 3.3.

Note that in addition to the assumption $7/16<\alpha<\beta<1/2$, we require
that $1/2-2^{-n}<\alpha$ so that the sets $E_{j}$, $j=1,\ldots,n$, do not
overlap.

######  Remark 3.4.

In the construction of NNs in this paper, we usually construct NNs whose
layers have different width. However, we can always add additional nodes to
these layers so that we end up with a fully-connected NN with all layers being
the same size.

Now, we are ready to state and prove the main theorem in this section.

######  Theorem 3.5.

Let $g$ be a special function that has at most $m\geq 3$ breakpoints. Then,
for any $n\geq 1$,

$g(R^{n}(x))\in\Upsilon^{2\max\\{m,5\\},n+1}({\rm ReLU};1,1).$

Proof: We choose $7/16<\alpha_{1}<\beta_{1}<\alpha_{2}<\beta_{2}<1/2$. Let us
denote by $\hat{R}_{1}$ the function $\hat{R}_{\alpha_{1},\beta_{1}}$ and
denote by $\hat{R}_{2}:=\hat{R}_{\alpha_{2},\beta_{2}}$. We claim that

$g(R^{n}(x))=\min\\{g(\hat{R}_{1}^{n}(x)),g(\hat{R}^{n}_{2}(x))\\},\quad
x\in\mathbb{R}.$ (3.10)

Let us assume this claim for a moment and proceed to prove the theorem.
Because of (i) in Lemma 3.2, we know that each of the functions
$\hat{R}_{1}^{n},\hat{R}_{2}^{n}$ is in $\Upsilon^{5,n}({\rm ReLU};1,1)$.
Since $g$ is a CPwL function with $m$ breakpoints, we have
$g\in\Upsilon^{m,1}({\rm ReLU};1,1)$. We can output $g(\hat{R}_{1}^{n})$ by
concatenating the networks for $\hat{R}_{1}^{n}$ with that for $g$. Namely, we
place the neural network for $\hat{R}_{1}^{n}$ in the first $n$ layers and
then follow that with the network for $g$ in the last layer using
$\hat{R}_{1}^{n}(x)$ as its input. Thus, $g(\hat{R}_{1}^{n})$ is in
$\Upsilon^{\max\\{m,5\\},n+1}({\rm ReLU};1,1)$. We now place the two neural
networks that output $g(\hat{R}_{1}^{n})$ and $g(\hat{R}_{2}^{n})$ stacked on
top of each other. The resulting network has width $W=2\max\\{m,5\\}$. At the
final step, we recall that

$\min\\{x,y\\}=y_{+}-(-y)_{+}-(y-x)_{+}.$ (3.11)

Therefore, by adding another layer to the network we have already created, we
can output the right side of (3.10). Hence, it is in $\Upsilon^{W,n+2}({\rm
ReLU};1,1)$ with the advertised width $W$.

(a) Graph of the special function $g$.

(b) Graphs of
$\min\\{g(\hat{R}^{n}_{\alpha_{1},\beta_{1}}),g(\hat{R}^{n}_{\alpha_{2},\beta_{2}})\\}$
and $g(R^{n})$ on $[0,1]$

Figure 3.5: Comparison between $g(R^{n})$ and
$\min\\{g(\hat{R}^{n}_{\alpha_{1},\beta_{1}}),g(\hat{R}^{n}_{\alpha_{2},\beta_{2}})\\}$
on $[0,1]$, where
$(\alpha_{1},\beta_{1},\alpha_{2},\beta_{2})=(0.492,0.494,0.496,0.498)$.

With these remarks in hand, we are left with proving the claim. For the proof,
let us first note that (3.10) holds when $x$ is outside $[0,1]$ because
$R^{n}(x)=\hat{R}_{1}^{n}(x)=\hat{R}_{2}^{n}(x)$ outside $[0,1]$. Now,
consider a general $\hat{R}=\hat{R}_{\alpha,\beta}$ and understand what
$g(\hat{R}^{n}(x))$ looks like as $x$ traverses a dyadic interval
$I_{k}:=[k2^{-n},(k+1)2^{-n}]$ from left to right. We will track this behavior
only when $\alpha$ is extremely close to $1/2$, i.e. $\delta=1/2-\alpha$ is
very small; at least $0<\delta\ll 2^{-n}$. From (ii) of Lemma 3.2, we know
that $\hat{R}^{n}(x)=R^{n}(x)$ until $x$ gets close to the right endpoint of
$I_{k}$, and in particular on

$I_{k}\setminus J_{k}(\alpha)\subset\Omega_{n},\hbox{where
}J_{k}(\alpha):=[(k+1)2^{-n}-\delta,(k+1)2^{-n}].$

This means that $g(\hat{R}^{n}(x))=g(R^{n}(x))$ until $x\in J_{k}(\alpha)$. On
$J_{k}(\alpha)$, we have $g\circ\hat{R}^{n}\geq 0$ since $g$ is a special
function (and therefore non-negative). By (iii) of Lemma 3.2,
$\hat{R}^{n}(x)=0$ on

$J_{k}^{\prime}(\beta):=[(k+1)2^{-n}-\delta^{\prime}2^{-n+1},(k+1)2^{-n}]\subset
J_{k}(\alpha),$

where

$\delta^{\prime}:=1/2-\beta,$

and therefore $g\circ\hat{R}^{n}\equiv 0$ on $J_{k}^{\prime}(\beta)$.

Now, we return to our choice of $\alpha_{1},\beta_{1},\alpha_{2},\beta_{2}$.
We first choose the $\alpha_{1}<\beta_{1}$ very close to $1/2$ so that at
least $\delta_{1}:=1/2-\alpha_{1}<2^{-n-3}$, which ensures that

$g\circ R^{n}\equiv 0\quad\hbox{on}\quad
J_{k}(\alpha_{1}):=[(k+1)2^{-n}-\delta_{1},(k+1)2^{-n}]$

because of (3.7). Moreover, it follows from the discussion so far that

$g\circ R^{n}=g\circ\hat{R}_{1}^{n}\quad\hbox{on}\quad I_{k}\setminus
J_{k}(\alpha_{1}).$

For any $\beta_{1}<\alpha_{2}<\beta_{2}<1/2$ we have that $g\circ
R^{n}=g\circ\hat{R}_{1}^{n}=g\circ\hat{R}_{2}^{n}$ on $I_{k}\setminus
J_{k}(\alpha_{1})$, but we choose $\alpha_{2}$ so that

$\delta_{2}:=1/2-\alpha_{2}<\delta_{1}^{\prime}2^{-n+1}:=(1/2-\beta_{1})2^{-n+1}.$

This guarantees that for $x\in J_{k}(\alpha_{1})$ one of the two non-negative
numbers $g(\hat{R}_{1}^{n}(x))$ or $g(\hat{R}_{2}^{n}(x))$ is zero, and thus
we have (3.10). $\Box$

###  3.2 Matrix constructions

In this section, we continue considering special functions $g$ and their
vectorization $G$. Let us introduce the notation

${\mathcal{M}}_{j}(x):=T_{B_{j}(x)},\quad x\in[0,1],\quad j=1,2,\dots,$

for the piecewise constant matrix valued functions $T_{B_{j}(x)}$. Let $T(x)$
be the piecewise constant matrix valued function which is defined as

$\displaystyle T(x)$ $\displaystyle:=$ $\displaystyle\chi_{[0,1/2)}(x)\cdot
T_{0}+\chi_{[1/2,1]}(x)\cdot T_{1}$ (3.12) $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}T_{0},&x<1/2,\\\ T_{1},&x\geq
1/2.\end{array}\right.$ (3.15)

Notice that we have purposefully defined $T$ on all of $\mathbb{R}$. We have

${\mathcal{M}}_{j}(x)=T(R^{j-1}(x)),\quad x\in[0,1],\quad j=1,\ldots,$ (3.16)

if we set

$R^{0}(x):=x,\quad x\in[0,1].$

We know from the cascade algorithm (2.13) that

$G_{n}(x)={\mathcal{M}}_{1}(x)\ldots{\mathcal{M}}_{n}(x)G(R^{n}(x)),\quad
x\in[0,1].$ (3.17)

We next introduce our technique for proving that $G_{n}$ is an output of a
neural network whose depth grows linearly in $n$. In what follows, we derive a
new expression for $G_{n}$ and then use it to prove the existence of such a
neural network. Recall that for a special function $g$,

$G(x)=g(x)e_{1},\quad x\in[0,1],$

where the column vectors $e_{j}\in\mathbb{R}^{N}$, $j=1,\ldots,N$, are the
standard basis for $\mathbb{R}^{N}$. Then (3.17) can be rewritten as

$\displaystyle G_{n}(x)$ $\displaystyle=$
$\displaystyle(\bar{g}_{1}(x),\ldots,\bar{g}_{n}(x))^{T}$ $\displaystyle=$
$\displaystyle{\mathcal{M}}_{1}(x)\ldots{\mathcal{M}}_{n}(x)g(R^{n}(x))e_{1},$

for $x\in[0,1]$, and thus the $k$-th coordinate $\bar{g}_{k}$ of $G_{n}$ is
given by

$\bar{g}_{k}(x)=g(R^{n}(x))e_{k}^{T}{\mathcal{M}}_{1}(x)\cdot\ldots\cdot{\mathcal{M}}_{n}(x)e_{1}.$
(3.18)

Recall that since $g$ is special, see (3.7), we have

$\displaystyle g(R^{n}(x))=0,$ $\displaystyle
x\in\Lambda:=[0,1]\cap\bigcup_{0\leq j\leq
2^{n}}[j2^{-n}-2^{-n-3},j2^{-n}+2^{-n-3}].$

Because of this, for each $j$, we can modify the definition of ${\cal M}_{j}$
to $\hat{\cal M}_{j}$ as long as $\hat{\cal M}_{j}$ agrees with ${\cal M}_{j}$
on $\Lambda^{\prime}:=[0,1]\setminus\Lambda$ and formula (3.18) will remain
valid. We now describe the modification we shall use.

It follows from (3.16) and (3.12) that for $j=1,\ldots,n$,

$\displaystyle{\mathcal{M}}_{j}(x)$ $\displaystyle=$ $\displaystyle
T(R^{j-1}(x))$ (3.19) $\displaystyle=$
$\displaystyle\chi_{[0,1/2{)}}(R^{j-1}(x))\cdot
T_{0}+\chi_{{[}1/2,1]}(R^{j-1}(x))\cdot T_{1},\quad x\in[0,1],$

where $R^{0}(x):=x$ and $\chi_{I}$ is the indicator function of the interval
$I$. Note that the functions $\chi$ and $R^{j-1}$, $j\geq 2$, participating in
(3.19) are discontinuous. We replace the characteristic functions
$\chi_{[0,1/2{)}}$ and $\chi_{{[}1/2,1]}$ by the CPwL functions

$\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}(x):=1-\frac{1}{\delta_{0}}(x-1/2)_{+}+\frac{1}{\delta_{0}}(x-1/2-\delta_{0})_{+},$
$\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}(x):=-\frac{1}{\delta_{0}}(x-1/2)_{+}+\frac{1}{\delta_{0}}(x-1/2+\delta_{0})_{+},$

respectively, where $\delta_{0}:=2^{-n-3}$. These functions satisfy for
$x\notin[1/2-2^{-n-3},1/2+2^{-n-3}]$

$\displaystyle\hat{\raise 1.29167pt\hbox{\large$\chi$}}_{0}(x)$
$\displaystyle=$ $\displaystyle\chi_{[0,1/2)}(x)\text{ and }$
$\displaystyle\hat{\raise 1.29167pt\hbox{\large$\chi$}}_{1}(x)$
$\displaystyle=$ $\displaystyle\chi_{[1/2,1]}(x).$ (3.20)

For $R$, we can use one of the substitutes $\hat{R}_{\alpha,\beta}$ defined in
the previous section. We take $\alpha>0$ such that
$\delta:=1/2-\alpha<2^{-n-3}$, $\beta\in(\alpha,1/2)$ and then consider

$\hat{R}:=\hat{R}_{\alpha,\beta}.$

With these preparations in hand, we define for $x\in[0,1],\ j=1,\dots,n,$

$\hat{\cal M}_{j}(x):=\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}(\hat{R}^{j-1}(x))T_{0}+\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}(\hat{R}^{j-1}(x))T_{1},$ (3.21)

where $\hat{R}^{0}(x):=x=R^{0}(x)$.

Finally, let us recall the sets $E_{j}$, $j=1,\dots,n$, see (3.1), and define

$E:=\bigcup_{j=1}^{n}E_{j},\quad E^{\prime}:=[0,1]\setminus E.$

Note that $E^{\prime}$ was denoted by $\Omega_{n}$ earlier.

######  Remark 3.6.

Notice that $E\subset\Lambda$ because of the choice of $\delta<2^{-n-3}$, and
so $\Lambda^{\prime}\subset E^{\prime}$. This means that for each
$j=1,\dots,n-1$, we have $\hat{R}^{j}(x)=R^{j}(x)$ for $x\in\Lambda^{\prime}$,
see (ii) of Lemma 3.2.

######  Lemma 3.7.

For each $j=1,2,\dots,n$, we have

$\hat{\cal M}_{j}(x):={\cal M}_{j}(x),\quad x\in\Lambda^{\prime},$ (3.22)

and therefore (3.18) holds with each ${\cal M}_{j}$ replaced by $\hat{\cal
M}_{j}$, $j=1,2,\dots,n$.

Proof: Let $x\in\Lambda^{\prime}$ and $1\leq j\leq n$. From Remark 3.6, we
know that $\hat{R}^{j-1}(x)=R^{j-1}(x)$. Next, we claim that when
$x\in\Lambda^{\prime}$, we have for $j=0,\dots,n-1$,

$R^{j}(x)\notin{[}1/2-2^{-n-3},1/2+2^{-n-3}]=:I\subset\Lambda,$ (3.23)

which in view of (3.2) will complete the proof of the Lemma.

To prove the claim (3.23), let us first note that when $j=0$ the claim is true
because $R^{0}(x)=x$ and $\Lambda^{\prime}$ does not contain points from $I$.
Now consider $j\geq 1$ and let $x\in\Lambda^{\prime}$. Choose $l$ so that
$x\in[l2^{-j},(l+1)2^{-j})=:J$. Recall that $R^{j}(x)=2^{j}x-l$, for $x\in J$,
and hence this function takes the value $1/2$ at $2^{-j}(l+1/2)$. Since
$x\in\Lambda^{\prime}$, it is at distance at least $\delta_{0}=2^{-n-3}$ from
$(l+1/2)2^{-j}$. Therefore, $R^{j}(x)$ differs from $1/2$ by at least
$2^{j}\delta_{0}$. This means $R^{j}(x)$ is not in $I$ as desired. $\Box$

We conclude this section with the observation that we now know that the $k$-th
coordinate $\bar{g}_{k}$ of $G_{n}$ has the representation

$\bar{g}_{k}(x)=g(R^{n}(x))e_{k}^{T}\hat{\mathcal{M}}_{1}(x)\cdot\ldots\cdot\hat{\mathcal{M}}_{n}(x)e_{1},$
(3.24)

whenever $g$ is a special function.

###  3.3 Computing products

In the next section, we use (3.24) to show that $\bar{g}_{k}$ is the output of
an NN with fixed width and depth $Cn$ with $C$ a fixed constant. If we look at
(3.24) and think of implementing it from left to right, we will be required to
compute products of the form $aA$, with $a$ being a row vector and $A$ being a
matrix, and both being outputs of an NN. In general, such a product is not an
output of an NN. In our case, however, both $a,A$ have special properties
which will allow us to show that the products we need are actually outputs of
an NN. The following lemma describes one setting when NNs can output products
exactly. We describe the simplest case where we want to take the product of a
scalar valued function with a vector valued function. More precisely, we
propose a function $\Pi=\Pi(x,y)$ that is an output of an NN and matches the
true product $xy$ whenever the scalar has values $0$ or $1$ or the vector $y$
is the zero vector. This will match our needs for computing $\bar{g}_{k}$.

In what follows, we denote by ${\bf e}\in\mathbb{R}^{N}$ the column vector
whose coordinates are all ones, that is

${\bf e}:=(1,1,\ldots,1)^{T}.$

######  Lemma 3.8.

Let $M$ be a positive number and let us define the function
$\Pi:\mathbb{R}\times\mathbb{R}^{N}\to\mathbb{R}^{N}$, by

$\displaystyle\Pi(x,y):=$ $\displaystyle-$ $\displaystyle\mathrm{ReLU}(Mx{\bf
e}-y)$ (3.25) $\displaystyle-$ $\displaystyle\mathrm{ReLU}\left(M(1-x){\bf
e}-\mathrm{ReLU}(-y)\right)$ $\displaystyle+$ $\displaystyle M{\bf e},$

for $x\in\mathbb{R}$ and $y\in\mathbb{R}^{N}$. Then, for all
$y=(y_{1},\ldots,y_{N})^{T}$ with $|y_{i}|\leq M$, and all $x\in[0,1]$, we
have

$\displaystyle\Pi\in\Upsilon^{2N+1,2}({\rm ReLU};N+1,N),$
$\displaystyle\Pi(1,y)=y,$ $\displaystyle\Pi(0,y)=0,$
$\displaystyle\Pi(x,0)=0.$ (3.26)

Proof: We consider an NN with $N+1$ inputs $(x,y)\in\mathbb{R}^{N+1}$. Its
first hidden layer has $2N+1$ nodes, holding $\mathrm{ReLU}(Mx{\bf e}-y)$,
$\mathrm{ReLU}(-y)$ and $x={\rm ReLU}(x)$. Its second layer has $2N$ nodes
holding the values $\mathrm{ReLU}(Mx{\bf e}-y)$ and

$$$\mathrm{ReLU}\left(M(1-x){\bf e}-\mathrm{ReLU}(-y)\right)=\\\
\mathrm{ReLU}\left(-M{\rm ReLU}(x){\bf e}-\mathrm{ReLU}(-y)+M{\bf
e}\right).$$$ (3.27)

We can view the first $N$ nodes in the second layer either as ReLU-free nodes,
or we can add a large bias which we then subtract after re-weighting at the
output. Finally, its output layer has $N$ nodes and bias $M{\bf e}$. Clearly,
this network outputs $\Pi$ in the case when $x\in[0,1]$.

A direct computation shows that

$\displaystyle\Pi(1,y)$ $\displaystyle=$ $\displaystyle-\mathrm{ReLU}(M{\bf
e}-y)-\mathrm{ReLU}\left(-\mathrm{ReLU}(-y)\right)+M{\bf e}$ $\displaystyle=$
$\displaystyle-M{\bf e}+y+M{\bf e}$ $\displaystyle=$ $\displaystyle y,$

since $|y_{i}|\leq M$, $i=1,\ldots,N$, and
$\mathrm{ReLU}\left(-\mathrm{ReLU}(-y)\right)=0$. Likewise,

$\displaystyle\Pi(0,y)$ $\displaystyle=$
$\displaystyle-\mathrm{ReLU}(-y)-\mathrm{ReLU}\left(M{\bf
e}-\mathrm{ReLU}(-y)\right)+M{\bf e}$ $\displaystyle=$
$\displaystyle-\mathrm{ReLU}(-y)-M{\bf e}+\mathrm{ReLU}(-y)+M{\bf e}$
$\displaystyle=$ $\displaystyle 0,$

and

$\displaystyle\Pi(x,0)$ $\displaystyle=$ $\displaystyle-{\rm ReLU}(Mx{\bf
e})-{\rm ReLU}(M(1-x){\bf e})+M{\bf e}$ $\displaystyle=$ $\displaystyle-Mx{\bf
e}-M(1-x){\bf e}+M{\bf e}$ $\displaystyle=$ $\displaystyle 0,$

since $|y_{i}|\leq M$, $i=1,\ldots,N$, and $x\in[0,1]$. $\Box$

###  3.4 The coordinates of $G_{n}$ are outputs of an NN

In this section, we show that each coordinate $\bar{g}_{k}$ of $G_{n}$ is the
output of an NN with fixed width $W$ and depth $Cn$ with $C$ a fixed constant.
We let $k\in\\{1,\dots,N\\}$ be arbitrary but fixed in this section. We begin
with the representation (3.24) for $\bar{g}_{k}$ and implement the product,
from left to right, via a recursive procedure. Namely, we recursively define
for $\\\ j=1,\ldots,n$,

$\displaystyle F^{0}(x)$ $\displaystyle=$ $\displaystyle
g(R^{n}(x))e_{k}^{T},$ $\displaystyle F^{j}(x)$ $\displaystyle=$
$\displaystyle F^{j-1}(x){\hat{\mathcal{M}}}_{j}(x).$

So, each $F^{j}(x)$ is a row vector. Clearly, we have

$\bar{g}_{k}(x)=F^{n}(x)e_{1}.$ (3.28)

We now replace $\hat{\cal M}_{j}$ by its representation (3.21), write
everything as column vectors and obtain the recursion for $j=1,\ldots,n,$

$\displaystyle[F^{j}(x)]^{T}$ $\displaystyle=$ $\displaystyle\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}(\hat{R}^{j-1}(x))\cdot{\cal
F}^{j-1}_{0}(x)+$ (3.29) $\displaystyle\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}(\hat{R}^{j-1}(x))\cdot{\cal
F}^{j-1}_{1}(x),$

with

${\cal F}^{j-1}_{0}(x)=T_{0}^{T}[F^{j-1}(x)]^{T},\quad{\cal
F}^{j-1}_{1}(x)=T_{1}^{T}[F^{j-1}(x)]^{T}.$ (3.30)

Notice that each of the two terms appearing in (3.29) is the product of a
scalar times a vector and so we can use $\Pi$ to implement this product. For
this, we define

$M:=\max_{j=0,\ldots,n-1}\max_{x\in[0,1]}\left\\{\|{\cal
F}_{0}^{j}(x)\|_{\ell_{\infty}^{N}},\|{\cal
F}_{1}^{j}(x)\|_{\ell_{\infty}^{N}}\right\\},$

and define the function $\Pi(\cdot,\cdot)$ in (3.25) with this constant $M$.

######  Lemma 3.9.

For each $j=1,\dots,n$, we have

$\displaystyle[F^{j}(x)]^{T}$ $\displaystyle=$ $\displaystyle\Pi(\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}(\hat{R}^{j-1}(x)),{\cal F}_{0}^{j-1}(x))+$
(3.31) $\displaystyle\Pi(\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}(\hat{R}^{j-1}(x)),{\cal F}_{1}^{j-1}(x)).$

Proof: This is proved by induction on $j$. Consider first the case $j=1$.
Since $g(R^{n})$ vanishes on $\Lambda$, we have that
$F^{0}=g(R^{n})e_{k}^{T}$, ${\cal F}^{0}=T_{0}^{T}[F^{0}]^{T}$, and ${\cal
F}^{1}=T_{1}^{T}[F^{0}]^{T}$ vanish on $\Lambda$. Moreover, since both
$\hat{\raise 1.29167pt\hbox{\large$\chi$}}_{0}(\hat{R}^{0})$ and $\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}(\hat{R}^{0})$ take only the values $0$ or
$1$ outside of $\Lambda$, Lemma 3.8 gives the result. We also obtain that
$F^{1}$ vanishes on $\Lambda$.

For $j\geq 2$, we proceed by induction, using that $F^{j-1}$ vanishes on
$\Lambda$ and relations (3.23) and (3.2) for $x\in\Lambda^{\prime}$. Namely,
we use the same argument to prove (3.31) and also to prove that $F^{j}$
vanishes on $\Lambda$. This allows us to advance the induction. $\Box$

######  Theorem 3.10.

If $g$ is a special function with $m$ break points, then for each
$k\in\\{1,\dots,N\\}$ and each $n\geq 1$, the coordinate function
$\bar{g}_{k}$ of $G_{n}$ belongs to the set $\Upsilon^{W,L}({\rm ReLU};1,1)$,
where

$W=\max\\{1+2\max\\{m,5\\},N+10,4N+3\\},\quad L=4n+1.$

Proof: We fix $k$ and construct a neural network ${\cal N}$ of the advertised
size that outputs $\bar{g}_{k}$. The network ${\cal N}$ is the concatenation
of several networks: a network ${\cal N}_{0}$ and then $n$ copies of a network
${\cal N}^{\prime}$. Let us note before we begin the proof that we repeatedly
use Remark 3.4 so that all of the component networks have the same width. We
do not always elaborate on that aspect going further.

The first network ${\cal N}_{0}$ has input $x$ and outputs
$(x,g(R^{n}(x)))=(\hat{R}^{0}(x),g(R^{n}(x)))$. It consists of the network
producing $g(R^{n})$ augmented with an additional channel that passes forward
the value $x$. We can view this channel as a ReLU channel since $x\geq 0$.
From Theorem 3.5 we know that

$g\circ R^{n}\in\Upsilon^{2\max\\{m,5\\},n+1}({\rm ReLU};1,1),$ (3.32)

where $m$ is the number of breakpoints of $g$. Thus, the width of this network
is $W_{0}=1+2\max\\{m,5\\}$ and the depth is $L_{0}=n+1$.

We come now to the recursive part ${\cal N}^{\prime}$ of ${\cal N}$, where
${\cal N}$ is completed by concatenating ${\cal N}_{0}$ with $n$ copies of
${\cal N}^{\prime}$. For each $j=1,\dots,n$, the network ${\cal N}^{\prime}$
that we describe below will take as Input: $\hat{R}^{j-1}(x),F^{j-1}(x),$ and
will produce Output: $\hat{R}^{j}(x),F^{j}(x)$. Notice that ${\cal N}_{0}$ can
output $\hat{R}^{0}(x)=x$ and $F^{0}(x)=g(R^{n}(x))e_{k}^{T}$ to start the
iteration. After these $n$ iterations are completed, ${\cal N}$ can output
$F^{n}(x)$ and $\bar{g}_{k}(x)$. Thus, it is enough to show that each
iteration can be completed with an NN of fixed width and depth.

We now describe the network ${\cal N}^{\prime}$ that gives the Input to Output
above. It has depth $L^{\prime}=3$. The first node of the first layer forwards
the value $\hat{R}^{j-1}(x)$. The next $5$ nodes of this layer are the network
for $\hat{R}$, followed by the $2$ nodes of the network for $\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}$ and the $2$ nodes for the network for
$\hat{\raise 1.29167pt\hbox{\large$\chi$}}_{1}$. The last $N$ nodes hold
$F^{j-1}(x)$. Thus, the width of this layer is $N+10$.

The next two layers of ${\cal N}^{\prime}$ consist of two copies of the
network producing $\Pi$ on the top of each other, augmented with additional
channel that holds $\hat{R}^{j}(x)$. Thus, the width of these two layers is
$4N+3$. So, the width of ${\cal N}^{\prime}$ is
$W^{\prime}=\max\\{N+10,4N+3\\}$. Clearly, then the width of ${\cal N}$ is

$W=\max\\{1+2\max\\{m,5\\},N+10,4N+3\\},$

and the depth is

$L=L_{0}+nL^{\prime}=n+1+3n=4n+1.$

We now describe how these networks are concatenated to produce ${\cal N}$. We
feed the output $\hat{R}^{0}(x)$ into the first node of the first layer and
into the networks for $\hat{R}$, $\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}$ and $\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}$. We feed zeroes to the last $N$ nodes of
this layer, except to the $k$-th of those, where we feed $g(R^{n}(x))$. Thus,
the output of the first layer of ${\cal N}^{\prime}$ is
$(\hat{R}^{0}(x),\hat{R}^{1}(x),\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}(\hat{R}^{0}(x)),\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}(\hat{R}^{0}(x)),F^{0}(x))$.

We then keep $\hat{R}^{1}(x)$ by feeding it through the first node of the
remaining layers before outputting it. We use the entries of the matrix
$T_{0}$ as weights applied to the output $F^{0}(x)$ of the previous layer to
produce ${\cal F}^{1}_{0}(x)$ and feed it to the first copy of the network for
$\Pi$. We feed to this first copy the output $\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{0}(\hat{R}^{0}(x))$ of the previous layer. We
use the entries of the matrix $T_{1}$ as weights applied to the output
$F^{0}(x)$ of the previous layer to produce ${\cal F}^{1}_{1}(x)$ and feed it,
together with the output $\hat{\raise
1.29167pt\hbox{\large$\chi$}}_{1}(\hat{R}^{0}(x))$ from the previous layer, to
the second copy of the network for $\Pi$.

We use formula (3.31) to output $F^{1}(x)$. Thus, after the concatenation of
${\cal N}_{0}$ and ${\cal N}^{\prime}$, we have computed
$(\hat{R}^{1}(x),F^{1}(x))$. Then, we concatenate as discussed above with the
next copy of ${\cal N}^{\prime}$ and so on. $\Box$

###  3.5 Piecing together

In this section, we construct an NN of controllable size that outputs $V^{n}g$
whenever $g$ is a special function. This is done by using the NNs from Theorem
3.10 that produce the components $\bar{g}_{k}$, $k=1,\dots,N$, of $G_{n}$.

######  Theorem 3.11.

If $g$ is a special function with $m\geq 3$ breakpoints, then for each $n\geq
1$,

$V^{n}g\in\Upsilon^{NW,4n+2}({\rm ReLU};1,1),\quad\\\ \hbox{where}\quad
W=\max\\{1+2\max\\{m,5\\},N+10,4N+3\\}.$ (3.33)

Proof: We introduce the following ‘ramp’ functions
$r_{k}\in\Upsilon^{2,1}({\rm ReLU};1,1)$, $k=1,2,\ldots,N$,

$\displaystyle r_{k}(x)$ $\displaystyle=$ $\displaystyle(x-k+1)_{+}-(x-k)_{+}$
(3.34) $\displaystyle=$ $\displaystyle\begin{cases}0,\quad x\leq k-1,\\\
x-k+1,\quad k-1\leq x\leq k,\\\ 1,\quad x\geq k.\end{cases}$

It follows that

$r_{k}(x)=x-k+1\quad\hbox{when}\quad x\in[k-1,k],\quad\hbox{and}\quad\\\
r_{k}(x)\in\\{0,1\\}\quad\hbox{when}\quad x\in\mathbb{R}\setminus[k-1,k].$
(3.35)

We use these functions to construct an NN ${\cal N}_{1}$ with input
$x\in\mathbb{R}$ and output $(r_{1}(x),\ldots,r_{N}(x))\in\mathbb{R}^{N}$ by
stacking on the top of each other the networks for $r_{1},r_{2},\ldots,r_{N}$.
This network has width $2N$ and depth $1$. Next, we build a network ${\cal
N}_{2}$ by stacking on the top of each other the NNs from Theorem 3.10 that
produce $\bar{g}_{k}(x)$, $k=1,\ldots,N$. This network has width $NW$, where
$W$ is the width from Theorem 3.10 and depth $4n+1$. We concatenate ${\cal
N}_{1}$ with ${\cal N}_{2}$ by feeding the first coordinate $r_{1}(x)$ of the
output of ${\cal N}_{1}$ to the NN producing $\bar{g}_{1}$, the second
coordinate $r_{2}(x)$ of the output of ${\cal N}_{1}$ to the NN producing
$\bar{g}_{2}$, etc. The concatenated neural network has width $NW$, depth
$4n+2$ and outputs

$\bar{g}_{1}(r_{1}(x))+\bar{g}_{2}(r_{2}(x))+\ldots+\bar{g}_{N}(r_{N}(x)).$

Moreover, because of property (3.35) and the fact that
$\bar{g}_{k}(0)=\bar{g}_{k}(1)=0$ for all $k=1,\ldots,N$, the output of the
constructed NN will be exactly $V^{n}g(x)$. $\Box$

######  Remark 3.12.

Other strategies to construct an NN that outputs $V^{n}g$ using the pieces
$\bar{g}_{k}$, $k=1,\ldots,N$, are possible. We have discussed a strategy that
inflates the width of the resulting NN (thus obtaining a width that is
possibly $\asymp N^{2}$), but keeps the depth $L$ independent of $N$. One may
choose to inflate the depth by a factor of $N$ (thus having depth $L\asymp
Nn$) but keep the width possibly linear in $N$.

###  3.6 Proof of Theorem 1.1

We first wish to start the discussion with $g=g_{0}$ a CPwL function that has
support in $[0,N]$ and has breakpoints at the integers. Proof of Theorem 1.1
for $g_{0}$: Recall that (3.6) gives $V^{n}g_{0}$ as a linear combination of
shifts of $V^{n}H$, where $H$ is the special function, defined in (3.4), that
is

$V^{n}g_{0}(x)=\sum_{j=1}^{8N-1}g_{0}(j/8)V^{n}H(x-2^{-n-3}(j-4)).$

Since $H$ has $m=3$ breakpoints, it follows from Theorem 3.11 that

$V^{n}H\in\Upsilon^{N\max\\{N+10,4N+3\\},4n+2}({\rm ReLU};1,1).$

We now use two basic well-known facts about outputs of NNs.

  * •

If the function $S$ belongs to $\Upsilon^{W^{\prime},L^{\prime}}({\rm
ReLU};1,1)$, then for any shift $\delta$, the function $S(\cdot+\delta)$ is in
$\Upsilon^{W^{\prime},L^{\prime}}({\rm ReLU};1,1)$.

  * •

If $S_{1},\dots,S_{\ell}\in\Upsilon^{W^{\prime},L^{\prime}}({\rm ReLU};1,1)$,
then the sum $\sum_{j=1}^{\ell}S_{j}\in\Upsilon^{W^{\prime}+2,\ell
L^{\prime}}({\rm ReLU};1,1)$.

Therefore, for every $j=1,\ldots,8N-1$,

$\displaystyle V^{n}H(\cdot-2^{-n-3}(j-4))\in$
$\displaystyle\Upsilon^{N\max\\{N+10,4N+3\\},4n+2}({\rm ReLU};1,1),$ (3.36)

and

$V^{n}g_{0}\in\Upsilon^{N\max\\{N+10,4N+3\\}+2,(8N-1)(4n+2)}({\rm ReLU};1,1).$

The proof is completed. $\Box$

Let us now explain why the theorem holds for any CPwL function $g$ supported
on $[0,N]$, i.e., why it is not necessary to assume that the breakpoints of
$g=g_{0}$ are at the integers. If $g$ has arbitrary breakpoints, we can always
take a finite set of breakpoints which contain the original breakpoints of $g$
and represent $g$ as a linear combination of hat functions centered at these
new breakpoints. By choosing the new breakpoints fine enough, each of the hat
functions will have a shift which is a special function and so the above proof
can be carried out in the same way. Thus, any CPwL function $g$ supported on
$[0,N]$ has the property that $V^{n}g\in\Sigma_{n}$.

##  4 Approximation of refinable functions

In this section, we show how the results of the previous section give upper
bounds on how well refinable functions can be approximated by deep NNs. This
is accomplished by utilizing known results from the theory of refinable
functions. Under certain conditions on the refinement mask $\bar{c}$, the
refinement equation has a unique solution $\phi=\phi_{\bar{c}}$ (up to
scaling). Moreover, for certain initial choices of a CPwL function $\phi_{0}$,
the cascade algorithm gives that $V^{n}\phi_{0}$ converges to $\phi$ in
$L_{\infty}$ with an exponential decay rate. There is a variety of statements
of this type, and rather than trying to summarize all of them, we refer the
reader to the existing literature, especially [5, 6] and the references in
those papers.

We say a refinement mask $\bar{c}$ is admissible if there exists a CPwL
function $\phi_{0}$ supported on $[0,N]$ for which

$\|\phi_{\bar{c}}-V^{n}\phi_{0}\|_{L_{\infty}(\mathbb{R})}\leq
C\lambda^{n},\quad n\geq 1,$ (4.1)

where $0<\lambda<1$ and $C>0$ are constants depending only on $\bar{c}$. Since
the preceding section shows that
$V^{n}\phi_{0}\in\Sigma_{n}:=\Upsilon^{C^{\prime},Cn}({\rm ReLU};1,1)$, with
$C^{\prime},C$ depending only on $\bar{c}$ and the number of breakpoints $m$
of $\phi_{0}$, we obtain the following theorem

######  Theorem 4.1.

If $\bar{c}$ is admissible then for $\Sigma_{n}$ as defined immediately above,
we have

$E_{n}(\phi)_{L_{\infty}(\mathbb{R})}:=\inf_{S\in\Sigma_{n}}\|f-S\|_{L_{\infty}(\mathbb{R})}\leq
C\lambda^{n},\quad n\geq 1.$ (4.2)

There are many results that establish conditions on $\bar{c}$ that guarantee
admissibility. In one set of results, one takes for $\phi_{0}$ the CPwL
function that interpolates $\phi_{\bar{c}}$ at the integers
$\\{0,1,\dots,N\\}$ and has its only breakpoints at these integers. A second
set of results shows that under certain conditions on $\bar{c}$, one can take
for $\phi_{0}$ the hat function centered at one with base width two.

##  5 Relation to $n$-term wavelet approximation and subdivision

We have shown that univariate refinable functions $\phi$ can be approximated
very efficiently using ReLU neural networks. In this section, we wish to point
out some consequences of this result related to $n$-term approximation from a
dictionary and to subdivision algorithms.

Let us first continue with a discussion of the approximation of functions of
one variable. One common tool for approximation, prevalent in computational
harmonic analysis, is to use wavelets and their descendants in the
approximation. The classical wavelets $\psi$ such as the Daubechies compactly
supported wavelets (see [3]) or the Cohen-Daubechies-Feauveau biorthogonal
wavelets (see [2]) are each a finite linear combination of shifts of a
refinable function $\phi$. Therefore, it follows from our results that $\psi$
is very well approximated by outputs of neural networks. Namely, the bounds on
approximation error that we have derived for $\phi$ apply for $\psi$ as well.
This can then be used to approximate general functions $f$ via their wavelet
decomposition. We briefly discuss how this plays out when the approximation
takes place in $L_{2}(\mathbb{R})$. A similar analysis holds when
approximation takes place in $L_{p}(\Omega)$ with $\Omega$ a sub-interval of
$\mathbb{R}$.

We suppose that $\psi$ is a compactly supported wavelet which generates an
orthogonal basis. To describe this wavelet basis, we normalize $\psi$ so that
$\|\psi\|_{L_{2}(\mathbb{R})}=1$. Let ${\cal D}$ be the set of dyadic
intervals $I=[j,j+1]2^{-k}$ where $j,k$ are integers. Then the functions

$\psi_{I}(x)=2^{k/2}\psi(2^{k}x-j),\quad I=[j,j+1]2^{-k},$ (5.1)

form a complete orthonormal system $\Psi:=(\psi_{I})_{I\in{\cal D}}$ for
$L_{2}(\mathbb{R})$. Therefore, every function $f\in L_{2}(\mathbb{R})$ has a
wavelet decomposition

$f=\sum_{I\in{\cal D}}f_{I}\psi_{I},\quad f_{I}:=\langle
f,\psi_{I}\rangle{:=\intop\limits_{\mathbb{R}}f\psi_{I}}.$ (5.2)

A common approximation and numerical tool is to use an $n$-term approximation
to $f$ from the terms in (5.2). This type of approximation has error

$\sigma_{n}(f)_{L_{2}(\mathbb{R})}:=\inf_{\\#(\Lambda)=n}\|f-\sum_{I\in\Lambda}f_{I}\psi_{I}\|_{L_{2}(\mathbb{R})}.$
(5.3)

Because of the results we have proved about NNA of $\psi$, we can replace each
$\psi_{I}$ by $\hat{\psi}_{I}$ from $\Upsilon^{C^{\prime},C\ell}({\rm
ReLU};1,1)$ and incur an additional error in the approximation for each term
that is replaced. Consider, for example, the case when $\psi$ is approximated
to accuracy $C2^{-\ell\alpha}$ by the elements of
$\Sigma_{\ell}:=\Upsilon^{C^{\prime},C\ell}({\rm ReLU};1,1)$. Then, each
function $\psi_{I}$ is likewise approximated by a
$\hat{\psi}_{I}\in\Sigma_{\ell}$ with the same accuracy $C2^{-\ell\alpha}$.
This gives that any sum $S=\sum_{I\in\Lambda}f_{I}\psi_{I}$ of $n$ terms is
approximated by $\hat{S}:=\sum_{I\in\Lambda}f_{I}\hat{\psi}_{I}$ with accuracy

$\|S-\hat{S}\|_{L_{2}(\mathbb{R})}\leq
C2^{-\ell\alpha}\sum_{I\in\Lambda}|f_{I}|\leq
C\sqrt{n}2^{-\ell\alpha}\|f\|_{L_{2}(\mathbb{R})},\quad n\geq 1.$ (5.4)

Since $\hat{S}$ is in $\Sigma_{Cn\ell}$, this gives the approximation rate

$E_{Cn\ell}(f)_{L_{2}(\mathbb{R})}\leq
C\sigma_{n}(f)_{L_{2}(\mathbb{R})}+C\sqrt{n}2^{-\ell\alpha}.$ (5.5)

Let us consider an example, where $\sigma_{n}(f)_{L_{2}(\mathbb{R})}\leq
Mn^{-r}$ with $r>0$. Choosing $\ell=a\log_{2}n$ with $a$ sufficiently large
depending only on $r$, we obtain

$E_{n\log_{2}n}(f)_{L_{2}(\mathbb{R})}\leq Cn^{-r},\quad n\geq 1.$ (5.6)

In other words, using slightly more parameters in NNA achieves the
approximation rate of $n$-term wavelet approximation. This rate holds for all
$r>0$ and universally for all choices of the wavelet basis. It does not
require knowledge of the wavelet $\psi$.

The above results extend to $n$-term wavelet approximation of multivariate
functions defined on $\mathbb{R}^{d}$ or a domain
$\Omega\subset\mathbb{R}^{d}$. The standard construction of multivariate
wavelet bases uses shifted dilates of functions

$\psi^{e}(x_{1},\dots,x_{d})=\psi^{e_{1}}(x_{1})\cdots\psi^{e_{d}}(x_{d}),\quad
e\in\\{0,1\\}^{d},$ (5.7)

where $\psi^{(0)}:=\phi$ and $\psi^{(1)}:=\psi$. The wavelet decomposition of
$f\in L_{2}(\Omega)$ now takes the form

$f=\sum_{I\in{\cal D}(\Omega)}f_{I,e}\psi^{e}_{I},\quad f_{I,e}:=\langle
f,\psi^{e}_{I}\rangle,$ (5.8)

where now ${\cal D}(\Omega)$ is a collection of dyadic cubes supported near
$\Omega$ and the $\psi_{I}^{e}$ are scaled dilated shifts of the $\psi^{e}$.

Recall (see Remark 8.2 in [7]) that the tensor product (5.7) can be
approximated to accuracy $Cd(2^{-\ell\alpha}+4^{-\ell^{\prime}})$ by an
element from $\Sigma_{C(\ell^{\prime}+\ell)}$, and therefore any function
appearing in (5.8) is approximated to this accuracy. Then, one can obtain
comparisons similar to (5.5) between NNA and $n$-term wavelet approximation in
the multivariate case. We leave the precise formulation of such comparisons to
the reader.

Finally, let us mention briefly a connection of our result with subdivision
algorithms (see [1] for a general treatment of these algorithms). We discuss
only the univariate setting. Generally speaking, a subdivision algorithm
begins with a fixed collection $\Lambda=\\{(x_{i},y_{i}):i=1,\dots,N\\}$ of
data points (called control points), and uses a recursive rule to generate
curves which are then used for shape design. In the simplest case, the $n$-th
iteration of a subdivision algorithm gives a curve $y=f_{n}(x)$ for a suitable
function $f_{n}$. The rule for generating the $f_{n}$ can often be described
as $f_{n}=V^{n}g$, where $g$ is a CPwL function and $V^{n}$ is the operator
associated to a refinement equation. Our results show that the functions
$f_{n}$ are outputs of neural networks of controlled size. Therefore, in these
cases, the functions generated by subdivision algorithms lie in these neural
network spaces.

## References

  * [1] A. Caveretta, W. Dahmen, C. Micchelli, Stationary Subdivision, American Math. Society, Providence, 1991.
  * [2] A. Cohen, I, Daubechies, J. C. Feauveau, Biorthogonal bases of compactly supported wavelets, Communications on Pure and Applied Mathematics 45(1992), 485–560.
  * [3] I. Daubechies, Ten Lectures on Wavelets, SIAM, Philadelphia, 1992.
  * [4] I. Daubechies, R. DeVore, S. Foucart, B. Hanin, G. Petrova, Nonlinear approximation and (deep) relu networks, ArXiv, Constructive Approximation, to appear.
  * [5] I. Daubechies, J. Lagarias, Two scale difference equations I: existence and global regularity of solutions, SIAM J. Math. Anal. 22(1991), 1388–1410.
  * [6] I. Daubechies, J. Lagarias, Two scale difference equations II: local regularity, infinite products of matrices and fractals, SIAM J. Math. Anal. 23(1) (1992), 1031–1079.
  * [7] R. DeVore, B. Hanin, G. Petrova, Neural Network Approximation, Acta Numerica, 30(2021), to appear.
  * [8] N. Dym, B. Sober, I. Daubechies, Expression of fractals through neural network functions, IEEE Journal on Selected Areas in Information Theory 1(1) (2020), 57–66.
  * [9] W. E, Q. Wang, Exponential convergence of the deep neural network approximation for analytic functions,Sci. China Math., 61 (2018), 1733–1740.
  * [10] D. Elbrac̈hter, D. Perekrestenko, P. Grohs, H. Bȯlcskei, Deep Neural Network Approximation Theory, IEEE Transactions of Information Theory, 67(5) (2021), 2581–2623.
  * [11] J.A.A. Opschoor, Ch. Schwab, J. Zech , Exponential ReLU DNN Expression of Holomorphic Maps in High Dimension, Constructive Approximation (2021), doi.org/10.1007/s00365-021-09542-5.
  * [12] A. Pinkus, Approximation theory of the mlp model in neural networks, Acta Numerica 8(1999), 143–195.
  * [13] D. Yarotsky, Error bounds for approximations with deep relu networks,Neural Networks, 94 (2017), 103–114.

Ingrid Daubechies, Department of Mathematics, Duke University, Durham, NC
27705,
<EMAIL_ADDRESS>
Ronald DeVore, Department of Mathematics, Texas A& M University, College
Station, TX 77843,
<EMAIL_ADDRESS>
Nadav Dym, Department of Mathematics, Duke University, Durham, NC 27705,
<EMAIL_ADDRESS>Shira Faigenbaum-Golovin, Department of Mathematics, Duke
University, Durham, NC 27705,
<EMAIL_ADDRESS>
Shahar Z. Kovalsky, Department of Mathematics, University of North Carolina,
Chapel Hill, NC 27599,
<EMAIL_ADDRESS>
Kung-Ching Lin , Department of Mathematics, Texas A& M University, College
Station, TX 77840,
<EMAIL_ADDRESS>
Josiah Park, Department of Mathematics, Texas A& M University, College
Station, TX 77840,
<EMAIL_ADDRESS>
Guergana Petrova, Department of Mathematics, Texas A& M University, College
Station, TX 77840,
<EMAIL_ADDRESS>
Barak Sober, Department of Mathematics, Duke University, Durham, NC 27705,
<EMAIL_ADDRESS>