# Nonlinear approximation of high-dimensional anisotropic analytic functions

Diane Guignard111DG acknowledges the support provided by the Natural Science
and Engineering Research Council (NSERC, grant RGPIN-2021-04311). PJ was
partially supported by NSF Fellowship DMS-1704121<EMAIL_ADDRESS>Peter
Jantsch222DG acknowledges the support provided by the Natural Science and
Engineering Research Council (NSERC, grant RGPIN-2021-04311). PJ was partially
supported by NSF Fellowship DMS-1704121<EMAIL_ADDRESS>
###### Abstract

Motivated by nonlinear approximation results for classes of parametric partial
differential equations (PDEs), we seek to better understand so-called library
approximations to analytic functions of countably infinite number of
variables. Rather than approximating a function of interest in a single space,
a library approximation uses a collection of spaces and the best space may be
chosen for any point in the domain. In the setting of this paper, we use a
specific library which consists of local Taylor approximations on sufficiently
small rectangular subdomains of the (rescaled) parameter domain
$Y:=[-1,1]^{\mathbb{N}}$. When the function of interest is the solution of a
certain type of parametric PDE, recent results [5] prove an upper bound on the
number of spaces required to achieve a desired target accuracy. In this work,
we prove a similar result for a more general class of functions with
anisotropic analyticity, namely the class introduced in [6]. In this way we
show both where the theory developed in [5] depends on being in the setting of
parametric PDEs with affine diffusion coefficients, and also expand the
previous result to include more general types of parametric PDEs.

###### keywords:

approximation of high-dimensional functions, anisotropic analyticity,
piecewise polynomials, nonlinear reduced model

[1]organization=University of Ottawa, Department of Mathematics and
Statistics, addressline=150 Louis-Pasteur Pvt, city=Ottawa, state=ON,
country=Canada, postcode=K1N 6N5 [2]organization=Wheaton College, Department
of Mathematics and Computer Science, addressline=501 College Ave,
city=Wheaton, state=IL, postcode=60187, country=USA

##  1 Introduction

Polynomial and piecewise polynomial approximations are fundamental tools in
numerical analysis, forming the basis for many widely used methods such as the
finite element method. More recently, results on polynomial and piecewise
polynomial approximation have become important for understanding model
reduction techniques for parametrized partial differential equations (PDEs),
which are a typical model for describing complex systems in the field of
uncertainty quantification or optimization. In this work, we consider these
problems through the more general framework of approximating a function

$y\in Y\mapsto u(y)\in X,$

where $X$ is a Banach space, and $Y\subset\mathbb{R}^{d}$ is the parameter
domain with $d$ large or even countably infinite. To prove results which are
immune to the dimension $d$, we assume in what follows that the parameters are
countably infinite, namely $y=(y_{1},y_{2},\ldots)$, and that they have been
rescaled so that $Y=[-1,1]^{\mathbb{N}}$. The finite dimensional case
$y=(y_{1},\dots,y_{d})$ with $d<\infty$ can always be recast in this setting
by considering that $u(y)$ does not depend on the variables $y_{j}$ for $j>d$.

Because of the dimensionality, it is often crucial to perform a model
reduction (dimension reduction) for $u$. A typical model reduction method is
based on introducing a linear space $X_{n}$, of low dimension $n$, which is
tailored to provide an accurate approximation to all $u(y)$ as $y$ varies in
$Y$, or equivalently, to

${\mathcal{M}}:=\\{u(y)\in X:\ y\in Y\\}.$ (1)

One possibility for obtaining such dimension reduction is to approximate $u$
by Banach space valued polynomials in $y$. Another common approach is to
define $X_{n}$ to be the linear span of so-called snapshots
$u(y^{1}),\ldots,u(y^{n})\in X$ for suitably selected parameters $y^{1},\ldots
y^{n}\in Y$ and, given $y\in Y$, approximate $u(y)$ by its orthogonal
projection onto $X_{n}$.

Recent results from [5, 11, 12, 15] have also drawn attention to the use of
nonlinear model reduction methods, which have several advantages over linear
methods. First, the ability to use approximation spaces of small dimension
enables one to avoid the computationally expensive process of projecting a
function into a space of large dimension, which must be done online whenever
the reduced model is utilized. Another advantage is in the problem of state
and parameter estimation, which is one of the main motivations for the
introduction of nonlinear reduced models in [5]. In this framework, there is
limited information available about the solution manifold, usually in the form
of linear measurements of the state, and increasing the dimension of the
reduced space beyond that of the space characterizing the measurements is
unhelpful; see for instance [4].

Although we are motivated by parametric PDE applications, we formulate and
study this subject in a more abstract form as a problem in multivariate
approximation. By deriving results for a general class of functions, namely
the class of anisotropic analytic functions introduced in [6] (see Definition
1 below), we hope to draw attention to two points. First, we show where the
previous theory from [5] relies on being in the setting of an elliptic
parametric PDE with affine diffusion coefficient. Furthermore, by expanding
the result to a general class of functions, we may then apply it to some other
types of parametric PDEs as soon as the corresponding solution satisfies
appropriate analyticity assumptions.

###  1.1 Linear reduced models

As mentioned above, there are two general approaches to finding a linear
reduced model $X_{n}$. When the map $y\mapsto u(y)$ has a certain analyticity
in $y$, the Taylor polynomial approach333Depending on the context, other
polynomial representations could be used such as expansions with respect to
Legendre, Chebyshev or Hermite polynomials. makes use of the series
representation

$u(y)=\sum_{\nu\in{\mathcal{F}}}t_{\nu}y^{\nu},\quad t_{\nu}\in X.$ (2)

Here, ${\mathcal{F}}$ denotes the set of finitely-supported sequences
$\nu=(\nu_{1},\nu_{2},\dots)$, i.e., sequences with finitely many non-zero
terms, and whose entries are nonnegative integers, and $y^{\nu}=\prod_{j\geq
1}y_{j}^{\nu_{j}}$. Under certain analyticity assumptions, quantitative bounds
for the norms of the Taylor coefficients, $\|t_{\nu}\|_{X}$, allow one to
prove that for any $\varepsilon$, there is a finite set
$\Lambda=\Lambda(\varepsilon)\subset{\mathcal{F}}$ such that

$\sup_{y\in Y}\|u(y)-\sum_{\nu\in\Lambda}t_{\nu}y^{\nu}\|_{X}\leq\varepsilon.$
(3)

The space $X_{n}:={\rm span}\\{t_{\nu}:\nu\in\Lambda\\}$ provides the reduced
model with $n=\\#(\Lambda)$. In this case, an approximation of $u(y)$ in
$X_{n}$ is readily provided by the function

$u(y)\approx\hat{u}(y):=\sum_{\nu\in\Lambda}t_{\nu}y^{\nu},$ (4)

in other words, we approximate $u$ using the terms $y^{\nu}$ as the
coefficients of $\hat{u}$ in the basis $\\{t_{\nu}\\}_{\nu\in\Lambda}$.
Moreover, the sets $\Lambda$ may be chosen as lower sets, which are defined by
the property

$\hbox{if}\quad\nu\in\Lambda,\quad\hbox{then}\quad\mu\in\Lambda\quad\hbox{whenever}\quad\mu_{j}\leq\nu_{j},\quad
j=1,2,\dots.$

A second approach to finding a reduced model is to judiciously select certain
snapshots $u(y^{1}),\dots,u(y^{n})\in X$ of $u$, for instance via a greedy
procedure, and use the space spanned by the snapshots as the reduced model,
i.e., $X_{n}:=\mathrm{span}\\{u(y^{1}),\dots,u(y^{n})\\}$. In this case, the
approximation of $u(y)$ in $X_{n}$ is defined to be

$u(y)\approx\tilde{u}(y):=P_{X_{n}}u(y),$

where $P_{X_{n}}u(y)$ denotes the orthogonal projection of $u(y)$ onto
$X_{n}$. We will comment on a few of the advantages and drawbacks of these
methods in Section 1.3 below.

###  1.2 Nonlinear reduced models and library approximation

In many contexts, numerical methods based on nonlinear approximation perform
better than their linear counterpart, in the sense that they achieved a
prescribed accuracy with fewer degrees of freedom [10]. This motivates us to
consider replacing the linear reduced model $X_{n}$ by a nonlinear space
$\Sigma_{n}$ depending on $n$ parameters. We call such a space $\Sigma_{n}$ a
nonlinear reduced model. This idea has already been suggested and studied in
certain settings; see e.g., [5, 11, 12, 15].

The nonlinear reduced models studied in this paper can be placed into the form
of what is sometimes called library approximation. Given a Banach space $X$, a
library ${\mathcal{L}}$ is a finite collection of affine spaces
$L_{1}:=x_{1}+X_{1},\dots,L_{N}:=x_{N}+X_{N}$, where each $X_{j}$ is a linear
space of dimension at most $m$, and each $x_{j}\in X$, $j=1,\dots,N$. We set
each $X_{j}=\\{0\\}$ in the case $m=0$. For an element $x\in X$, the error of
approximation of $x$ by the library ${\mathcal{L}}$ is

$E(x,{\mathcal{L}}):=\inf_{L\in{\mathcal{L}}}\mathop{\rm dist}(x,L)_{X}.$ (5)

In other words, given $x$, we choose the best of the affine spaces
$L_{j}=x_{j}+X_{j}$, $j=1,\ldots,N$, to approximate $x$. Given a library
${\mathcal{L}}$ and a compact set $K\subset X$, we define the worst-case error

$E_{\mathcal{L}}(K):=\sup_{x\in K}E(x,{\mathcal{L}}).$ (6)

For a given a class of functions $K$, the goal is then to build a library with
$m$ small, in comparison to the dimension $n$ used in linear models $X_{n}$,
while retaining the accuracy of the reduced model and keeping the dimension of
the library $N$ moderate.

We denote by ${\mathcal{L}}_{m,N}={\mathcal{L}}_{m,N}(X)$ the collection of
all libraries ${\mathcal{L}}=\\{L_{1},\ldots,L_{N}\\}$ containing $N$ affine
spaces of dimension at most $m$. If we fix the values of $m$ and $N$, then the
best performance of a library with these fixed values is

$d_{m,N}(K):=\inf_{{\mathcal{L}}\in\ {\mathcal{L}}_{m,N}}E_{\mathcal{L}}(K).$
(7)

We call $d_{m,N}$ the library width of $K$. This definition slightly differs
from that introduced in [13] in which the spaces $L_{j}$ are taken to be
linear instead of affine.

Library widths include the two standard approximation concepts of widths and
entropy. Recall that if $K$ is a compact set in a Banach space $X$, then its
Kolmogorov $m$-width is

$d_{m}(K):=d_{m}(K)_{X}:=\inf_{\dim(W)=m}\mathop{\rm dist}(K,W)_{X},$ (8)

where the infimum is taken over all linear spaces $W$ of dimension $m$. Thus
the Kolmogorov $m$-width of $K$ is the smallest error that can be obtained by
approximating $K$ with linear spaces of dimension $m$. It follows that we can
bound the library width $d_{m,1}(K)_{X}$ between Kolmogorov widths by

$d_{m+1}(K)\leq d_{m}(K_{0})=d_{m,1}(K)\leq d_{m}(K),$ (9)

where $K_{0}=K-x_{0}$ for some suitable $x_{0}\in X$. At the other extreme,

$d_{0,2^{n}}(K)=\varepsilon_{n}(K),$ (10)

where $\varepsilon_{n}(K)$ is the $n$th entropy number of $K$: that is, the
smallest number $\varepsilon$ such that $K$ can be covered by $2^{n}$ balls of
radius $\varepsilon$ in $X$.

###  1.3 Application to Parametric PDEs

As mentioned before, one of the main motivations in considering the
approximation of high-dimensional Banach or Hilbert space-valued functions is
the solution of parametric PDEs, which take the general form

${\mathcal{P}}(u,y)=0,$ (11)

where $y$ ranges over some parameter domain $Y$ and $u=u(y)$ is the
corresponding solution assumed to be uniquely defined in some Hilbert space
$V$ for every $y\in Y$. We distinguish two frameworks in which such parametric
PDEs arise. In optimal design or inverse problems, the goal is to minimize an
objective function involving $u(y)$. In the uncertainty quantification
setting, where the parameter vector $y$ is the realization of some random
vector modeling the uncertainty in the system, we are interested in computing
statistics of $u(y)$. Both settings require the solution of the parametric PDE
(11) for many different values of $y\in Y$, where again the rescaled parameter
domain is assumed to be $Y=[-1,1]^{\mathbb{N}}$. To relate the following to
the general discussion above, let $X=V$ and define $K={\mathcal{M}}:=\\{u(y):\
y\in Y\\}$ to be the solution manifold of the PDE.

There is a rigorous theory that quantifies the approximation performance of
linear reduced models for parametric PDEs; see [9] for a summary of known
results. The theory is most fully developed in the case of elliptic PDEs of
the form

$-\mathop{\rm div}\nolimits(a\nabla u)=f,$ (12)

set on a physical domain $D\subset\mathbb{R}^{k}$ (typically $k=1,2,3$), with,
e.g., Dirichlet boundary conditions $u_{|\partial D}=0$, and where the
diffusion function $a$ has an affine representation of the form

$a(y)=\bar{a}+\sum_{j\geq 1}y_{j}\psi_{j},$ (13)

for some given functions $\bar{a}$ and $(\psi_{j})_{j\geq 1}$ in
$L^{\infty}(D)$. These functions are assumed to satisfy the condition

$\left\|\frac{\sum_{j\geq 1}|\psi_{j}|}{\bar{a}}\right\|_{L^{\infty}(D)}<1,$
(14)

which is equivalent to the following _Uniform Ellipticity Assumption_ (UEA):
there exist $0<a_{\mathrm{min}}\leq a_{\mathrm{max}}<\infty$ such that

$0<a_{\mathrm{min}}\leq a(y)\leq a_{\mathrm{max}}<\infty,\quad y\in Y.$ (15)

Lax-Milgram theory then ensures that whenever $f\in V^{\prime}=H^{-1}(D)$, for
each $y\in Y$, the corresponding solution $u(y)$ is uniquely defined in the
Hilbert space $V:=H_{0}^{1}(D)$ endowed with the norm $\|v\|_{V}:=\|\nabla
v\|_{L^{2}(D)}$, $v\in V$.

Under these assumptions on the parametrized input data of the PDE, it is known
that $u$ admits an analytic extension onto certain complex polydiscs or so-
called filled-in Bernstein polyellipses that contain $Y$ (see [9]). In other
words, $u$ has a certain anisotropic analyticity, dictated by the radius of
the polydiscs or the length of the semi-axis of the polyellipses,
respectively, and is therefore amenable to approximation by polynomials.

For this affine parametric model (and some related to it), recent results show
that there is a numerical advantage in the Taylor coefficient approach to
approximating $u$. More specifically, it is sometimes possible to find a
priori a suitable lower set $\Lambda$ by exploiting the parametric form of the
diffusion coefficients [1], and bounds on the cardinality of $\Lambda$ needed
to reach a prescribed accuracy are available; see for instance [9, 6]. This
avoids computationally expensive search algorithms that are a component of
greedy reduced basis selections. Moreover, the (Galerkin) projection involved
in greedy algorithms is not needed, saving the cost of solving a linear system
with a dense $n\times n$ matrix. On the other hand, greedy procedures have the
advantage that they are provably near-optimal for finding a linear space to
approximate $u$, in the sense that their convergence rates are similar to
those of the optimal linear spaces for approximating ${\mathcal{M}}$ [3].
Numerical experiments show that for a prescribed target accuracy, the greedy
generated spaces that meet this accuracy are of significantly lower dimension
then their polynomial counterparts [5]. However, as mentioned above, the
(offline) computational costs to constructing a reduced basis via a greedy
algorithm becomes prohibitive as the target accuracy $\varepsilon$ gets small
(or $n$ is getting large); we refer to [9] for a detailed analysis. This high
computational cost can be alleviated if one uses random training sets, see
[8], in which case the error bounds are no longer certified but hold with high
probability.

In the case of nonlinear reduced models for parametric PDEs, a library
${\mathcal{L}}$ would then consist of affine spaces

$L_{i}:=u_{i}+V_{i},$ (16)

where each $u_{i}\in V$ and each $V_{i}\subset V$ has dimension at most $m$.
Then, the best approximation to $u(y)$ from $L_{i}$ is

$u_{i}+P_{V_{i}}(u(y)-u_{i}),$ (17)

where $P_{V_{i}}$ is the $V$-orthogonal projection onto $V_{i}$. In this
context, when presented with a parameter $y$ for which we wish to compute an
approximation to $u(y)$, the choice of which space $L_{i}$ to use from a given
library ${\mathcal{L}}$ could be decided in several ways. One possibility
would be to find a computable upper bound for $\mathop{\rm
dist}(u(y),L_{i})_{V}=\|u-u_{i}-P_{V_{i}}(u(y)-u_{i})\|_{V}$, namely a
quantity only involving the projection $P_{V_{i}}(u(y)-u_{i})$ and input data,
and choose the value of $i$ that minimizes this surrogate quantity. This
approach would however require the computation of the projection
$P_{V_{i}}(u(y)-u_{i})$ onto each space $V_{i}\in{\mathcal{L}}$ which can be
prohibitive when the cardinality of the library is large. Another procedure,
and the one considered in this paper, involves building an a priori partition
of the parameter domain $Y$ into cells $Q_{i}$, and constructing an affine
space $L_{i}$ for each cell. Then the choice of $L_{i}$ for approximating
$u(y)$ is determined by the cell $Q_{i}$ containing $y$. One of the
motivations for using library approximations with a small value of $m$ is to
control the offline costs needed to construct each affine space $L_{i}$ in the
collection. In addition, having a collection of low-dimensional spaces can
also be beneficial in terms of online costs, as each query of the parameter-
to-solution map $y\mapsto u(y)$ is computationally cheap. We also mention that
keeping $m$ small is in fact required is some contexts, for instance when
estimating the state from data observations. Indeed, in this setting the
dimension of the reduced spaces are limited by the number of measurements of
the state.

There are many parametric PDE problems outside of this theory for elliptic
diffusion equations with coefficients of the form (13), which nonetheless has
certain anisotropic analyticity properties. Therefore, one goal of this paper
is to prove results for nonlinear approximation in these cases. In the
following sections, we do this by considering general approximation classes of
anisotropic analytic functions, without regard for any specific parametric PDE
setting.

###  1.4 Outline

The rest of this paper is organized as follows. In Section 2 we introduce the
model class of anisotropic analytic functions with Definition 1. With Theorem
1, we then give a global error estimate for the (Taylor) polynomial
approximation error in the $L^{\infty}(Y,X)$ norm, and discuss sufficient
conditions for proving local error estimates. In Section 3, we introduce
results from interpolation theory that are used to prove one of the local
error estimate given in Section 4. In the latter, we give two upper bounds for
the error in a subdomain $Q\subset Y$; see Theorems 3 and 4. Although both
estimates provide the same convergence rate with respect to the dimension of
the (local) reduced space, the upper bound derived in Theorem 3 requires that
the sequence $\rho=(\rho_{1},\rho_{2},\ldots)$ characterizing the analytic
anisotropy of the function to be approximated satisfies
$(\rho_{j}^{-1})_{j\geq 1}\in\ell_{1}(\mathbb{N})$. This is a restrictive
assumption that is not needed for the bound in Theorem 4 which involves a
modified sequence $\kappa=(\rho_{1}^{\theta},\rho_{2}^{\theta},\ldots)$ with
$0<\theta\leq 1$. Section 5 contains a comparison of the error estimates based
on the original and modified sequences $\rho$ and $\kappa$. The local bound of
Theorem 4 is then used in Section 6 to derive an upper bound on the dimension
of the library needed to achieved a prescribed accuracy using spaces of a
fixed dimension on each subdomain. Finally, concluding remarks are made in
Section 7.

###  1.5 Notation

For sequences $a=(a_{j})_{j\geq 1}$, $b=(b_{j})_{j\geq 1}$ and
$c=(c_{j})_{j\geq 1}$, we will assume the following operations act elementwise
and write

$a\pm b=(a_{1}\pm b_{1},a_{2}\pm
b_{2},\ldots),\quad|a|=(|a_{1}|,|a_{2}|,\ldots),\quad
a+cb=(a_{1}+c_{1}b_{1},a_{2}+c_{2}b_{2},\ldots),$

and

$a^{b}=\prod_{j\geq 1}a_{j}^{b_{j}},\quad a!=\prod_{j\geq 1}a_{j}!.$

Moreover, for any multi-index set $\Lambda\subseteq{\mathcal{F}}$ containing
the zero sequence $0$, we write $\Lambda^{*}:=\Lambda\setminus\\{0\\}$.

##  2 Anisotropic analyticity and approximation

In this section, we recall the classes of anisotropic analytic functions
introduced in [6] and derive a (global) approximation error estimate.
Throughout this paper $\rho=(\rho_{1},\rho_{2},\dots)$ denotes a sequence of
positive real numbers larger than one (i.e., $\rho_{j}>1$ for all $j\geq 1$)
which satisfies $\lim_{j\to\infty}\rho_{j}=\infty$. We recall the Banach space
$\ell_{\infty}(\mathbb{N})$ of all bounded complex valued sequences
$(z_{j})_{j\geq 1}$, with its usual norm
$\|z\|_{\ell_{\infty}{(\mathbb{N})}}:=\sup_{j\geq 1}|z_{j}|$, and let
${\mathcal{U}}$ denote the unit ball of $\ell_{\infty}(\mathbb{N})$.

In what follows, we are interested in representing a function $u\in
L^{\infty}(Y,X)$ by a Taylor series expansion

$u(y)=\sum_{\nu\in{\mathcal{F}}}t_{\nu}y^{\nu},\quad t_{\nu}\in X.$ (18)

An important question is in which sense this Taylor series converges. We say
that the convergence is uniform unconditional if any rearrangement of the
terms in the series in (18) converges uniformly in the space $X$. As noted in
[9, §3.1], such convergence is ensured whenever
$(\|t_{\nu}\|_{X})_{\nu\in{\mathcal{F}}}$ is in $\ell_{1}({\mathcal{F}})$.
Moreover, if $u$ satisfies a so-called _truncation property_ , then $u$
coincide with its Taylor series, see [14, Proposition 2.1.5] for details. The
class of functions ${\mathcal{B}}_{\rho,p}$ introduced in [6] then consists of
$X$-valued functions with convergent Taylor series that has certain anisotropy
dictated by the sequence $\rho$. The precise definition is as follows.

######  Definition 1.

For any $0<p\leq\infty$, we define the space ${\mathcal{B}}_{\rho,p}$ as the
set of all $u\in L^{\infty}(Y,X)$ which admit a representation

$u(y)=\sum_{\nu\in{\mathcal{F}}}t_{\nu}y^{\nu},\quad y\in Y,$

with the convergence of the series uniform unconditional on $Y$, and where the
$t_{\nu}=t_{\nu}(u)\in X$ are unique and satisfy

$\|u\|_{{\mathcal{B}}_{\rho,p}}<\infty,$ (19)

where

$\|u\|_{{\mathcal{B}}_{\rho,p}}:=\left\\{\begin{array}[]{ll}\left(\sum_{\nu\in{\mathcal{F}}}[\rho^{\nu}\|t_{\nu}\|_{X}]^{p}\right)^{1/p}=\|(\rho^{\nu}\|t_{\nu}\|_{X})_{\nu\in{\mathcal{F}}}\|_{\ell_{p}({\mathcal{F}})}&\mbox{if
}0<p<\infty\\\ &\\\
\sup_{\nu\in{\mathcal{F}}}\rho^{\nu}\|t_{\nu}\|_{X}&\mbox{if
}p=\infty.\end{array}\right.$ (20)

Note that these classes get smaller as $p$ decreases, i.e.,
${\mathcal{B}}_{\rho,p}\subset{\mathcal{B}}_{\rho,q}$ when $p\leq q$.

######  Remark 1.

We could define anisotropic spaces using other sequence norms in place of
$\ell_{p}$ norms (20), for instance Lorentz space norms. Moreover, different
classes of analytic anisotropic functions could be defined replacing the
Taylor basis $y^{\nu}$, $\nu\in{\mathcal{F}}$, by other polynomial bases, a
relevant example being a basis constituted of Legendre polynomials [7].

The goal of this work is to study nonlinear approximation for the model
classes ${\mathcal{B}}_{\rho,p}$, and more specifically to investigate the
approximation of $u\in{\mathcal{B}}_{\rho,p}$ by a library of $X$-valued
piecewise (Taylor) polynomials. The general idea is the following: we fix a
target accuracy $\varepsilon>0$ and an integer $m\geq 0$, and form a partition
$\\{Q_{i}\\}_{i=1}^{N}$ of $Y=[-1,1]^{\mathbb{N}}$ consisting of
$N:=N(\varepsilon,m)$ subdomains $Q_{i}$. These $Q_{i}$ are chosen such that
there is a $X$-valued polynomial of the form

$P_{i}(y)=\sum_{\nu\in\Lambda_{i}}t_{\nu,i}(y-\bar{y}^{i})^{\nu},\qquad\mbox{satisfying}\qquad\sup_{y\in
Q_{i}}\|u(y)-P_{i}(y)\|_{X}\leq\varepsilon,$

where $\bar{y}^{i}\in Q_{i}$, $\Lambda_{i}$ is a (lower) set of cardinality
$m+1$, and $t_{\nu,i}\in X$ for $\nu\in\Lambda_{i}$. In other words, since
$\Lambda_{i}$ is lower and thus contains the zero sequence, to each subdomain
$Q_{i}$ we associate an affine space of the form (16)

$L_{i}:=t_{0,i}+X_{i},\quad X_{i}:={\rm
span}\\{t_{\nu,i}:\,\,\nu\in\Lambda_{i}^{*}\\},\,\dim(X_{i})=m.$

For ease of both mathematical analysis and practical computation, we consider
a tensor product partition of $Y$, yielding a covering made of hyperrectangles
as defined in (29) below. This process, sketched in the proof of Theorem 5, is
done as in our previous work [5].

The goal is then to give an upper bound on the required number of subdomains,
i.e., on the size of the library, and provide a recipe to built a suitable
partition. The main ingredient for reaching that goal is the derivation of
local error estimates, namely the estimation of the error in the
$L^{\infty}(Q_{i},X)$ norm between $u\in{\mathcal{B}}_{\rho,p}$ and its
truncated Taylor series about some $\bar{y}^{i}\in Q_{i}$. Unlike the PDE
setting, such local error estimates cannot be deduced directly from a global
error estimate using a simple shifting and scaling argument. Nonetheless, we
first derive an error estimate on the whole parameter domain $Y$ for the error
between $u$ and a truncated Taylor series about the origin.

######  Theorem 1.

Let $u\in{\mathcal{B}}_{\rho,p}$ for some $1\leq p\leq\infty$, and let
$p^{\prime}$ denote the conjugate of $p$, i.e., $1/p+1/p^{\prime}=1$. Assume
that the sequence $\rho$ satisfies $\rho_{j}>1$ for all $j\geq 1$, and
$(\rho_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ for some $0<q<p^{\prime}$.
Then for any $m\geq 0$, there is a lower set $\Lambda$ with $\\#(\Lambda)=m+1$
such that the $X$-valued polynomial
$P(y):=\sum_{\nu\in\Lambda}t_{\nu}y^{\nu}$,
$t_{\nu}:=\partial_{\nu}u(0)/\nu!,$ satisfies

$\|u-P\|_{L^{\infty}(Y,X)}\leq
C(\rho,q)\|u\|_{{\mathcal{B}}_{\rho,p}}\|(\rho_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}(m+1)^{-r},\quad r:=-1+\frac{1}{p}+\frac{1}{q}>0,$ (21)

where $C(\rho,q)>0$ depends only on $q$ and the sequence $\rho$.

###### Proof.

We start by showing that there exists a polynomial $P$ with $m+1$ terms such
that

$\|u-P\|_{L^{\infty}(Y,X)}\leq\|u\|_{{\mathcal{B}}_{\rho,p}}\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}\|_{\ell_{q}}(m+1)^{-r}.$
(22)

Let $\Lambda$ be a lower set of indices $\nu\in{\mathcal{F}}$ corresponding to
the $m+1$ largest terms $\rho^{-\nu}$. Such a set, which may not be unique,
can be obtained by a proper handling of the possible ties in the
$\rho^{-\nu}$; see [6]. Recalling that $p^{\prime}$ denote the conjugate of
$p$, using the Hölder inequality we have for any $y\in Y$

$\|u(y)-P(y)\|_{X}\leq\sum_{\nu\notin\Lambda}\|t_{\nu}\|_{X}=\sum_{\nu\notin\Lambda}\|t_{\nu}\|_{X}\rho^{\nu}\rho^{-\nu}\leq\|u\|_{{\mathcal{B}}_{\rho,p}}\left[\sum_{\nu\notin\Lambda}\rho^{-\nu
p^{\prime}}\right]^{\frac{1}{p^{\prime}}}.$ (23)

Moreover, we easily get

$\sum_{\nu\notin\Lambda}\rho^{-\nu
p^{\prime}}=\sum_{\nu\notin\Lambda}\rho^{-\nu(p^{\prime}-q)}\rho^{-\nu
q}\leq\left[\sup_{\nu\notin\Lambda}\rho^{-\nu(p^{\prime}-q)}\right]\sum_{\nu\notin\Lambda}\rho^{-\nu
q}.$ (24)

We now let $(\gamma_{k})_{k\geq 1}$ be a non-increasing rearrangement of the
sequence $(\rho^{-\nu})_{\nu\in{\mathcal{F}}}$. We note that $\gamma_{1}$ will
always correspond to $\rho^{-0}$ due to the fact that $\rho_{j}>1$ for all
$j\geq 1$. Then we have

$\sup_{\nu\notin\Lambda}\rho^{-\nu
q}=\gamma^{q}_{m+2}\leq(m+1)^{-1}\sum_{k=2}^{m+2}\gamma_{k}^{q}\leq(m+1)^{-1}\sum_{k\geq
2}\gamma_{k}^{q}=(m+1)^{-1}\sum_{\nu\neq 0}\rho^{-q\nu}$ (25)

which implies

$\sup_{\nu\notin\Lambda}\rho^{-\nu}\leq(m+1)^{-\frac{1}{q}}\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}\|_{\ell_{q}}.$
(26)

Inserting (26) in (24) and then in (23) we get

$\displaystyle\|u(y)-P(y)\|_{X}$ $\displaystyle\leq$
$\displaystyle\|u\|_{{\mathcal{B}}_{\rho,p}}\left[\left\\{(m+1)^{-\frac{1}{q}}\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}\|_{\ell_{q}}\right\\}^{p^{\prime}-q}\right]^{\frac{1}{p^{\prime}}}\left[\sum_{\nu\notin\Lambda}\rho^{-\nu
q}\right]^{\frac{1}{p^{\prime}}}$ $\displaystyle\leq$
$\displaystyle\|u\|_{{\mathcal{B}}_{\rho,p}}(m+1)^{-\frac{p^{\prime}-q}{qp^{\prime}}}\left(\sum_{\nu\neq
0}\rho^{-\nu q}\right)^{\frac{p^{\prime}-q}{qp^{\prime}}}\left(\sum_{\nu\neq
0}\rho^{-\nu q}\right)^{\frac{1}{p^{\prime}}}$ $\displaystyle=$
$\displaystyle\|u\|_{{\mathcal{B}}_{\rho,p}}(m+1)^{-\frac{1}{q}+\frac{1}{p^{\prime}}}\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}\|_{\ell_{q}}.$

To conclude the proof, it remains to bound the $\ell_{q}$ norm of
$(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}$ by that of $(\rho_{j}^{-1})_{j\geq
1}$. Thanks to [5, Theorem 3.1] we have

$\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}\|_{\ell_{q}}\leq
C(\rho,q)\|(\rho_{j}^{-1})_{j\geq 1}\|_{\ell_{q}},$ (27)

where

$C(\rho,q):=\beta^{\frac{1}{q}}\exp\big{(}\frac{\beta}{q}\|(\rho_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}^{q}\big{)},\qquad\beta:=-\ln(1-\rho_{\min}^{-q})\rho_{\min}^{q},\quad\rho_{\min}:=\min_{j\geq
1}\rho_{j}>1,$ (28)

and the proof is complete. ∎

######  Remark 2.

The error estimate (22) is a straightforward extension of [5, Equation (3.13)]
to the general case $1\leq p\leq\infty$, and its proof is given here for
convenience. In [5, Equation (3.13)], which corresponds to the case $p=2$, the
constant $C_{\delta}$ is an upper bound for $\|u\|_{{\mathcal{B}}_{\rho,2}}$
obtained using the fact that $u$ is the solution to the elliptic parametric
PDE (12); see [1] for a proof of this _a priori_ estimate.

######  Remark 3.

Note that we could have considered the upper bound (22) with the norm
$\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}}\|_{\ell_{q}}$ instead of
$\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}\|_{\ell_{q}}$, namely without
excluding the zero sequence, in which case $(m+1)^{-r}$ can be replaced by
$(m+2)^{-r}$. The reason for having ${\mathcal{F}}^{*}$ is to be able to bound
$\|(\rho^{-\nu})_{\nu\in{\mathcal{F}}^{*}}\|_{\ell_{q}}$ by
$\|(\rho_{j}^{-1})_{j\geq 1}\|_{\ell_{q}}$ which is needed for the tensor
product partition of $Y$ considered in this work. Indeed, the cover of the
parameter domain $Y$ will be obtained as in [5] by partitioning some of the
directions $j=1,2,\ldots$, namely the ones contributing the most to the error.
This information is encoded in the sequence $(\rho_{j})_{j\geq 1}$, which
controls the anisotropy of $u\in{\mathcal{B}}_{\rho,p}$: a larger $\rho_{j}$
(and thus a smaller $\rho_{j}^{-1}$) indicates a smaller influence of the
variable $y_{j}$ on $u$.

As mentioned above, our library consists of local Taylor approximations and we
want to compute an upper bound on $N(\varepsilon,m)$, the cardinality of the
library for a given a target accuracy $\varepsilon$ and a dimension $m$. To do
this, we derive a local version of (21) in Theorem 1, i.e., we show a similar
error bound for the Taylor series coefficients around an arbitrary point
$\bar{y}\in Y:=[-1,1]^{\mathbb{N}}$. The general idea is this: assume again
that we are in the setting of Theorem 1 above, with $(\rho_{j}^{-1})_{j\geq
1}\in\ell_{q}(\mathbb{N})$ and $\rho_{j}>1$ for $j\geq 1$. Suppose then that
$Q_{\lambda}(\bar{y})\subset Y$ is a hyperrectangle centered at $\bar{y}$ with
side-lengths $2\lambda_{j}$, $j\geq 1$, i.e.

$Q_{\lambda}(\bar{y}):=\\{y\in\mathbb{R}^{\mathbb{N}}:\quad|y_{j}-\bar{y}_{j}|\leq\lambda_{j}\quad\forall
j\geq 1\\},$ (29)

where $\lambda_{j}\leq 1-|\bar{y}_{j}|$ so that $Q_{\lambda}(\bar{y})\subset
Y$. We would then like to show that for any $Q:=Q_{\lambda}(\bar{y})$ as in
(29) and any $m\geq 0$, there is a polynomial $P_{Q}$ with $m+1$ terms such
that

$\sup_{y\in Q}\|u(y)-P_{Q}(y)\|_{X}\leq C\|(\tilde{\rho}_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}(m+1)^{-r},\quad r=-1+\frac{1}{q}+\frac{1}{p},$ (30)

where $C=C(u,\rho,p,\bar{y})$ is some positive constant and

$\tilde{\rho}_{j}:=\frac{\rho_{j}-|\bar{y}_{j}|}{\lambda_{j}},\quad j\geq 1.$
(31)

Once the local error estimate (30) is established, then for any given center
$\bar{y}\in Y$ and integer $m\geq 0$, we can choose a sequence
$\lambda=(\lambda_{j})_{j\geq 1}$ so that the truncated Taylor series of $u$
about $y=\bar{y}$ with $m+1$ terms achieves the target accuracy $\varepsilon$
on $Q_{\lambda}(\bar{y})$. Indeed, the smaller $\lambda_{j}$ the larger
$\tilde{\rho}_{j}$ and thus the smaller the upper bound (30).

If we define the function $v$ via $v(y)=u(\bar{y}+\lambda y)$, $y\in Y$, we
then infer that the local error estimate (30) is proved if we can show that
$v$ satisfies the assumptions of Theorem 1 with the sequence
$\tilde{\rho}=(\tilde{\rho}_{j})_{j\geq 1}$ defined in (31). To see this,
first note that

$\tilde{\rho}_{j}=\frac{\rho_{j}-|\bar{y}_{j}|}{\lambda_{j}}=\rho_{j}\frac{1-|\bar{y}_{j}|/\rho_{j}}{\lambda_{j}}\geq\rho_{j}\frac{1-|\bar{y}_{j}|/\rho_{j}}{1-|\bar{y}_{j}|}\geq\rho_{j},$
(32)

so that if $(\rho_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ then
$(\tilde{\rho}_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ for the same value
of $q$. We also have the relationship
$\partial_{\nu}v(0)=\lambda^{\nu}\partial_{\nu}u(\bar{y})$. Hence, if we want
the Taylor series approximation of $u$ centered at $\bar{y}$ to achieve the
same order of approximation $(m+1)^{-r}$ in $Q_{\lambda}(\bar{y})$, we need to
show

$\sum_{\nu\in{\mathcal{F}}}\left[\left\|\frac{\partial_{\nu}v(0)}{\nu!}\right\|_{X}\tilde{\rho}^{\nu}\right]^{p}=\sum_{\nu\in{\mathcal{F}}}\left[\left\|\frac{\partial_{\nu}u(\bar{y})}{\nu!}\right\|_{X}(\rho-|\bar{y}|)^{\nu}\right]^{p}<\infty.$
(33)

Establishing (33), which is used to prove the first local estimate (see
Theorem 3), is accomplished in §4.

When $u$ is the solution to an elliptic parametric PDE of the form (12) with
affine diffusion coefficient as in (13), we know assumptions under which the
solution map $u$ satisfies the hypothesis of Theorem 1 with $p=2$. Then
because of the affine structure, the shifted and scaled function $v$ will
satisfy a similar parametric PDE, and thus we may apply Theorem 1. Our
previous work [5] uses that parametric PDE theory to show that local error
estimate holds. In the next section we prove that (33) holds without assuming
that $u$ is the affine parametric PDE solution map, namely when all we know
about $u$ is that it belongs to ${\mathcal{B}}_{\rho,p}$. To do so, we will
apply results from the field of interpolation theory.

##  3 Upper bound for a map between weighted sequences of Taylor coefficients

For an integer $1\leq r\leq\infty$, any positive sequence
$\rho=(\rho_{j})_{j\geq 1}$, and any $y\in Y$, we define the operator
$T_{\rho,y}:\ell_{r}({\mathcal{F}},X)\rightarrow\ell_{r}({\mathcal{F}},X)$ as

$T_{\rho,y}:(v_{\nu})_{\nu\in{\mathcal{F}}}\mapsto\left((\rho-|y|)^{\nu}\sum_{\mu\geq\nu}v_{\mu}\frac{\mu!}{(\mu-\nu)!\nu!}\rho^{-\mu}y^{\mu-\nu}\right)_{\nu\in{\mathcal{F}}}.$
(34)

For an analytic function $f:Y\rightarrow X$, this operator takes a weighted
sequence of Taylor coefficients at $0$ to a weighted sequence of Taylor
coefficients at $y$, i.e.,

$T_{\rho,y}:\left(\rho^{\nu}\frac{\partial_{\nu}f(0)}{\nu!}\right)_{\nu\in{\mathcal{F}}}\mapsto\left((\rho-|y|)^{\nu}\frac{\partial_{\nu}f(y)}{\nu!}\right)_{\nu\in{\mathcal{F}}}.$
(35)

Indeed, by definition of $T_{\rho,y}$ in (34), the $\nu$-term of the mapped
weighted sequence is

$(\rho-|y|)^{\nu}\sum_{\mu\geq\nu}\rho^{\mu}\frac{\partial_{\mu}f(0)}{\mu!}\frac{\mu!}{(\mu-\nu)!\nu!}\rho^{-\mu}y^{\mu-\nu}=(\rho-|y|)^{\nu}\frac{1}{\nu!}\sum_{\mu\geq\nu}y^{\mu-\nu}\frac{\partial_{\mu}f(0)}{(\mu-\nu)!}=(\rho-|y|)^{\nu}\frac{\partial_{\nu}f(y)}{\nu!},$

where for the last equality we used the relation (obtained by a Taylor
expansion)

$\partial_{\nu}f(y)=\sum_{\sigma\in{\mathcal{F}}}\frac{\partial_{\sigma}(\partial_{\nu}f(0))}{\sigma!}y^{\sigma}\stackrel{{\scriptstyle\mu=\sigma+\nu}}{{=}}\sum_{\mu\geq\nu}\frac{\partial_{\mu}f(0)}{(\mu-\nu)!}y^{\mu-\nu}.$

The following theorem is the main result of this section and will be a key
ingredient in the proof of the local error estimates given in the next
section.

######  Theorem 2.

Let $\rho=(\rho_{j})_{j\geq 1}$ be a sequence such that $\rho_{j}>1$ for all
$j\geq 1$, and let $y\in Y$. If $(|y_{j}|\rho_{j}^{-1})_{j\geq
1}\in\ell_{1}(\mathbb{N})$ then for any $1\leq p\leq\infty$ we have

$\|T_{\rho,y}\|_{\ell_{p}({\mathcal{F}},X)\rightarrow\ell_{p}({\mathcal{F}},X)}\leq\left(\prod_{j=1}^{\infty}\left(1-\frac{|y_{j}|}{\rho_{j}}\right)^{-1}\right)^{1-1/p}.$
(36)

###### Proof.

We first show that there exist two positive constants $M_{1},M_{\infty}$ such
that the map $T_{\rho,y}$ defined in (34) satisfies

$\|T_{\rho,y}\|_{\ell_{r}({\mathcal{F}},X)\rightarrow\ell_{r}({\mathcal{F}},X)}\leq
M_{r},\qquad r=1,\infty.$ (37)

Starting with the case $r=1$, we let
$v=(v_{\nu})_{\nu\in{\mathcal{F}}}\in\ell_{1}({\mathcal{F}},X)$. From the
definition of $T_{\rho,y}$ and the triangle inequality, we see that

$\displaystyle\|T_{\rho,y}v\|_{\ell_{1}({\mathcal{F}},X)}$
$\displaystyle=\sum_{\nu\in{\mathcal{F}}}\|(T_{\rho,y}v)_{\nu}\|_{X}$
$\displaystyle=\sum_{\nu\in{\mathcal{F}}}\left\|\sum_{\mu\geq\nu}v_{\mu}\frac{\mu!}{(\mu-\nu)!\nu!}y^{\mu-\nu}\rho^{-\mu}(\rho-|y|)^{\nu}\right\|_{X}$
$\displaystyle\leq\sum_{\nu\in{\mathcal{F}}}\sum_{\mu\geq\nu}\|v_{\mu}\|_{X}\frac{\mu!}{(\mu-\nu)!\nu!}|y|^{\mu-\nu}\rho^{-\mu}(\rho-|y|)^{\nu}.$

The latter series may be reordered as

$\sum_{\nu\in{\mathcal{F}}}\sum_{\mu\geq\nu}\|v_{\mu}\|_{X}\frac{\mu!}{(\mu-\nu)!\nu!}|y|^{\mu-\nu}\rho^{-\mu}(\rho-|y|)^{\nu}=\sum_{\mu\in{\mathcal{F}}}\|v_{\mu}\|_{X}\rho^{-\mu}\left(\sum_{\nu\leq\mu}\frac{\mu!}{(\mu-\nu)!\nu!}|y|^{\mu-\nu}(\rho-|y|)^{\nu}\right).$

By the binomial theorem, the inner sum is equal to $\rho^{\mu}$, so putting
together the previous string of inequalities yields

$\|T_{\rho,y}v\|_{\ell_{1}({\mathcal{F}},X)}\leq\sum_{\mu\in{\mathcal{F}}}\|v_{\mu}\|_{X}=\|v\|_{\ell_{1}({\mathcal{F}},X)}.$
(38)

This gives (37) for $r=1$ with constant $M_{1}=1$. We proceed in a similar
manner for the case $r=\infty$. Letting
$v=(v_{\nu})_{\nu\in{\mathcal{F}}}\in\ell_{\infty}({\mathcal{F}},X)$, we
estimate

$\displaystyle\|T_{\rho,y}v\|_{\ell_{\infty}({\mathcal{F}},X)}$
$\displaystyle=\sup_{\nu\in{\mathcal{F}}}\|(T_{\rho,y}v)_{\nu}\|_{X}$
$\displaystyle\leq\sup_{\nu\in{\mathcal{F}}}\sum_{\mu\geq\nu}\|v_{\mu}\|_{X}\frac{\mu!}{(\mu-\nu)!\nu!}|y|^{\mu-\nu}\rho^{-\mu}(\rho-|y|)^{\nu}$
$\displaystyle\leq\sup_{\mu\in{\mathcal{F}}}\left\\{\|v_{\mu}\|_{X}\rho^{\mu}\right\\}\sup_{\nu\in{\mathcal{F}}}\left\\{\sum_{\mu\geq\nu}\frac{\mu!}{(\mu-\nu)!\nu!}\prod_{j=1}^{\infty}\left(\frac{|y_{j}|}{\rho_{j}}\right)^{\mu_{j}-\nu_{j}}\left(1-\frac{|y_{j}|}{\rho_{j}}\right)^{\nu_{j}}\right\\}.$

Since $(|y_{j}|\rho_{j}^{-1})_{j\geq 1}\in\ell_{1}(\mathbb{N})$ by assumption,
the series on the last line is equal to

$\prod_{j=1}^{\infty}\left(1-\frac{|y_{j}|}{\rho_{j}}\right)^{-1}=:M_{\infty}<\infty,$
(39)

which gives in the case $r=\infty$. Finally, (36) is obtained from (37) by
applying the Riesz-Thorin theorem [2]:

$\|T_{\rho,y}\|_{\ell_{p}({\mathcal{F}},X)\rightarrow\ell_{p}({\mathcal{F}},X)}\leq
M_{1}^{1-\theta}M_{\infty}^{\theta},\qquad\theta=1-\frac{1}{p}.$ (40)

∎

######  Remark 4.

The assumption $(|y_{j}|\rho_{j}^{-1})_{j\geq 1}\in\ell_{1}(\mathbb{N})$ in
Theorem 2 is not needed if we are only interested in the case $p=1$; see (38).

##  4 Piecewise polynomial approximation for anisotropic analytic functions

We are now ready to derive a local version of Theorem 1, i.e., to prove an
approximation result of the form (30) on subdomains of $Y$. Throughout this
section, let $Q:=Q_{\lambda}(\bar{y})$ be as in (29), with center $\bar{y}\in
Y$ and side-length vector $\lambda$ satisfying $\lambda_{j}\leq
1-|\bar{y}_{j}|$ so that $Q\subset Y$. A first local error estimate for the
Taylor series at $\bar{y}$ in $Q$ is given in the following theorem.

######  Theorem 3.

Let $u\in{\mathcal{B}}_{\rho,p}$ for some $1\leq p\leq\infty$, and assume that
the sequence $\rho$ satisfies $\rho_{j}>1$ for all $j\geq 1$, and
$(\rho_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ for some $0<q\leq 1$. Then
for any $m\geq 0$, there is a set $\Lambda$ with $\\#(\Lambda)=m+1$ such that
the $X$-valued polynomial
$P_{Q}(y):=\sum_{\nu\in\Lambda}\frac{\partial_{\nu}u(\bar{y})}{\nu!}(y-\bar{y})^{\nu}$
satisfies

$\|u-P_{Q}\|_{L^{\infty}(Q,X)}\leq
C(\rho,q)\left(\prod_{j=1}^{\infty}\left(1-\frac{|\bar{y}_{j}|}{\rho_{j}}\right)^{-1}\right)^{1-\frac{1}{p}}\|u\|_{{\mathcal{B}}_{\rho,p}}\|(\tilde{\rho}_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}(m+1)^{-r},\quad r:=-1+\frac{1}{p}+\frac{1}{q},$ (41)

where

$\tilde{\rho}_{j}:=\frac{\rho_{j}-|\bar{y}_{j}|}{\lambda_{j}},\quad j\geq 1,$
(42)

and $C(\rho,q)$ is the positive constant defined in (28).

###### Proof.

As before, we define the function $v(y):=u(\bar{y}+\lambda y)$, $y\in Y$. We
will prove this theorem by showing that $v$ satisfies the assumptions of
Theorem 1 with the sequence $\tilde{\rho}$.

Recall from (32) that $\tilde{\rho}_{j}\geq\rho_{j},$ $j\geq 1$, so that if
$(\rho_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ then
$(\tilde{\rho}_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ for the same value
of $q$. We also have the relationship
$\partial_{\nu}v(0)=\lambda^{\nu}\partial_{\nu}u(\bar{y})$. Hence, if we want
to achieve the order of approximation $(m+1)^{-r}$ by the Taylor series
approximation in $Q$, we need to show that
$v\in{\mathcal{B}}_{\tilde{\rho},p}$. Recalling the definition of the map
$T_{\rho,\bar{y}}$, see in particular (35), we have

$\displaystyle\sum_{\nu\in{\mathcal{F}}}\left[\left\|\frac{\partial_{\nu}v(0)}{\nu!}\right\|_{X}\tilde{\rho}^{\nu}\right]^{p}$
$\displaystyle=$
$\displaystyle\sum_{\nu\in{\mathcal{F}}}\left[\left\|\frac{\partial_{\nu}u(\bar{y})}{\nu!}\right\|_{X}(\rho-|\bar{y}|)^{\nu}\right]^{p}$
$\displaystyle=$
$\displaystyle\|T_{\rho,\bar{y}}(\rho^{\nu}t_{\nu})_{\nu\in{\mathcal{F}}}\|_{\ell_{p}({\mathcal{F}},X)}^{p}$
$\displaystyle\leq$
$\displaystyle\|T_{\rho,\bar{y}}\|_{\ell_{p}({\mathcal{F}},X)\rightarrow\ell_{p}({\mathcal{F}},X)}^{p}\|u\|_{{\mathcal{B}}_{\rho,p}}^{p},$

where $t_{\nu}=\partial_{\nu}u(0)/\nu!$.

Hence, thanks to Theorem 2 we obtain

$\|v\|_{{\mathcal{B}}_{\tilde{\rho},p}}\leq\left(\prod_{j=1}^{\infty}\left(1-\frac{|\bar{y}_{j}|}{\rho_{j}}\right)^{-1}\right)^{1-\frac{1}{p}}\|u\|_{{\mathcal{B}}_{\rho,p}}.$
(43)

The right-hand side of (43) is finite since we have assumed
$u\in{\mathcal{B}}_{\rho,p}$ and

$(\rho_{j}^{-1})_{j\geq
1}\in\ell_{q}(\mathbb{N})\subseteq\ell_{1}(\mathbb{N})\quad\Longrightarrow\quad(|y_{j}|\rho_{j}^{-1})_{j\geq
1}\in\ell_{1}(\mathbb{N}).$

Thus $v\in{\mathcal{B}}_{\tilde{\rho},p}$, and by Theorem 1, there is a set
$\Lambda$ with $m+1$ terms, such that the polynomial
$P(y):=\sum_{\nu\in\Lambda}t_{\nu}(v)y^{\nu}$,
$t_{\nu}(v)=\partial_{\nu}v(0)/\nu!$, satisfies

$\|v-P\|_{L^{\infty}(Y,X)}\leq
C(\tilde{\rho},q)\|v\|_{{\mathcal{B}}_{\tilde{\rho},p}}\|(\tilde{\rho}_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}(m+1)^{-r},$

where $C(\tilde{\rho},q)$ is defined as in (28). Defining $P_{Q}(y)$ by

$P_{Q}(y)=P((y-\bar{y})/\lambda)=\sum_{\nu\in\Lambda}\frac{\partial_{\nu}u(\bar{y})}{\nu!}(y-\bar{y})^{\nu},$
(44)

it is easy to see that

$\|u-P_{Q}\|_{L^{\infty}(Q,X)}\leq
C(\tilde{\rho},q)\|v\|_{{\mathcal{B}}_{\tilde{\rho},p}}\|(\tilde{\rho}_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}(m+1)^{-r}.$ (45)

Finally, using again that $\tilde{\rho}_{j}\geq\rho_{j}$ for all $j\geq 1$,
and the fact that the function

$\beta(x)=-\ln(1-x^{-1})x,\quad x\in(1,\infty),$

is non-increasing, we have $C(\tilde{\rho},q)\leq C(\rho,q)$. Using this with
(43) in (45) yields the desired inequality (41). ∎

The drawback of Theorem 3 is the strong assumption that
$(\rho_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ for some $q\leq 1$. We now
show that we can get around this assumption by considering a slightly
different sequence, namely $(\kappa_{j})_{j\geq 1}:=(\rho_{j}^{\theta})_{j\geq
1}$ for some $0<\theta\leq 1$, while maintaining the same convergence rate
$(m+1)^{-r}$.

######  Theorem 4.

Let $u\in{\mathcal{B}}_{\rho,p}$ for some $1\leq p\leq\infty$, and assume the
sequence $\rho$ satisfies $\rho_{j}>1$ for all $j\geq 1$, and
$(\rho_{j}^{-1})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ for some
$0<q<\frac{p}{p-1}$. Let $(\kappa_{j})_{j\geq 1}$ be the sequence defined by
$\kappa_{j}:=\rho_{j}^{\theta}$, where $\theta:=1-\frac{q}{p^{\prime}}$ with
$p^{\prime}$ the conjugate of $p$. Then $u\in{\mathcal{B}}_{\kappa,1}$ and,
for each $m\geq 0$, there is a polynomial $P_{Q}$ with $m+1$ terms such that

$\|u-P_{Q}\|_{L^{\infty}(Q,X)}\leq
C(\kappa,q_{\theta})\|u\|_{{\mathcal{B}}_{\kappa,1}}\|(\tilde{\kappa}_{j}^{-1})_{j\geq
1}\|_{\ell_{q_{\theta}}}(m+1)^{-r},\quad r:=-1+\frac{1}{p}+\frac{1}{q},$ (46)

where $q_{\theta}:=\frac{q}{\theta}$ and

$\tilde{\kappa}_{j}:=\frac{\kappa_{j}-|\bar{y}_{j}|}{\lambda_{j}}=\frac{\rho_{j}^{\theta}-|\bar{y}_{j}|}{\lambda_{j}},\quad
j\geq 1.$ (47)

Note that $\theta=1-\frac{q}{p^{\prime}}$, defined in Theorem 4, indeed
belongs to $(0,1)$ whenever $p>1$, which follows from the assumption
$0<q<p^{\prime}=\frac{p}{p-1}$, while $\theta=1$ if $p=1$.

###### Proof.

We first show that $u\in{\mathcal{B}}_{\rho,p}$ implies that
$u\in{\mathcal{B}}_{\kappa,1}$. This is immediate when $p=1$, since in this
case we have $\theta=1$ and $\kappa=\rho$, and thus
$\|u\|_{{\mathcal{B}}_{\kappa,1}}=\|u\|_{{\mathcal{B}}_{\rho,p}}$. When
$1<p\leq\infty$, this follows from the relation

$\|u\|_{{\mathcal{B}}_{\kappa,1}}=\sum_{\nu\in{\mathcal{F}}}\kappa^{\nu}\|t_{\nu}\|_{X}=\sum_{\nu\in{\mathcal{F}}}\rho^{\nu}\|t_{\nu}\|_{X}\rho^{(\theta-1)\nu}\leq\|u\|_{{\mathcal{B}}_{\rho,p}}\Big{(}\sum_{\nu\in{\mathcal{F}}}\rho^{(\theta-1)p^{\prime}\nu}\Big{)}^{\frac{1}{p^{\prime}}},$
(48)

where the second sum converges since $(\theta-1)p^{\prime}=-q$. Moreover, it
is clear that

$\sum_{\nu\in{\mathcal{F}}}\kappa^{-q_{\theta}\nu}=\sum_{\nu\in{\mathcal{F}}}\rho^{-q\nu}<\infty,$
(49)

so that
$(\kappa^{-\nu})_{\nu\in{\mathcal{F}}}\in\ell_{q_{\theta}}({\mathcal{F}})$.
Then the rest of the proof follows that of Theorem 3 with $\rho$, $p$, and $q$
replaced by $\kappa$, $1$, and $q_{\theta}$, respectively. In this case
equation (43) gives

$\|v\|_{{\mathcal{B}}_{\tilde{\kappa},1}}\leq\|u\|_{{\mathcal{B}}_{\kappa,1}},$

which does not require the assumption $(\kappa_{j}^{-1})_{j\geq
1}\in\ell_{1}(\mathbb{N})$; see Remark 4. Moreover, the convergence rate $r$
is indeed as defined in (47) since

$r=-1+\frac{1}{1}+\frac{1}{q_{\theta}}=-1+\frac{1}{p}+\frac{1}{q}.$

∎

If we take $\bar{y}=(0,0,\ldots)$ and $\lambda=(1,1,\ldots)$, then Theorem 4
yields a global error estimate on $Q=Y$ using the sequence $\kappa$ in lieu of
$\rho$, i.e., instead of (21) we have

$\|u-P\|_{L^{\infty}(Y,X)}\leq
C(\kappa,q_{\theta})\|u\|_{{\mathcal{B}}_{\kappa,1}}\|(\kappa_{j}^{-1})_{j\geq
1}\|_{\ell_{q_{\theta}}}(m+1)^{-r}$ (50)

for some polynomial $P=P(y)$ with $m+1$ terms. We compare in the next section
the global error estimates (21) and (50).

######  Remark 5.

According to the proof of Theorem 1, the bound (22) is achieved by
$P(y):=\sum_{\nu\in\Lambda}t_{\nu}y^{\nu}$, where $\Lambda$ is a lower set
with multi-indices corresponding to the $(m+1)$ largest $\rho^{-\nu}$. Then
(50) is achieved by the same polynomial since

$\rho^{-\nu}\geq\rho^{-\mu}\quad\Longrightarrow\quad\kappa^{-\nu}=(\rho^{-\nu})^{\theta}\geq(\rho^{-\mu})^{\theta}=\kappa^{-\mu};$

in other words, the ordering for the $\kappa^{-\nu}$ is the same as the one
for the $\rho^{-\nu}$, and the corresponding multi-index set $\Lambda$ is the
same for both sequences (provided that ties in the size of the $\rho^{-\nu}$
are handled in the same way).

##  5 Comparison of the global error bounds

We now turn to the comparison of the global error estimates using the sequence
$\rho$ versus those using $\kappa$, namely of the upper bounds for the error
in the $L^{\infty}(Y,X)$ norm given in (21) and (50), respectively. For ease
of reference, we briefly recall the bounds on $p$ and $q$, and a few relevant
definitions:

$1\leq p\leq\infty,\quad
0<q<\frac{p}{p-1},\quad\kappa_{j}=\rho_{j}^{\theta},\quad\theta=1-\frac{q}{p^{\prime}}\in(0,1],\quad
p^{\prime}=\frac{p}{p-1}.$

Note that if $p=1$, then $\theta=1$ and thus the two estimates coincide. If
$p>1$, then $\theta\in(0,1)$, and we will thus consider only this case from
now on.

The two error estimates consist of four terms that we compare below.

  * 1.

$(m+1)^{-r}$: The convergence rate $r$ is the same in both error estimates,
namely $r=-1+1/p+1/q$, and thus this term is the same in both error estimates.

  * 2.

$\|(\rho_{j}^{-1})_{j\geq 1}\|_{\ell_{q}}$ versus $\|(\kappa_{j}^{-1})_{j\geq
1}\|_{\ell_{q_{\theta}}}$: We have

$\|(\kappa_{j}^{-1})_{j\geq 1}\|_{\ell_{q_{\theta}}}=\|(\rho_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}^{\theta}.$ (51)

Now whether $\|(\kappa_{j}^{-1})_{j\geq 1}\|_{\ell_{q_{\theta}}}$ is smaller
than $\|(\rho_{j}^{-1})_{j\geq 1}\|_{\ell_{q}}$ depends on whether
$\|(\rho_{j}^{-1})_{j\geq 1}\|_{\ell_{q}}$ is larger than one or not. Indeed,
since $\theta\in(0,1)$ we have

$\|(\kappa_{j}^{-1})_{j\geq
1}\|_{\ell_{q_{\theta}}}\leq\|(\rho_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}\quad\mbox{if}\quad\|(\rho_{j}^{-1})_{j\geq 1}\|_{\ell_{q}}\geq
1$ (52)

with reverse inequality otherwise.

  * 3.

$C(\rho,q)$ versus $C(\kappa,q_{\theta})$: Recall that these constants are
defined by (28). Since $\rho_{j}>1$ for all $j\geq 1$ and $\theta\in(0,1)$, we
have $\kappa_{j}=\rho_{j}^{\theta}<\rho_{j}$. Moreover,
$\kappa_{\min}=\rho_{\min}^{\theta}$ and thus the $\beta$ in $C(\rho,q)$ and
$C(\kappa,q_{\theta})$ are the same:

$\beta:=-\ln\left(1-\rho_{\min}^{-q}\right)\rho_{\min}^{q}=-\ln\left(1-\kappa_{\min}^{-\frac{q}{\theta}}\right)\kappa_{\min}^{\frac{q}{\theta}}=-\ln\left(1-\kappa_{\min}^{-q_{\theta}}\right)\kappa_{\min}^{q_{\theta}}.$

Therefore, we have

$C(\kappa,q_{\theta})=\beta^{\frac{\theta}{q}}\exp\left(\frac{\beta\theta}{q}\|(\kappa_{j}^{-1})_{j\geq
1}\|_{\ell_{q_{\theta}}}^{\frac{q}{\theta}}\right)\stackrel{{\scriptstyle\eqref{rel:norms}}}{{=}}\beta^{\frac{\theta}{q}}\exp\left(\frac{\beta\theta}{q}\|(\rho_{j}^{-1})_{j\geq
1}\|_{\ell_{q}}^{q}\right)=C(\rho,q)^{\theta}\leq C(\rho,q),$

where for the last inequality we used the fact that $C(\rho,q)\geq 1$ since
$\beta\geq 1$. Indeed, we have

$\ln(1-x)=-x-\frac{x^{2}}{2}-\frac{x^{3}}{3}-\ldots=-\sum_{k=1}^{\infty}\frac{x^{k}}{k}$

and thus

$\beta=-\ln\left(1-\rho_{\min}^{-q}\right)\rho_{\min}^{q}=\sum_{k=1}^{\infty}\frac{\rho_{\min}^{(1-k)q}}{k}=1+\sum_{k=2}^{\infty}\frac{\rho_{\min}^{(1-k)q}}{k}\geq
1.$

  * 4.

$\|u\|_{\mathcal{B}_{\rho,p}}$ versus $\|u\|_{\mathcal{B}_{\kappa,1}}$: From
(48), we directly have that

$\|u\|_{\mathcal{B}_{\kappa,1}}\leq
K\|u\|_{\mathcal{B}_{\rho,p}},\quad\mbox{where
}K:=\Big{(}\sum_{\nu\in{\mathcal{F}}}\rho^{(\theta-1)p^{\prime}\nu}\Big{)}^{\frac{1}{p^{\prime}}}\in(1,\infty).$

Therefore, if $K\gg 1$ then $\|u\|_{\mathcal{B}_{\kappa,1}}$ could potentially
be much larger than $\|u\|_{\mathcal{B}_{\rho,p}}$. Moreover, we do not have a
reversed inequality of the form
$k\|u\|_{\mathcal{B}_{\rho,p}}\leq\|u\|_{\mathcal{B}_{\kappa,1}}$ for some
constant $k>0$, as this would imply that the spaces ${\mathcal{B}}_{\rho,p}$
and ${\mathcal{B}}_{\kappa,1}$ are the same.

##  6 Bounds on the library size

In this section, we use the local error upper bound (46) to build a library
consisting of piecewise Taylor polynomials. Without loss of generality, we
assume that the target accuracy $\varepsilon>0$ and the dimension $m\geq 0$
are such that

$C\|(\kappa_{j}^{-1})_{j\geq 1}\|_{\ell_{q}}(m+1)^{-r}>\varepsilon,\quad
C:=C(\kappa,q_{\theta})\|u\|_{\mathcal{B}_{\kappa,1}},$ (53)

where $C(\kappa,q_{\theta})$ is the constant defined in (28),
$\kappa_{j}=\rho_{j}^{\theta}$ and $\theta=1-\frac{q}{p^{\prime}}$ as in
Theorem 4. Indeed, if (53) does not hold, then there is no need to partition
the parameter domain, since thanks to the global error estimate (50) there is
a Taylor series approximation centered at the origin with $m+1$ terms
satisfying the prescribed accuracy $\varepsilon$.

######  Theorem 5.

Let $u\in\mathcal{B}_{\rho,p}$ for some $1\leq p\leq\infty$, and assume that
the sequence $\rho$ is nondecreasing with $\rho_{1}>1$ and satisfies
$(\rho^{-1}_{j})_{j\geq 1}\in\ell_{q}(\mathbb{N})$ for some
$0<q<\frac{p}{p-1}$. Let $q_{\theta}=q/\theta$ with $\theta=1-q/p^{\prime}$,
where $p^{\prime}$ is the conjugate of $p$. Finally, let $\varepsilon>0$,
$m\geq 0$ and assume that (53) holds. Then, there exists a tensor product
partition of $Y$ into a collection ${\mathcal{R}}$ of $N:=N(\varepsilon,m)$
hyperrectangles such that on each $Q\in{\mathcal{R}}$ there is a $X$-valued
polynomial $P_{Q}$ with $m+1$ terms such that

$\|u(y)-P_{Q}(y)\|_{X}\leq\varepsilon,\quad y\in Q.$ (54)

Furthermore, if $J:=J(\varepsilon,m)\geq 1$ is the smallest integer such that

$\sum_{j\geq
J+1}\rho_{j}^{-q}\leq\frac{1}{2}C^{-q_{\theta}}(m+1)^{q_{\theta}r}\varepsilon^{q_{\theta}},$
(55)

where $C$ is the constant in (53), and

$\sigma:=\left(\frac{1}{2J}\right)^{\frac{1}{q_{\theta}}}C^{-1}(m+1)^{r}\varepsilon,$
(56)

then the partition is obtained by only subdividing in the first $J$
directions, and the number of cells $N$ in this partition satisfies

$N\leq\prod_{j=1}^{J}\left(\sigma^{-1}|\ln(1-\rho_{j}^{-\theta})|+C({\sigma})\right)\quad\mbox{for
some}\quad C({\sigma})\in(1,2).$ (57)

###### Proof.

This proof follows closely that of [5, Theorem 3.5]. The main difference is
that we will use the local error estimate (46) to build a tensor product
partition of $Y$, i.e., we use the sequence $(\kappa_{j})_{j\geq
1}=(\rho_{j}^{\theta})_{j\geq 1}$ instead of $(\rho_{j})_{j\geq 1}$, and
consider the $\ell_{q_{\theta}}(\mathbb{N})$ norm instead of the
$\ell_{q}(\mathbb{N})$ norm. However, the strategy for partitioning $Y$ is
similar, as is the proof of the bound (57), but we give the details of the
partitioning here for the reader’s convenience.

First, since $(\rho_{j})_{j\geq 1}$ is nondecreasing by assumption,
$(\kappa_{j})_{j\geq 1}$ is likewise nondecreasing. According to (46), for any
hyperrectangle $Q$, centered at $\bar{y}$ with side-length vector
$(\lambda_{j})_{j\geq 1}$, a sufficient condition to have
$\|u-P_{Q}\|_{L^{\infty}(Q,X)}\leq\varepsilon$ is to have

$\sum_{j\geq
1}\left(\frac{\rho_{j}^{\theta}-|\bar{y}_{j}|}{\lambda_{j}}\right)^{-q_{\theta}}=\sum_{j\geq
1}\tilde{\kappa}_{j}^{-q_{\theta}}\leq
C^{-q_{\theta}}(m+1)^{rq_{\theta}}\varepsilon^{q_{\theta}}=:\eta,$ (58)

where $C$ is defined in (53), and $P_{Q}$ is a polynomial with $m+1$ terms.
Note that if we set set $\bar{y}_{j}=0$ and $\lambda_{j}=1$ for $j\geq J+1$,
where $J$ is given in (55), the tail of the series in (58) contributes to
_half of the error_ , namely

$\sum_{j\geq J+1}\tilde{\kappa}_{j}^{-q_{\theta}}=\sum_{j\geq
J+1}(\rho_{j}^{\theta})^{-q_{\theta}}=\sum_{j\geq
J+1}\rho_{j}^{-q}\leq\frac{1}{2}\eta.$ (59)

Thus, the strategy is to subdivide only in the directions $j=1,\ldots,J$, and
we do this so that the remaining error is equidistributed among the first $J$
directions. This is accomplished by requiring that the center $\bar{y}_{j}$
and the sidelength $\lambda_{j}$ of each subinterval satisfies

$\tilde{\kappa}_{j}=\frac{\rho_{j}^{\theta}-|\bar{y}_{j}|}{\lambda_{j}}=\sigma^{-1},\quad
1\leq j\leq J,$ (60)

yielding

$\sum_{j=1}^{J}\tilde{\kappa}_{j}^{-q_{\theta}}=\sum_{j=1}^{J}\sigma^{q_{\theta}}=\frac{1}{2}\eta.$
(61)

To define the tensor product grid, for each coordinate direction $y_{j}$,
$j=1,\dots,J$, we first define how we subdivide the interval $[-1,1]$ into
$(2k_{j}+1)$ subintervals

$I_{j}^{i},\quad-k_{j}\leq i\leq k_{j}.$

We do not subdivide any of the coordinate axis when $j>J$, i.e., $k_{j}=0$ and
$I_{j}^{0}=[-1,1]$ when $j>J$. The partition is also chosen to be symmetric
and so $I_{j}^{-i}=-I_{j}^{i}$, $i=1,\dots,k_{j}$.

We fix $j\in\\{1,\dots,J\\}$ and describe the partition of $[-1,1]$ into
intervals corresponding to the $j$-th coordinate. Our first interval
$I_{j}^{0}$ is centered at $\bar{y}_{j}^{0}=0$ and according to (60), we set
$\lambda_{j}^{0}=\sigma\rho_{j}^{\theta}$ provided this number is less than
one. Otherwise, when $\sigma\rho_{j}^{\theta}\geq 1$, we define
$\lambda_{j}^{0}:=1$, in which case $k_{j}=0$ and the partition consists only
of the one interval $I_{j}^{0}=[-1,1]$. Note that since
$(\rho_{j}^{\theta})_{j\geq 1}$ is nondecreasing, when this occurs it also
happens for all larger values of $j$.

As mentioned above, the partition is symmetric with respect to the origin and
so we only describe the intervals to the right of the origin. The next
interval $I_{j}^{1}$, with center $\bar{y}_{j}^{1}$ and sidelength
$\lambda_{j}^{1}$, has left endpoint the same as the right endpoint of
$I_{j}^{0}$, i.e.,

$\bar{y}_{j}^{1}-\lambda_{j}^{1}=\bar{y}_{j}^{0}+\lambda_{j}^{0}.$

Now to satisfy (60), we choose

$\lambda_{j}^{1}=\sigma(\rho_{j}^{\theta}-\bar{y}_{j}^{1})\quad\implies\quad\lambda_{j}^{1}=\frac{\sigma}{1+\sigma}(\rho_{j}^{\theta}-\bar{y}_{j}^{0}-\lambda_{j}^{0}).$

The only exception to this definition is when the right endpoint of this
interval is larger than 1. Then we recenter the interval so its left endpoint
is as before and its right endpoint is 1. In this case, we would stop the
process and $k_{j}$ would be 1.

We continue in this same way moving to the right. In general, the interval
$I_{j}^{i}$ will have its left endpoint equal to the right endpoint of
$I_{j}^{i-1}$, with center $\bar{y}_{j}^{i}$ and sidelength $\lambda_{j}^{i}$
which satisfy

$\lambda_{j}^{i}=\sigma(\rho_{j}^{\theta}-\bar{y}_{j}^{i}).$ (62)

As before, we rescale in the case that such a choice would give a right
endpoint larger than 1 and terminate the partitioning process. It follows that
the interval $I_{j}^{i}$ always satisfies

$\lambda_{j}^{i}\leq\sigma(\rho_{j}^{\theta}-\bar{y}_{j}^{i}),\quad
i=0,1,\dots,k_{j},$ (63)

with equality except for possibly the last interval $I_{j}^{k_{j}}$. This
partitioning gives a tensor product set ${\mathcal{R}}$ of hyperrectangles
$Q$.

To conclude the proof, it remains to derive a bound for the number of elements
${\mathcal{R}}$ given by

$N=\prod_{j=1}^{J}(2k_{j}+1),$

namely to show that when $k_{j}\neq 0,j=1,\ldots,J,$ we have

$2k_{j}+1\leq\left(\sigma^{-1}|\ln\left(1-\rho_{j}^{-\theta}\right)|+{C({\sigma})}\right).$
(64)

Since the proof is technical and follows the same arguments as in [5, Theorem
3.5], we do not provide the details here. ∎

Note that although the error is distributed equally among all the directions
$j=1,2,\ldots,J$, see (60), the partition obtained using the strategy
described in the proof of Theorem 5 is anisotropic in general. Indeed, the
number of subintervals $2k_{j}+1$ in direction $j$ is controlled by $\rho_{j}$
through the bound (64).

######  Remark 6.

The upper bound (57) is similar to [5, Equation (3.29)] which reads

$N\leq\prod_{j=1}^{\tilde{J}}\left(\tilde{\sigma}^{-1}|\ln(1-\rho_{j}^{-1})|+C({\tilde{\sigma}})\right)\quad\mbox{for
some}\quad C({\tilde{\sigma}})\in(1,2);$ (65)

notice the factor $\rho_{j}^{-1}$ instead of $\rho_{j}^{-\theta}$ in (57). In
(65), $\tilde{J}$ is the smallest integer such that

$\sum_{j\geq
J+1}\rho_{j}^{-1}\leq\frac{1}{2}\tilde{C}^{-q}(m+1)^{qr}\varepsilon^{q},$

where $\tilde{C}=C(\rho,q)C_{\delta}$ with $C(\rho,q)$ as in (27) and
$C_{\delta}$ an upper bound for $\|u\|_{{\mathcal{B}}_{\rho,2}}$, and

$\tilde{\sigma}:=\left(\frac{1}{2J}\right)^{\frac{1}{q}}\tilde{C}^{-1}(m+1)^{r}\varepsilon.$

######  Remark 7.

We can obtain explicit upper bounds for $N$ when considering specific
sequences $\rho$. For example, if we assume that $(\rho_{j})_{j\geq
1}=(Mj^{s})_{j\geq 1}$ for some fixed $M>1$ and $s>1/2$, then proceeding as in
[5, Section 3.3] we have $\sigma\sim J^{-s\theta}$,
$|\ln(1-\rho_{j}^{-\theta})|\lesssim j^{-s\theta}$, and
$J\sim\lambda^{\frac{q_{\theta}}{1-sq}}$. Therefore, inserting these relations
in (57) we infer that

$N\lesssim J^{s\theta J}(J!)^{-s\theta}\leq
e^{c\lambda^{\frac{q_{\theta}}{1-sq}}}=e^{c\lambda^{\frac{q}{\theta(1-sq)}}},\quad\lambda:=(m+1)^{r}\varepsilon,$

for some constant $c>0$ independent of $q$.

##  7 Conclusion

In this article, we extend the nonlinear reduced model introduced in [5] to
approximate more general high-dimensional functions, namely to approximate the
class ${\mathcal{B}}_{\rho,p}$ of _anisotropic analytic_ functions studied in
[6]. The nonlinear reduced model, which belongs to the category of library
approximation, is obtained by partitioning the parameter domain and by using a
different truncated Taylor series on each subdomain. In Theorem 5, we give an
upper bound on the number of subdomains (and thus on the size of the library)
needed to achieve a prescribed accuracy while using a prescribed number of
terms for each truncated Taylor series. The key ingredient needed to obtain
such partition is a local error estimate quantifying, for any subdomain, the
worst-case error between the exact solution and a local Taylor polynomial.
Indeed, once a local error estimate is available, then the partition strategy
proposed in [5] can be straightforwardly applied.

In the elliptic PDE setting of [5], a local error estimate can be obtained by
a simple scaling and shifting argument. This is not possible in the general
case considered here, where the only information we have on the function we
want to approximate is that it belongs to the class ${\mathcal{B}}_{\rho,p}$,
and a more refined argument is needed. The main results of this work are thus
Theorems 3 and 4 where we derive local error estimates. The upper bound
obtained in Theorem 3 holds under the (strong) assumption that the sequence
$\rho$ satisfy $(\rho_{j}^{-1})_{j\geq 1}\in\ell_{1}(\mathbb{N})$. This
assumption is not needed for the bound of Theorem 4, which involves a slightly
different sequence than the original sequence $\rho$.

We conclude by mentioning that given a particular function
$u\in{\mathcal{B}}_{\rho,p}$, a number of terms $m+1$ and an error tolerance
$\varepsilon$, the partition considered in the proof of Theorem 5 is not
optimal in the sense that it does not provide a library ${\mathcal{L}}$ of
minimal cardinality (with affine spaces of dimension $m$) such that
$E_{{\mathcal{L}}}({\mathcal{M}})\leq\varepsilon$ for
${\mathcal{M}}=\\{u(y):\,y\in Y\\}$. In particular, we restrict the
approximations to (i) piecewise Taylor polynomials and (ii) tensor-product
based partitions of $Y$. There are thus opportunities for improvement, for
instance by considering other strategies for partitioning the parameter domain
as well as other types of spaces (such as piecewise Legendre polynomials or
local reduced basis). Nonetheless, the proposed procedure for building a
library given $u\in{\mathcal{B}}_{\rho,p}$, $m$ and $\varepsilon$ is easy to
implement and the library is computationally cheap to construct.

## Acknowledgements

The authors would like to thank Albert Cohen, Ron DeVore, Guergana Petrova,
and Andrea Bonito for helpful discussions.

## References

  * [1] M. Bachmayr, A. Cohen, and G. Migliorati, Sparse polynomial approximation of parametric elliptic PDEs. Part I: affine coefficients, ESAIM:Mathematical Modelling and Numerical Analysis, 51 (2017), pp. 321–339.
  * [2] J. Bergh and J. Löfström, Interpolation spaces: an introduction, vol. 223, Springer Science & Business Media, 2012.
  * [3] P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk, Convergence rates for greedy algorithms in reduced basis methods, SIAM Journal on Mathematical Analysis, 43 (2011), pp. 1457–1472.
  * [4] , Data assimilation in reduced modeling, SIAM/ASA Journal on Uncertainty Quantification, 5 (2017), pp. 1–29.
  * [5] A. Bonito, A. Cohen, R. DeVore, D. Guignard, P. Jantsch, and G. Petrova, Nonlinear methods for model reduction, ESAIM: Mathematical Modelling and Numerical Analysis, 55 (2021), pp. 507–531.
  * [6] A. Bonito, R. DeVore, D. Guignard, P. Jantsch, and G. Petrova, Polynomial approximation of anisotropic analytic functions of several variables, Constructive Approximation, 53 (2021), pp. 319–348.
  * [7] A. Chkifa, A. Cohen, and C. Schwab, Breaking the curse of dimensionality in sparse polynomial approximation of parametric pdes, Journal de Mathématiques Pures et Appliquées, 9 (2015), pp. 400–428.
  * [8] A. Cohen, W. Dahmnen, R. DeVore, and J. Nichols, Reduced basis greedy selection using random training sets, ESAIM:Mathematical Modelling and Numerical Analysis, 54 (2020), pp. 1509–1524.
  * [9] A. Cohen and R. DeVore, Approximation of high-dimensional parametric PDEs, Acta Numerica, 24 (2015), pp. 1–159.
  * [10] R. DeVore, Nonlinear approximation, Acta Numerica, 7 (1998), pp. 51–150.
  * [11] J. Eftang, A. Patera, and E. Rønquist, An “hp” certified reduced basis method for parametrized elliptic partial differential equations, SIAM Journal on Scientific Computing, 32 (2010), pp. 3170–3200.
  * [12] Y. Maday and B. Stamm, Locally adaptive greedy approximations for anisotropic parameter reduced basis spaces, SIAM Journal on Scientific Computing, 35 (2013), pp. A2417–A2441.
  * [13] V. Temlykov, Nonlinear Kolmogorov widths, Mathematical Notes, 63 (1998), pp. 785–795.
  * [14] J. Zech, Sparse-grid approximation of high-dimensional parametric pdes.
  * [15] Z. Zou, D. Kouri, and W. Aquino, An adaptive local reduced basis method for solving PDEs with uncertain inputs and evaluating risk, Computer Methods in Applied Mechanics and Engineering, 345 (2019), pp. 302–322.