# Optimal randomized quadrature for weighted Sobolev and Besov classes with
the Jacobi weight on the ball

Jiansong Li  School of Mathematical Sciences, Capital Normal University,
Beijing 100048, China<EMAIL_ADDRESS>and  Heping Wang  School of
Mathematical Sciences, Capital Normal University, Beijing 100048, China
<EMAIL_ADDRESS>
###### Abstract.

We consider the numerical integration

${\rm INT}_{d}(f)=\int_{\mathbb{B}^{d}}f(x)w_{\mu}(x)dx$

for the weighted Sobolev classes $BW^{r}_{p,\mu}$ and the weighted Besov
classes $BB_{\tau}^{r}(L_{p,\mu})$ in the randomized case setting, where
$w_{\mu},\,\mu\geq 0,$ is the classical Jacobi weight on the ball
$\mathbb{B}^{d}$, $1\leq p\leq\infty$, $r>(d+2\mu)/p$, and $0<\tau\leq\infty$.
For the above two classes, we obtain the orders of the optimal quadrature
errors in the randomized case setting are $n^{-r/d-1/2+(1/p-1/2)_{+}}$.
Compared to the orders $n^{-r/d}$ of the optimal quadrature errors in the
deterministic case setting, randomness can effectively improve the order of
convergence when $p>1$.

###### Key words and phrases:

Optimal quadrature error; Weighted Sobolev classes; Weighted Besov classes;
Deterministic case setting; Randomized case setting; Filtered
hyperinterpolation.

###### 2010 Mathematics Subject Classification:

41A55, 65D30, 65D32

##  1\. Introduction

Let $F_{d}$ be a class of continuous functions on $D_{d}$, where $D_{d}$ is a
compact subset of the Euclidean space $\mathbb{R}^{d}$ with a probability
measure $\rho$. The integral of a continuous function
$f:\,F_{d}\rightarrow\,{R}$ denotes by

(1.1) ${\rm INT}_{d}(f)=\int_{D_{d}}f(x)d\rho(x).$

We want to approximate this integral ${\rm INT}_{d}(f)$ by (deterministic)
algorithms of the form

$A_{n}(f):=\varphi_{n}(f(x_{1}),f(x_{2}),\dots,f(x_{n})),$

where $x_{j}\in D_{d}$ can be chosen adaptively and
$\varphi_{n}:{R}^{n}\rightarrow{R}$ is an arbitrary mapping. Adaption means
that the selection of $x_{j}$ may depend on the already computed values
$f(x_{1}),f(x_{2}),\dots,f(x_{j-1})$. We denoted by $\mathcal{A}_{n}^{\rm
det}$ the class of all algorithms of this form. If $x_{1},\dots,x_{n}$ are
fixed and $\varphi_{n}$ is linear, i.e.,

$A_{n}(f)=\sum_{j=1}^{n}{\lambda}_{j}f(x_{j}),\ \ {\lambda}_{j}\in{R},\
j=1,\dots,n,$

then the algorithm $A_{n}$ is called a linear algorithm. Such linear algorithm
$A_{n}$ is also called a quadrature formula. We say that a quadrature formula
$A_{n}$ is positive if ${\lambda}_{j}>0,\,j=1,\dots,n$.

The deterministic case error of $A_{n}$ on $F_{d}$ is given by

$e^{\rm det}(F_{d},A_{n}):=\sup\limits_{f\in F_{d}}|{\rm
INT}_{d}(f)-A_{n}(f)|,$

and the minimal (optimal) deterministic case error on $F_{d}$ given by

$e_{n}^{\rm det}(F_{d}):=\inf\limits_{A_{n}\in\mathcal{A}_{n}^{\rm det}}e^{\rm
det}(F_{d},A_{n}).$

It was well known (see [3]) that if $F_{d}$ is convex and balanced, then
$e_{n}^{\rm det}(F_{d})$ can be achieved by linear algorithms. Hence
$e_{n}^{\rm det}(F_{d})$ is also called the optimal quadrature error.

Randomized algorithms, called also Monte-Carlo algorithms, are understood as
$\Sigma\otimes\mathcal{B}(F_{d})$ measurable functions

$(A^{\omega})=(A^{\omega}(\cdot))_{{\omega}\in\Omega}:\Omega\times
F_{d}\to{R},$

where $\mathcal{B}(F_{d})$ denotes Borel $\sigma$-algebra of $F_{d}$,
$(\Omega,\Sigma,\mathcal{P})$ is a suitable probability space, and for any
fixed ${\omega}\in\Omega$, $A^{\omega}$ is a deterministic method with
cardinality $n(f,{\omega})$. The number $n(f,{\omega})$ may be randomized and
adaptively depend on the input, and the cardinality of $(A^{\omega})$ is then
defined by

${\rm Card}(A^{\omega}):=\sup_{f\in
F_{d}}\mathbb{E}_{\omega}\,n(f,{\omega}):=\sup\limits_{f\in
F_{d}}\int_{\Omega}n(f,\omega)d\mathcal{P}(\omega).$

We denote by $\mathcal{A}_{n}^{\rm ran}$ the class of all randomized
algorithms with cardinality not exceeding $n$.

The randomized case error of $(A^{\omega})$ on $F_{d}$ is defined by

$e^{\rm ran}(F_{d},(A^{\omega})):=\sup\limits_{f\in F_{d}}{E}_{\omega}|{\rm
INT}_{d}(f)-A^{\omega}(f)|,$

and the minimal (optimal) randomized case error on $F_{d}$ is defined by

$e_{n}^{\rm ran}(F_{d}):=\inf\limits_{(A^{\omega})\in\mathcal{A}_{n}^{\rm
ran}}e^{\rm ran}(F_{d},(A^{\omega})).$

There are many papers devoted to investigating the integration problem (1.1)
in the deterministic and randomized case settings. Compared to deterministic
algorithms, randomized algorithms may speed up the order of convergence in
many cases, especially for integration problem. We recall some known results.

Throughout the paper, the notation $a_{n}\asymp b_{n}$ means $a_{n}\lesssim
b_{n}$ and $a_{n}\gtrsim b_{n}$. Here, $a_{n}\lesssim b_{n}\,(a_{n}\gtrsim
b_{n})$ means that there exists a constant $c>0$ independent of $n$ such that
$a_{n}\leq cb_{n}\,(b_{n}\leq ca_{n})$.

(1) Consider the classical Sobolev class $BW_{p}^{r}([0,1]^{d})$, $1\leq
p\leq\infty$, $r\in{N}$, defined by

$BW_{p}^{r}([0,1]^{d})=\big{\\{}f\in
L_{p}([0,1]^{d})\,\big{|}\,\sum_{|\alpha|_{1}\leq r}\|D^{\alpha}f\|_{p}\leq
1\big{\\}},$

and the Hölder class $C^{k,{\gamma}}_{d}$, $k\in{N}_{0}$, $0<{\gamma}\leq 1$,
defined by

$C^{k,\gamma}_{d}:=\big{\\{}f\in
C([0,1]^{d})\,\big{|}\,|D^{\alpha}f(x)-D^{\alpha}f(y)|\leq\max\limits_{1\leq
i\leq d}|x_{i}-y_{i}|^{\gamma},\,|{\alpha}|_{1}=k\big{\\}},$

where ${\alpha}\in{N}_{0}^{d},\
|\alpha|_{1}:=\sum\limits_{i=1}^{d}\alpha_{i}$, and $D^{\alpha}f$ is the
partial derivative of order ${\alpha}$ of $f$ in the sense of distribution.
Bakhvalov in [1] and [2] proved that

$e_{n}^{\rm det}(C^{k,{\gamma}}_{d})\asymp n^{-\frac{k+{\gamma}}{d}}\ \ \ {\rm
and}\ \ \ e_{n}^{\rm det}(BW_{\infty}^{r}([0,1]^{d}))\asymp n^{-\frac{r}{d}}.$

Novak extended the second equivalence result in [24] and [25], and proved that
for $1\leq p<\infty$ and $r>d/p$,

$e_{n}^{\rm det}(BW_{p}^{r}([0,1]^{d}))\asymp n^{-\frac{r}{d}}.$

Meanwhile, Novak considered the randomized case errors of the above two
classes in [24] and [25], and proved that

$e_{n}^{\rm ran}(C^{k,{\alpha}}_{d})\asymp
n^{-\frac{k+{\alpha}}{d}-\frac{1}{2}},$

and for $1\leq p\leq\infty$ and $r>d/p$,

$e_{n}^{\rm ran}(BW_{p}^{r}([0,1]^{d}))\asymp
n^{-\frac{r}{d}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}},$

where $a_{+}=\max(a,0)$.

(2) Consider the anisotropic Sobolev class $BW_{p}^{{\bf r}}([0,1]^{d}),\
1\leq p\leq\infty,\ {\bf r}=(r_{1},\cdots,r_{d})\in\mathbb{N}^{d}$, defined by

$BW_{p}^{{\bf r}}([0,1]^{d})=\big{\\{}f\in
L_{p}([0,1]^{d})\,\big{|}\,\sum_{j=1}^{d}\big{\|}\frac{\partial^{r_{j}}f}{\partial
x_{j}^{r_{j}}}\big{\|}_{p}\leq 1\big{\\}}.$

Fang and Ye in [13] obtained for $g({\bf r})>d/{p}$,

$e_{n}^{\rm det}(BW_{p}^{{\bf r}}([0,1]^{d}))\asymp n^{-g({\bf r})},$

and for $g({\bf r})>1/{p}$,

$e_{n}^{\rm ran}(BW_{p}^{{\bf r}}([0,1]^{d}))\asymp n^{-g({\bf
r})-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}},$

where $g({\bf r})=\big{(}\sum_{j=1}^{d}r_{j}^{-1}\big{)}^{-1}$. For the
anisotropic Hölder-Nikolskii classes, Fang and Ye obtained the similar results
in [13].

(3) Consider the Sobolev class with bounded mixed derivative $BW_{p}^{r,\rm
mix}([0,1]^{d}),\ r\in\mathbb{N},\ 1\leq p\leq\infty$, defined by

$BW_{p}^{r,\rm mix}([0,1]^{d})=\big{\\{}f\in
L_{p}([0,1]^{d})\,\big{|}\,\sum_{|\alpha|_{\infty}\leq
r}\|D^{\alpha}f\|_{p}\leq 1\big{\\}},$

where $|\alpha|_{\infty}:=\max\limits_{1\leq i\leq d}{\alpha}_{i}$. The
authors in [5, 14, 31, 32] obtained for $r>1/{p}$ and $1<p<\infty$,

$e_{n}^{\rm det}(BW_{p}^{r,\rm mix}([0,1]^{d}))\asymp n^{-r}(\log
n)^{\frac{d-1}{2}}.$

It was shown in [19, 27, 35] that for $r>\max\\{1/p,1/2\\}$ and $1<p<\infty$,

$e_{n}^{\rm ran}(BW_{p}^{r,\rm mix}([0,1]^{d}))\asymp
n^{-r-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}.$

(4) For the Sobolev class $BW_{p}^{r}({S}^{d-1})$, $1\leq p\leq\infty$, $r>0$,
on the sphere ${S}^{d-1}$, it was proved in [4, 17, 37] that for $r>(d-1)/p$,

$e_{n}^{\rm det}(BW_{p}^{r}(\mathbb{S}^{d-1}))\asymp n^{-\frac{r}{d-1}}.$

Wang and Zhang in [39] obtained for $r>(d-1)/p$,

$e_{n}^{\rm ran}(BW_{p}^{r}(\mathbb{S}^{d-1}))\asymp
n^{-\frac{r}{d-1}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}.$

(5) For the generalized Besov class $BB_{p,{\theta}}^{\Omega}({S}^{d-1})$,
$1\leq p,{\theta}\leq\infty,$ with the smoothness index $\Omega$ satisfying
some conditions, Duan and Ye in [9] obtained

$e_{n}^{\rm
det}(BB_{p,{\theta}}^{\Omega}({S}^{d-1}))\asymp\Omega(n^{-\frac{1}{d-1}}),$

and

$e_{n}^{\rm
ran}(BB_{p,{\theta}}^{\Omega}({S}^{d-1}))\asymp\Omega(n^{-\frac{1}{d-1}})n^{-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}.$

We remark that if $\Omega(t)=t^{r}$, then
$BB_{p,{\theta}}^{\Omega}({S}^{d-1})$ recedes to the usual Besov class
$BB^{r}_{\theta}(L_{p}({S}^{d-1}))$.

(6) Dai and Wang in [6] investigated the weighted Besov class
$BB_{\tau}^{r}(L_{p,w}({S}^{d-1}))$, $r>0,\,0<\tau\leq\infty,\,1\leq
p\leq\infty,$ with an $A_{\infty}$ weight $w$ on ${S}^{d-1}$. They obtained
for $r>s_{w}/p$,

$e_{n}^{\rm det}(BB_{\tau}^{r}(L_{p,w}({S}^{d-1})))\asymp n^{-\frac{r}{d-1}},$

where $s_{w}$ is a critical index for the $A_{\infty}$ weight $w$. This
generalized the unweighted result of [18]. Meanwhile, they also obtained the
corresponding results for the weighted Besov classes on the unit ball and on
the standard simplex of the Euclidean space ${R}^{d}$.

The above results indicate that randomized algorithms effectively improve the
optimal rate of convergence in many cases. There is a vast literature of
integration problems in the deterministic and randomized case settings, see
for example, [6, 10, 11, 12, 13, 15, 25, 26, 34, 36, 43]. However, as far as
we know, there are few results about integration problem on the unite ball
${B}^{d}$ in the randomized case setting.

Let $\mathbb{B}^{d}=\big{\\{}x\in\mathbb{R}^{d}\,|\,|x|\leq 1\big{\\}}$ be the
unit ball of $\mathbb{R}^{d}$, where $x\cdot y$ is the usual inner product and
$|x|=(x\cdot x)^{1/2}$ is the usual Euclidean norm. We denote by
$L_{p,\mu}\equiv L_{p,\mu}({B}^{d}),\,0<p<\infty,$ the space of all measurable
functions with finite quasi-norm

$\|f\|_{p,\mu}:=\Big{(}\int_{\mathbb{B}^{d}}|f(x)|^{p}w_{\mu}(x)dx\Big{)}^{1/p},$

where $w_{\mu}(x)=b_{d}^{\mu}(1-|x|^{2})^{\mu-1/2},\ \mu\geq 0$ is the
classical Jacobi weight on ${B}^{d}$, normalized by
$\int_{{B}^{d}}w_{\mu}(x)dx=1$. When $p=\infty$ we consider the space of
continuous functions $C({B}^{d})$ with the uniform norm. Let $BW_{p,\mu}^{r}$
and $BB_{\tau}^{r}(L_{p,\mu})$, $1\leq p\leq\infty$, $r>0$,
$0<\tau\leq\infty$, denote the weighted Sobolev class and the weighted Besov
class on $\mathbb{B}^{d}$, respectively (see the precise definitions in
Section 2). We remark that if $r>(d+2\mu)/p$, then the spaces $W_{p,\mu}^{r}$
and $B_{\tau}^{r}(L_{p,\mu})$ are compactly embedded into the space of
continuous functions $C(\mathbb{B}^{d})$.

This paper is concerned with numerical integration on ${B}^{d}$

(1.2) ${\rm INT}_{d}(f)=\int_{\mathbb{B}^{d}}f(x)w_{\mu}(x)dx.$

For the weighted Besov class $BB_{\tau}^{r}(L_{p,\mu})$, $1\leq p\leq\infty$,
$0<\tau\leq\infty$, and $r>(d+2\mu)/p$, it follows from [6] that

(1.3) $e_{n}^{\rm det}(BB_{\tau}^{r}(L_{p,\mu}))\asymp n^{-\frac{r}{d}}.$

For the weighted Sobolev class $BW_{p,\mu}^{r}$, $1\leq p\leq\infty$,
$r>(d+2\mu)/p$, we obtain the similar result as follows.

######  Theorem 1.1.

Let $1\leq p\leq\infty$ and $r>(d+2\mu)/{p}$. Then we have

(1.4) $e_{n}^{\rm det}(BW_{p,\mu}^{r})\asymp n^{-\frac{r}{d}}.$

From (1.3) and (1.4), we know that the integration problems (1.2) for the
weighted Besov class $BB_{\tau}^{r}(L_{p,\mu})$ and the weighted Sobolev class
$BW_{p,\mu}^{r}$ is “intractable” in the deterministic setting if $d$ is much
larger than $r$. So it is natural to ask whether randomness improves the order
of convergence. In this paper we investigate randomized quadrature for
$BW_{p,\mu}^{r}$ and $BB_{\tau}^{r}(L_{p,\mu})$. We obtain their sharp
asymptotic orders of quadrature errors in the randomized case setting, and
find that randomized algorithms provide a faster rate than that of
deterministic ones for $p>1$. Our main results can formulated as follows.

######  Theorem 1.2.

Let $1\leq p\leq\infty$, $0<\tau\leq\infty$, and $r>(d+2\mu)/{p}$. Then we
have

(1.5) $e_{n}^{\rm ran}(BX_{p}^{r})\asymp
n^{-\frac{r}{d}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}},$

where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or $B_{\tau}^{r}(L_{p,\mu})$.

######  Remark 1.3.

We compare the results in the deterministic and randomized case settings. For
$p=1$, the order of convergence is the same, which means that randomness does
not help for $p=1$. Randomness does help for $1<p\leq\infty.$ Indeed,
randomness improve the order of convergence by a factor $n^{1-1/p}$ for
$1<p<2$ and $n^{1/2}$ for $2\leq p\leq\infty$.

The organization of the paper is the following. Section 2 presents some facts
about harmonic analysis on the ball. In Section 3 we use the filtered
hyperinterpolation operators to approximate functions in $W_{p,\mu}^{r}$ or
$B_{\tau}^{r}(L_{p,\mu})$, and show that the filtered hyperinterpolation
operators are asymptotically optimal algorithms in the sense of optimal
recovery in some cases. We also give the proof of Theorem 1.1. Section 4 and
Section 5 are devoted to proving the upper and lower estimates of the
quantities $e_{n}^{\rm ran}(BX_{p}^{r})$ as in Theorem 1.2, respectively.

##  2\. Preliminaries

This section is devoted to give some basic knowledge about harmonic analysis
on the unit ball ${B}^{d}$.

For the classical Jacobi weight

$w_{\mu}(x)=b_{d}^{\mu}(1-|x|^{2})^{\mu-1/2},\ \mu\geq 0,\
b_{d}^{\mu}=\Big{(}\int_{{B}^{d}}(1-|x|^{2})^{\mu-1/2}dx\Big{)}^{-1},\ $

on $\mathbb{B}^{d}$, denote by $L_{p,\mu}\equiv
L_{p,\mu}({B}^{d})\,(0<p<\infty)$ the space of all Lebesgue measurable
functions $f$ on $\mathbb{B}^{d}$ with the finite quasi-norm

$\|f\|_{p,\mu}:=\Big{(}\int_{\mathbb{B}^{d}}|f(x)|^{p}w_{\mu}(x)dx\Big{)}^{1/p}.$

And when $p=\infty$ we consider the space of continuous functions $C({B}^{d})$
with the uniform norm. In particular, $L_{2,\mu}$ is a Hilbert space with
inner product

$\langle f,g\rangle_{\mu}:=\int_{{B}^{d}}f(x)g(x)w_{\mu}(x)dx,\ {\rm for}\
f,g\in L_{2,\mu}.$

Let $\Pi_{n}^{d}$ be the space of all polynomials in $d$ variables of total
degree at most $n$. We denote by $\mathcal{V}_{n}^{d}(w_{\mu})$ the space of
all polynomials of degree $n$ which are orthogonal to lower degree polynomials
in $L_{2,\mu}.$ It is well known (see [7, p.38 or p.229]) that the spaces
$\mathcal{V}_{n}^{d}(w_{\mu})$ are just the eigenspaces corresponding to the
eigenvalues $-n(n+2\mu+d-1)$ of the second-order differential operator

$D_{\mu}:=\triangle-(x\cdot\nabla)^{2}-(2\mu+d-1)x\cdot\nabla,$

where $\triangle$ and $\nabla$ are the Laplace operator and gradient operator,
respectively. More precisely,

$D_{\mu}P=-n(n+2\mu+d-1)P,\ \ {\rm for\ all}\
P\in\mathcal{V}_{n}^{d}(w_{\mu}).$

It is easy to see that the spaces $\mathcal{V}_{n}^{d}(w_{\mu})$ are mutually
orthogonal in $L_{2,\mu}$. Let
$\\{\phi_{nk}\equiv\phi_{nk}^{d}:\,k=1,2,\dots,a_{n}^{d}\\}$ be a fixed
orthonormal basis for $\mathcal{V}_{n}^{d}(w_{\mu})$, where $a_{n}^{d}:={\rm
dim}\,\mathcal{V}_{n}^{d}(w_{\mu})$. Then

$\\{\phi_{nk}:\,k=1,2,\dots,a_{n}^{d},\,n=0,1,2,\dots\\}$

is an orthonormal basis for $L_{2,\mu}$. The orthogonal projector ${\rm
Proj}_{n}:\,L_{2,\mu}\rightarrow\mathcal{V}_{n}^{d}(w_{\mu})$ can be written
as

$\displaystyle({\rm Proj}_{n}f)(x)$
$\displaystyle=\sum\limits_{k=1}^{a_{n}^{d}}\langle
f,\phi_{nk}\rangle\phi_{nk}(x)=\langle f,P_{n}(w_{\mu};x,\cdot)\rangle_{\mu},$

where
$P_{n}(w_{\mu};x,y)=\sum\limits_{k=1}^{a_{n}^{d}}\phi_{nk}(x)\phi_{nk}(y)$ is
the reproducing kernel of $\mathcal{V}_{n}^{d}(w_{\mu})$. See [41] for more
details about $P_{n}(w_{\mu};x,y)$.

For $r>0$, we define the fractional power $(-D_{\mu})^{r/2}$ of the operator
$-D_{\mu}$ on $f$ by

$(-D_{\mu})^{r/2}f:=\sum\limits_{k=0}^{\infty}(k(k+2\mu+d-1))^{r/2}{\rm
Proj}_{k}f,$

in the sense of distribution. By [42], we have for any $P\in\Pi_{n}^{d}$,

(2.1) $\|(-D_{\mu})^{r/2}P\|_{p,\mu}\lesssim n^{r}\|P\|_{p,\mu}.$

Given $r>0$ and $1\leq p\leq\infty$, we define the weighted Sobolev space by

$W_{p,\mu}^{r}\equiv W_{p,\mu}^{r}({B}^{d}):=\big{\\{}f\in L_{p,\mu}\ \big{|}\
\|f\|_{W_{p,\mu}^{r}}:=\|f\|_{p,\mu}+\|(-D_{\mu})^{r/2}f\|_{p,\mu}<\infty\big{\\}},$

while the weighted Sobolev class $BW_{p,\mu}^{r}$ is defined to be the unit
ball of the weighted Sobolev space $W_{p,\mu}^{r}$. We remark that if
$r>(d+2\mu)/p$, then $W_{p,\mu}^{r}$ is compactly embedded into $C({B}^{d})$.

Let $\eta\in C^{\infty}[0,+\infty)$ (a “$C^{\infty}$-filter”) satisfy

$\chi_{\left[0,1\right]}\leq\eta\leq\chi_{\left[0,2\right]}.$

Here, $\chi_{A}$ denotes the characteristic function of $A$ for $A\subset{R}$.
For $L\in{N}$, we define the filtered polynomial operator by

(2.2) $V_{L}(f)(x)\equiv
V_{L,\eta}(f)(x):=\sum_{k=0}^{\infty}\eta(\frac{k}{L}){\rm
Proj}_{k}(f)(x)=\langle f,K_{L,\eta}(x,\cdot)\rangle_{\mu},$

where $f\in L_{1,\mu}$, and

(2.3)
$K_{L,\eta}(x,y)=\sum_{k=0}^{\infty}\eta(\frac{k}{L})P_{k}(w_{\mu};x,y),\
x,y\in{B}^{d}.$

Then the following properties hold (see, for example, [28])):

(a) $V_{L}(f)\in\Pi^{d}_{2L-1}$ for any $f\in L_{1,\mu}$;

(b) $P=V_{L}(P)$ for any $P\in\Pi_{L}^{d}$;

(c)
$\|V_{L}\|:=\|V_{L}\|_{(\infty,\infty)}=\|V_{L}\|_{(1,1)}=\sup\limits_{x\in\mathbb{B}^{d}}\|K_{L,\eta}(x,\cdot)\|_{1,\mu}\lesssim
1$;

(d) $\|V_{L}\|_{(p,p)}\leq\|V_{L}\|\lesssim 1$ for $1\leq p\leq\infty$;

(e) $\|f-V_{L}(f)\|_{p,\mu}\leq(1+\|V_{L}\|_{(p,p)})E_{L}(f)_{p,\mu}\lesssim
E_{L}(f)_{p,\mu}$ for $1\leq p\leq\infty$,

where

$\|A\|_{(p,p)}:=\sup\limits_{\|f\|_{p,\mu}\leq 1}\|Af\|_{p,\mu}$

is the operator norm of a linear operator $A$ on $L_{p,\mu}$, and
$E_{L}(f)_{p,\mu}$ is the best approximation of $f\in L_{p,\mu}$ from
$\Pi_{L}^{d}$ defined by

$E_{L}(f)_{p,\mu}:=\inf\limits_{P\in\Pi_{L}^{d}}\|f-P\|_{p,\mu}.$

We note that property (c) is essential.

######  Remark 2.1.

Let $\eta$ be a filter, i.e., $\eta$ is a continuous function satisfying
$\chi_{\left[0,1\right]}\leq\eta\leq\chi_{\left[0,2\right]}.$ We may weaken
the smoothness condition on $\eta$ such that the operator norms
$\|V_{L,\eta}\|$ are uniformly bounded. Wang and Sloan investigated the
corresponding problem on the sphere, and gave the compact condition on $\eta$
for which the operator norms of the filtered polynomial operators
$V^{{S}}_{L,\eta}$ on the sphere are uniformly bounded. Following the way in
[38], Li obtained in [22] that the operator norms $\|V_{L,\eta}\|$ are
uniformly bounded whenever $\eta\in W^{\lfloor\frac{d+2\mu+1}{2}\rfloor}BV$,
where $W^{r}BV[a,b]$ denotes the set of all continuous functions $\eta$ on
$[a,b]$ for which $\eta^{(r-1)}$ is absolutely continuous and $\eta^{(r)}_{+}$
and $\eta^{(r)}_{-}$ exist and are of bounded variation on $[a,b]$ for
$r\in{N}$. Hence, if $\eta\in W^{\lfloor\frac{d+2\mu+1}{2}\rfloor}BV$, then
properties (a)-(e) hold. Note that

$C^{r+1}[a,b]\subset W^{r}BV[a,b]\subset C[a,b],\ {\rm for\ any}\ r\in{N}.$

The condition $\eta\in W^{\lfloor\frac{d+2\mu+1}{2}\rfloor}BV$ is compact,
since there exists an $\eta\in W^{\lfloor\frac{d+2\mu-1}{2}\rfloor}BV$ such
that $\|V_{L,\eta}\|$ are not uniformly bounded.

Now we define weighted Besov spaces on the ball. Given $1\leq p\leq\infty$,
$r>0$, and $0<\tau\leq\infty$, we define the weighted Besov space
$B_{\tau}^{r}(L_{p,\mu})$ to be the space of all real functions $f$ with
quasi-norm

$\|f\|_{B_{\tau}^{r}(L_{p,\mu})}:=\Bigg{\\{}\begin{aligned}
&\|f\|_{p,\mu}+\Big{(}\sum\limits_{j=0}^{\infty}2^{jr\tau}E_{2^{j}}(f)_{p,\mu}^{\tau}\Big{)}^{1/\tau},\
\ &0<\tau<\infty,\\\ &\|f\|_{p,\mu}+\sup\limits_{j\geq
0}2^{jr}E_{2^{j}}(f)_{p,\mu},\ \ \ &\tau=\infty,\end{aligned}$

while the weighted Besov class $BB_{\tau}^{r}(L_{p,\mu})$ is defined to be the
unit ball of the weighted Besov space $B_{\tau}^{r}(L_{p,\mu})$.

There are other definitions of the weighted Besov spaces which are equivalent
(see [20, Proposition 5.7]). We remark that if $1\leq p,q\leq\infty,\
r>(d+2\mu)/p$, then $B_{\tau}^{r}(L_{p,\mu})$ is compactly embedded into
$C({B}^{d})$, and for $1\leq p\leq\infty,\ r>0$,
$0<\tau_{1}\leq\tau_{2}\leq\infty$,

$B_{\tau_{1}}^{r}(L_{p,\mu})\subset B_{\tau_{2}}^{r}(L_{p,\mu})\subset
B_{\infty}^{r}(L_{p,\mu}).$

It follows from the Jackson inequality (see [42]) that for $f\in
W_{p,\mu}^{r},\ 1\leq p\leq\infty$, $r>0$,

(2.4) $E_{n}(f)_{p,\mu}\lesssim n^{-r}\|f\|_{W_{p,\mu}^{r}}.$

This means that

$W_{p,\mu}^{r}\subset B_{\infty}^{r}(L_{p,\mu}).$

It can be seen that for $f\in B_{\tau}^{r}(L_{p,\mu})$, $0<\tau\leq\infty$,

(2.5) $E_{n}(f)_{p,\mu}\leq 2^{r}n^{-r}\|f\|_{B_{\tau}^{r}(L_{p,\mu})}.$

We introduce a metric $\rho$ on $\mathbb{B}^{d}$:

$\rho(x,y):=\arccos\Big{(}(x,y)+\sqrt{1-|x|^{2}}\sqrt{1-|y|^{2}}\Big{)}.$

For $r>0,\ x\in\mathbb{B}^{d}$ and a positive integer $n$, we set

${\bf B}_{\rho}(x,r):=\\{y\in\mathbb{B}^{d}\ |\ \rho(x,y)\leq r\\}.$

For $\varepsilon\in(0,1)$, we say that a finite subset
$\Lambda\subset\mathbb{B}^{d}$ is maximal $\varepsilon$-separated if

$\mathbb{B}^{d}\subset\bigcup\limits_{{\omega}\in\Lambda}{\bf
B}_{\rho}({\omega},\varepsilon)\ {\rm\ and}\
\min\limits_{{\omega}\neq{\omega}^{\prime}}\rho({\omega},{\omega}^{\prime})\geq\varepsilon.$

Note that such a maximal $\varepsilon$-separated set $\Lambda$ exists and
$\\#\Lambda\asymp\varepsilon^{-d}$, where $\\#A$ denotes the number of
elements of a set $A$ (see [28, Lemma 5.2]).

Finally, we give the Nikolskii inequalities on ${B}^{d}$.

######  Lemma 2.2.

([20, Proposition 2.4]) Let $1\leq p,q\leq\infty$ and $\mu\geq 0$. Then for
any $P\in\Pi_{n}^{d}$ we have,

(2.6) $\|P\|_{q,\mu}\lesssim n^{(d+2\mu)(1/p-1/q)_{+}}\|P\|_{p,\mu}.$

##  3\. Filtered hyperinterpolation on the ball

Let $\eta$ be a filter such that properties (a)-(e) hold. We want to
approximate the inner product integral (2.2) of $V_{L,\eta}(f)(x)$ by a
positive quadrature rule of polynomial degree $3L$. Following [30], we shall
call the resulting operator “filtered hyperinterpolation”.

For this purpose, we need positive quadrature rules on ${B}^{d}$. For
$L\in{N}$, we assume that
$Q_{L}(f):=\sum_{{\omega}\in\Lambda_{L}}{\lambda}_{\omega}f({\omega})$ is a
positive quadrature rule on ${B}^{d}$ which is exact for $f\in\Pi_{3L}^{d}$,
i.e., $\Lambda_{L}$ is a finite subset of $\mathbb{B}^{d}$ with
$\\#\Lambda_{L}\asymp L^{d}$, weights ${\lambda}_{\omega}>0,\
{\omega}\in\Lambda_{L}$, satisfy, for all $P\in\Pi_{3L}^{d}$,

$\int_{\mathbb{B}^{d}}P(x)w_{\mu}(x)dx=Q_{L}(P)=\sum_{\omega\in\Lambda_{L}}\lambda_{\omega}P(\omega).$

Such positive quadrature rules exist. Indeed, for $L\in{N}$, it follows from
[7, Theorem 11.6.5] that for a given maximal $\delta/L$-separated subset
$\Lambda_{L}$ of ${B}^{d}$ with $\delta\in(0,\delta_{0})$ for some
$\delta_{0}>0$, there exists a positive quadrature formula

$\int_{\mathbb{B}^{d}}f(x)w_{\mu}(x)dx\approx
Q_{L}(f):=\sum_{\omega\in\Lambda_{L}}\lambda_{\omega}f(\omega),\
\lambda_{\omega}>0,$

with $\lambda_{\omega}\asymp\int_{{\bf B}_{\rho}(y,\delta/L)}w_{\mu}(x)dx$ and
$\\#\Lambda_{L}\asymp L^{d}$, which is exact for $\Pi^{d}_{3L}$.

For the above positive quadrature formula $Q_{L}$, we can define the discreted
inner product $\langle\cdot,\cdot\rangle_{Q_{L}}$ on $C({B}^{d})$ by

$\langle
f,g\rangle_{Q_{L}}:=Q_{L}(fg)=\sum_{\omega\in\Lambda_{L}}\lambda_{\omega}f(\omega)g({\omega}).$

The filtered hyperinterpolation operator is defined by

(3.1) $G_{L}(f)(x):=\langle
f,K_{L,\eta}(x,\cdot)\rangle_{Q_{L}}=\sum_{\omega\in\Lambda_{L}}\lambda_{\omega}f({\omega})K_{L,\eta}(x,{\omega}).$

From [40] we know that

(3.2)
$\|G_{L}\|=\sup_{x\in\mathbb{B}^{d}}\sum_{\omega\in\Lambda_{L}}\lambda_{\omega}|K_{L,\eta}(x,{\omega})|\lesssim
1.$

The following theorem plays an important role in the proof of upper estimates.

######  Theorem 3.1.

Let $1\leq p,q\leq\infty$, $r>(d+2\mu)/p$, $0<\tau\leq\infty$, and $G_{L}$ be
given as in (3.1). Then for all $f\in X_{p}^{r}$, we have

(3.3) $\|f-G_{L}(f)\|_{q,\mu}\lesssim
L^{-r+(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}\|f\|_{X_{p}^{r}},$

where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or $B_{\tau}^{r}(L_{p,\mu})$.

######  Remark 3.2.

When $1\leq p=q\leq\infty$ and $X_{p}^{r}=W_{p,\mu}^{r}$, (3.3) was obtained
by Li in [22].

In order to prove Theorem 3.1, we need the following two lemmas.

######  Lemma 3.3.

([40, Theorem 3.1] and [21, Lemma 2.2]) Suppose that $n\in{N}$, $\Omega_{n}$
is a finite subset of $\mathbb{B}^{d}$, and
$\\{\mu_{\omega}:\,\omega\in\Omega_{n}\\}$ is a set of positive numbers. If
there exists a $p_{0}\in(0,\infty)$ such that for any $f\in\Pi_{n}^{d}$,

(3.4)
$\sum_{\omega\in\Omega_{n}}\mu_{\omega}|f(\omega)|^{p_{0}}\lesssim\int_{\mathbb{B}^{d}}|f(x)|^{p_{0}}w_{\mu}(x)dx,$

then the following regularity condition

(3.5) $\sum_{\omega\in\Omega_{n}\cap{\bf
B}_{\rho}(y,\frac{1}{n})}\mu_{\omega}\lesssim\int_{{\bf
B}_{\rho}(y,\frac{1}{n})}w_{\mu}(x)dx,\ {\rm for\ any}\ y\in{B}^{d},$

holds.

Conversely, if the regularity condition (3.5) holds, then for any $1\leq
p<\infty$, $m\in{N}$, $m\geq n$, $f\in\Pi_{m}^{d}$, we have

(3.6)
$\sum_{\omega\in\Omega_{n}}\mu_{\omega}\left|f(\omega)\right|^{p}\lesssim(\frac{m}{n})^{d+2\mu}\int_{\mathbb{B}^{d}}\left|f(x)\right|^{p}w_{\mu}(x)dx.$

######  Lemma 3.4.

Let $1\leq p\leq\infty$, and $L\in{N}$. Then for any $N\geq L$ and
$P\in\Pi_{N}^{d}$, we have

(3.7)
$\|G_{L}(P)\|_{p,\mu}\lesssim(\frac{N}{L})^{\frac{d+2\mu}{p}}\|P\|_{p,\mu}.$

###### Proof.

Our proof will be divided into three cases.

_Case 1:_ $p=\infty$.

In this case, by (3.2) we have for $N\geq L$ and $P\in\Pi_{N}^{d}$,

$\displaystyle\|G_{L}(P)\|_{\infty}\leq\|G_{L}\|\|P\|_{\infty}\lesssim\|P\|_{\infty}.$

_Case 2:_ $p=1$.

In this case, since $Q_{L}$ is a positive quadrature rule which is exact for
$\Pi_{3L}^{d}$, then (3.4) is true for
$\\{\lambda_{\omega}\\}_{\omega\in\Lambda_{L}}$ with $p_{0}=2$. This leads
that the regular condition (3.5) holds. By property (c) and Lemma 3.3 we
obtain for $N\geq L$ and $P\in\Pi_{N}^{d}$,

$\displaystyle\|G_{L}(P)\|_{1,\mu}$
$\displaystyle=\|\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}P({\omega})K_{L,\eta}(\cdot,{\omega})\|_{1,\mu}$
$\displaystyle\leq\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}|P({\omega})|\|K_{L,\eta}(\cdot,{\omega})\|_{1,\mu}$
$\displaystyle\lesssim\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}|P({\omega})|\lesssim(\frac{N}{L})^{{d+2\mu}}\|P\|_{1,\mu}.$

_Case 3:_ $1<p<\infty$.

In this case, for $N\geq L$ and $P\in\Pi_{N}^{d}$, by the Hölder inequality,
(3.2), property (c), and Lemma 3.3, we obtain

$\displaystyle\|G_{L}(P)\|_{p,\mu}^{p}$
$\displaystyle=\int_{\mathbb{B}^{d}}\Big{|}\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}P({\omega})K_{L,\eta}(x,{\omega})\Big{|}^{p}w_{\mu}(x)dx$
$\displaystyle\leq\int_{\mathbb{B}^{d}}\Big{(}\sum\limits_{\omega\in\Lambda_{L}}{\lambda}_{{\omega}}|P(\omega)||K_{L,\eta}(x,{\omega})|\Big{)}^{p}w_{\mu}(x)dx$
$\displaystyle\leq\int_{\mathbb{B}^{d}}\Big{(}\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}|P({\omega})|^{p}|K_{L,\eta}(x,{\omega})|\Big{)}\Big{(}\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}|K_{L,\eta}(x,{\omega})|\Big{)}^{p-1}w_{\mu}(x)dx$
$\displaystyle\leq\Big{(}\sum\limits_{\omega\in\Lambda_{L}}{\lambda}_{{\omega}}|P({\omega})|^{p}\|K_{L,\eta}(\cdot,{\omega})\|_{1,\mu}\Big{)}\Big{(}\sup_{x\in\mathbb{B}^{d}}\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}|K_{L,\eta}(x,{\omega})|\Big{)}^{{p-1}}$
$\displaystyle\lesssim\sum\limits_{\omega\in\Lambda_{L}}\lambda_{\omega}|P({\omega})|^{p}\lesssim(\frac{N}{L})^{d+2\mu}\|P\|_{p,\mu}^{p},$

which proves (3.7).

Lemma 3.4 is proved.∎

Now we turn to prove Theorem 3.1.

Proof of Theorem 3.1.

Since $X_{p}^{r}$ is continuously embedded into $B_{\infty}^{r}(L_{p,\mu})$,
it suffices to show Theorem 3.1 for $B_{\infty}^{r}(L_{p,\mu})$.

Suppose that $m$ is an integer satisfying $2^{m}\leq L<2^{m+1}$. Let $1\leq
p,q\leq\infty,\ r>(d+2\mu)/p$, and $f\in B_{\infty}^{r}(L_{p,\mu})$. Define
$g_{2^{k}}\in\Pi_{2^{k}}^{d}$ by

$E_{2^{k}}(f)_{p,\mu}=\|f-g_{2^{k}}\|_{p,\mu},$

and let $f_{k}=g_{2^{k}}-g_{2^{k-1}}$ for $k\geq 0$, where we set
$g_{2^{-1}}=0$. Note that since $\Pi_{2^{k}}^{d}$ are the finite dimensional
linear spaces, the best approximant polynomials $g_{2^{k}}$ always exist (see,
for instance, [23, p. 17, Theorem 1]). It can be seen that
$f_{k}\in\Pi_{2^{k}}^{d}$, and the series $\sum\limits_{k=j+1}^{\infty}f_{k}$
converges to $f-g_{2^{j}}$ in the uniform norm for each $j\geq-1$. We have

$\displaystyle\|f-G_{L}(f)\|_{q,\mu}$
$\displaystyle=\|\sum_{k=m+1}^{\infty}(f_{k}-G_{L}(f_{k}))\|_{q,\mu}$
$\displaystyle\leq\sum_{k=m+1}^{\infty}\|f_{k}-G_{L}(f_{k})\|_{q,\mu}$ (3.8)
$\displaystyle\leq\sum_{k=m+1}^{\infty}\|f_{k}\|_{q,\mu}+\sum_{k=m+1}^{\infty}\|G_{L}(f_{k})\|_{q,\mu}.$

It follows from the Nikolskii inequality (2.6) and (2.5) we have

$\displaystyle\|f_{k}\|_{q,\mu}$ $\displaystyle\lesssim
2^{k(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}\|f_{k}\|_{p,\mu}$
$\displaystyle\leq
2^{k(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}(\|f-g_{2^{k}}\|_{p,\mu}+\|f-g_{2^{k-1}}\|_{p,\mu})$
$\displaystyle\lesssim
2^{k(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}E_{2^{k-1}}(f)_{p,\mu}$ (3.9)
$\displaystyle\lesssim
2^{-k(r-(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+})}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}.$

This means that

$\displaystyle\sum_{k=m+1}^{\infty}\|f_{k}\|_{q,\mu}$
$\displaystyle\lesssim\sum_{k=m+1}^{\infty}2^{-k(r-(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+})}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}$
$\displaystyle\asymp
2^{-m(r-(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+})}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}$
(3.10) $\displaystyle\asymp
L^{-r+(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}.$

Applying (3) and Lemma 3.4, we get for $k\geq m+1$,

$\displaystyle\|G_{L}(f_{k})\|_{q,\mu}$ $\displaystyle\lesssim
L^{(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}\|G_{L}(f_{k})\|_{p,\mu}$
$\displaystyle\lesssim
L^{(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}(\frac{2^{k}}{L})^{\frac{d+2\mu}{p}}\|f_{k}\|_{p,\mu}$
$\displaystyle\lesssim
L^{(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}(\frac{2^{k}}{L})^{\frac{d+2\mu}{p}}2^{-kr}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}.$

It follows that

$\displaystyle\sum_{k=m+1}^{\infty}\|G_{L}(f_{k})\|_{q,\mu}$
$\displaystyle\lesssim\sum_{k=m+1}^{\infty}L^{(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}(\frac{2^{k}}{L})^{\frac{d+2\mu}{p}}2^{-kr}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}$
$\displaystyle\lesssim
L^{(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}-\frac{d+2\mu}{p}}\sum_{k=m+1}^{\infty}2^{-k(r-\frac{d+2\mu}{p})}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}$
(3.11) $\displaystyle\asymp
L^{-r+(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}.$

Hence, for $f\in B_{\infty}^{r}(L_{p,\mu})$, by (3), (3), and (3) we have

$\displaystyle\|f-G_{L}(f)\|_{q,\mu}\lesssim
L^{-r+(d+2\mu)(\frac{1}{p}-\frac{1}{q})_{+}}\|f\|_{B_{\infty}^{r}(L_{p,\mu})}.$

This completes the proof of Theorem 3.1. $\hfill\Box$

Next we show that the filtered hyperinterpolation operators $G_{L}$ are order
optimal in sense of the optimal recovery in some cases. Let $F_{d}$ be a class
of continuous functions on $D_{d}$, and $(X,\|\cdot\|_{X})$ be a normed linear
space of functions on $D_{d}$, where $D_{d}$ is a subset of ${R}^{d}$. For
$n\in{N}$, the sampling numbers (or the optimal recovery) of $F_{d}$ in $X$
are defined by

$g_{n}(F_{d},X)\ :=\inf_{\begin{subarray}{c}\xi_{1},\dots,\xi_{n}\in D_{d}\\\
\varphi:\ {R}^{n}\rightarrow X\end{subarray}}\sup_{f\in
F_{d}}\|f-\varphi(f(\xi_{1}),\dots,f(\xi_{n}))\|_{X},$

where the infimum is taken over all $n$ points $\xi_{1},\dots,\xi_{n}$ in
$D_{d}$ and all mappings $\varphi$ from ${R}^{n}$ to $X$. If in the above
definition, the infimum is taken over all $n$ points $\xi_{1},\dots,\xi_{n}$
in $D_{d}$ and all linear mappings $\varphi$ from ${R}^{n}$ to $X$, we obtain
the definition of the linear sampling numbers $g_{n}^{\rm lin}(F_{d},X)$.

It is well known (see [33]) that for a balanced convex set $F_{d}$,

(3.12) $g_{n}^{\rm lin}(F_{d},X)\geq
g_{n}(F_{d},X)\geq\inf_{\begin{subarray}{c}\xi_{1},\dots,\xi_{n}\in
D_{d}\end{subarray}}\sup_{\begin{subarray}{c}f\in F_{d}\\\
f(\xi_{1})=\dots=f(\xi_{n})=0\end{subarray}}\|f\|_{X}.$

######  Theorem 3.5.

Let $1\leq q\leq p\leq\infty$, $0<\tau\leq\infty$, and $r>(d+2\mu)/p$. Then we
have

(3.13) $g_{n}^{\rm lin}(BX_{p}^{r},L_{q,\mu})\asymp
g_{n}(BX_{p}^{r},L_{q,\mu})\asymp n^{-r/d},$

where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or $B_{\tau}^{r}(L_{p,\mu})$.

In order to prove Theorem 3.5 we need the following lemma.

######  Lemma 3.6.

([6, Proposition 4.8]) Let $X$ be a linear subspace of $\Pi_{N}^{d}$ with
${\rm dim}\,X\geq\varepsilon\,{\rm dim}\,\Pi_{N}^{d}$ for some
$\varepsilon\in(0,1)$. Then there exists a function $f\in X$ such that
$\|f\|_{p,\mu}\asymp 1$ for all $0<p\leq\infty$.

Proof of Theorem 3.5.

Without loss of generality we assume that $n$ is sufficiently large. We choose
$L\in{N}$ such that

$\\#\Lambda_{L}\leq n\ \ {\rm and}\ \ \\#\Lambda_{L}\asymp n.$

It follows from the definition of $G_{L}$ and $g_{n}^{\rm
lin}(BX_{p}^{r},L_{q,\mu})$ that

$g_{n}^{\rm lin}(BX_{p}^{r},L_{q,\mu})\leq\sup_{f\in
BX_{p}^{r}}\|f-G_{L}(f)\|_{q,\mu}.$

By Theorem 3.1 and the above inequlity we have

(3.14) $\displaystyle g_{n}(BX_{p}^{r},L_{q,\mu})\leq g_{n}^{\rm
lin}(BX_{p}^{r},L_{q,\mu})\lesssim L^{-r}\asymp n^{-r/d}.$

Now we show the lower bound. Let $\xi_{1},\dots,\xi_{n}$ be any $n$ distinct
points on ${B}^{d}$. Take a positive integer $N$ such that $2n\leq{\rm
dim}\,\Pi_{N}^{d}\leq Cn$, and denote

$X_{0}:=\big{\\{}g\in\Pi_{N}^{d}\ \big{|}\ g(\xi_{j})=0\ {\rm for\ all}\
j=1,\dots,n\big{\\}}.$

Thus, $X_{0}$ is a linear subspace of $\Pi_{N}^{d}$ with

${\rm dim}\,X_{0}\geq{\rm dim}\,\Pi_{N}^{d}-n\geq\frac{1}{2}{\rm
dim}\,\Pi_{N}^{d}.$

It follows from Lemma 3.6 that there exists a function $g_{0}\in X_{0}$ such
that

$\|g_{0}\|_{p_{0},\mu}\asymp 1,\ {\rm}\ {\rm for\ all}\ 0<p_{0}\leq\infty.$

Let $f_{0}(x)=N^{-r}(g_{0}(x))^{2}$ and $m\in{N}$ such that $2^{m-1}\leq
N<2^{m}$. Then by the fact that
$E_{2^{j}}(f_{0})_{p,\mu}\leq\|f_{0}\|_{p,\mu}$ we have

$\displaystyle\|f_{0}\|_{B_{\tau}^{r}(L_{p,\mu})}$
$\displaystyle=\|f_{0}\|_{p,\mu}+\Big{(}\sum\limits_{j=0}^{m+1}2^{jr\tau}E_{2^{j}}(f_{0})_{p,\mu}^{\tau}\Big{)}^{1/\tau}$
$\displaystyle\lesssim\Big{(}\sum\limits_{j=0}^{m+1}2^{jr\tau}\Big{)}^{1/\tau}\|f_{0}\|_{p,\mu}\lesssim
2^{mr}N^{-r}\|g_{0}\|_{2p,\mu}^{2}\lesssim 1.$

By the fact that $f_{0}\in\Pi_{2N}^{d}$ and (2.1) we have

(3.15) $\displaystyle\|f_{0}\|_{W_{p,\mu}^{r}}$
$\displaystyle=\|f_{0}\|_{p,\mu}+\|(-D_{\mu})^{r/2}f_{0}\|_{p,\mu}\lesssim
N^{r}\|f_{0}\|_{p,\mu}=\|g_{0}\|_{2p,\mu}^{2}\lesssim 1.$

Hence, there exists a positive constant $C$ such that $f_{1}=Cf_{0}\in
BX_{p}^{r}$, and $f_{1}(\xi_{1})=\dots=f_{1}(\xi_{n})=0$. It follows from
(3.12) that

$g_{n}(BX_{p}^{r},L_{q,\mu})\geq\inf_{\begin{subarray}{c}\xi_{1},\dots,\xi_{n}\in
D_{d}\end{subarray}}\|f_{1}\|_{q,\mu}\gtrsim
N^{-r}\inf_{\begin{subarray}{c}\xi_{1},\dots,\xi_{n}\in
D_{d}\end{subarray}}\|g_{0}\|_{2q,\mu}^{2}\asymp N^{-r}\asymp n^{-r/d},$

which combining with (3.14), gives (3.13).

The proof of Theorem 3.5 is finished. $\hfill\Box$

######  Remark 3.7.

It follows from the proof of Theorem 3.5 that for $1\leq q\leq p\leq\infty$,
$0<\tau\leq\infty$, and $r>(d+2\mu)/p$,

$g_{n}(BX_{p}^{r},L_{q,\mu})\asymp n^{-r/d}\asymp\sup_{f\in
BX_{p}^{r}}\|f-G_{L}(f)\|_{q,\mu},$

where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or $B_{\tau}^{r}(L_{p,\mu})$. This
implies that the filtered hyperinterpolation operators are asymptotically
optimal algorithms in the sense of optimal recovery for $1\leq q\leq
p\leq\infty$.

Finally we prove Theorem 1.1.

Proof of Theorem 1.1.

Since $\|f\|_{B_{\infty}^{r}(L_{p,\mu})}\lesssim\|f\|_{W_{p,\mu}^{r}}$ for
$f\in W_{p,\mu}^{r}$, by (1.3) we obtain for $1\leq p\leq\infty$ and
$r>(d+2\mu)/p$,

$e_{n}^{\rm det}(BW^{r}_{p,\mu})\lesssim e_{n}^{\rm
det}(BB_{\infty}^{r}(L_{p,\mu}))\lesssim n^{-r/d}.$

Now we prove the lower bound. Let $\xi_{1},\dots,\xi_{n}$ be any $n$ distinct
points on ${B}^{d}$. Take a positive integer $N$ such that $2n\leq{\rm
dim}\,\Pi_{N}^{d}\leq Cn$. According to the proof of Theorem 3.5, there exists
a function $f_{1}(x)$ such that

$f_{1}\in BW_{p,\mu}^{r},\ \ f_{1}(\xi_{1})=\dots=f_{1}(\xi_{n})=0,\ \
f_{1}(x)\geq 0,$

and

$\|f_{1}\|_{1,\mu}=\int_{{B}^{d}}f_{1}(x)w_{\mu}(x)dx\asymp N^{-r}.$

It follows from [33] that for $BW_{p,\mu}^{r}$ which is a balanced convex set,

$\displaystyle e_{n}^{\rm det}(BW_{p,\mu}^{r})$
$\displaystyle\geq\inf_{\begin{subarray}{c}\xi_{1},\dots,\xi_{n}\in{B}^{d}\end{subarray}}\sup_{\begin{subarray}{c}f\in
F_{d}\\\
f(\xi_{1})=\dots=f(\xi_{n})=0\end{subarray}}\Big{|}\int_{{B}^{d}}f(x)w_{\mu}(x)dx\Big{|}$
$\displaystyle\geq\inf_{\begin{subarray}{c}\xi_{1},\dots,\xi_{n}\in{B}^{d}\end{subarray}}\Big{|}\int_{{B}^{d}}f_{1}(x)w_{\mu}(x)dx\Big{|}\gtrsim
N^{-r}\asymp n^{-r/d}.$

The proof of Theorem 1.1 is finished. $\hfill\Box$

##  4\. The upper estimates

This section is devoted to proving the upper estimates of the quantities
$e_{n}^{\rm ran}(X_{p}^{r})$ given as in (1.5). That is, for $1\leq
p\leq\infty$, $r>(d+2\mu)/p$, and $0<\tau\leq\infty$,

(4.1) $e_{n}^{\rm ran}(BX_{p}^{r})\lesssim
n^{-\frac{r}{d}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}},$

where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or $B_{\tau}^{r}(L_{p,\mu})$.

For this purpose, we will use the positive quadrature rule and the filtered
hyperinterpolation operator to construct an randomized algorithm to attain the
upper bounds. Due to Henrich [15], we need a concrete Monte Carlo method by
virtue of the standard Monte Carlo algorithm. It is defined as follows: let
$\\{\xi_{i}\\}_{i=1}^{N}$ be independent, ${B}^{d}$-valued, distributed over
${B}^{d}$ with respect to the measure $w_{\mu}(x)dx$ random vectors on
probability space $(\Omega,\Sigma,\nu)$. For any $h\in C({B}^{d})$, we put

(4.2) $Q_{N}^{\omega}(h)=\frac{1}{N}\sum_{i=1}^{N}h(\xi_{i}({\omega})),\
{\omega}\in\Omega.$

The following lemma can be drawn in a same way as in [15, Proposition 5.4].
Here we omit the proof.

######  Lemma 4.1.

Let $1\leq p\leq\infty$ and $\mu\geq 0$, Then for any $h\in C({B}^{d})$, we
have

(4.3) ${E}_{\omega}|{\rm INT}_{d}(h)-Q_{N}^{\omega}(h)|\lesssim
N^{-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}\|h\|_{p,\mu}.$

Now we prove (4.1).

Proof of (4.1).

Let $n\in{N}$. Without loss of generality we assume that $n$ is sufficiently
large. Then there exists a positive quadrature rule

$\int_{\mathbb{B}^{d}}f(x)w_{\mu}(x)dx\approx
Q_{L}(f):=\sum_{\xi\in\Lambda_{L}}\lambda_{\xi}f(\xi),\ \lambda_{\xi}>0,$

which is exact for $\Pi_{3L}^{d}$, where $\\#\Lambda_{L}\leq n/2$ and $n\asymp
L^{d}$.

As in Section 3.1, we can construct the filtered hyperinterpolation operator
by

$G_{L}(f)(x)=\sum_{\xi\in\Lambda_{L}}\lambda_{\xi}f(\xi)K_{L,\eta}(x,\xi),$

where $K_{L,\eta}$ is given as in (2.3). Hence, according to Theorem 3.1 we
have for any $f\in X_{p}^{r},\ 1\leq p\leq\infty,\ r>(d+2\mu)/{p}$,

(4.4) $\|f-G_{L}(f)\|_{p,\mu}\lesssim L^{-r}\|f\|_{X_{p}^{r}}.$

Let $N=\lfloor\frac{n}{2}\rfloor$, where $\lfloor x\rfloor$ denotes the
largest integer not exceeding $x$. We define the randomized algorithm
$(A_{n}^{\omega})$ by

$\displaystyle A_{n}^{\omega}(f)=Q_{N}^{\omega}(f-G_{L}(f))+{\rm
INT}_{d}(G_{L}(f)),$

where $f\in C({B}^{d})$, and $Q_{N}^{\omega}$ is the standard Monte Carlo
algorithm given as in (4.2). We also note that

${\rm INT}_{d}(G_{L}(f))=\sum_{\xi\in\Lambda_{\xi}}{\lambda}_{\xi}f(\xi).$

Clearly, the algorithm $(A_{n}^{\omega})$ use only at most
$\\#\Lambda_{L}+N\leq n$ function values of $f$. This means that
$(A_{n}^{\omega})\in\mathcal{A}_{n}^{\rm ran}$. Also the algorithm
$(A_{n}^{\omega})$ is a randomized linear algorithm. It is easy to check that

$|{\rm INT}_{d}(f)-A_{n}^{\rm{\omega}}(f)|=|{\rm
INT}_{d}(g)-Q_{N}^{\omega}(g)|,$

where $g=f-G_{L}(f)$. Combining with (4.3) and (4.4), we obtain for $f\in
BX_{p}^{r}$, $r>(d+2\mu)/p$,

$\displaystyle{E}_{\omega}|{\rm INT}_{d}(f)-A_{n}^{{\omega}}(f)|$
$\displaystyle={E}_{\omega}|{\rm INT}_{d}(g)-Q_{N}^{\omega}(g)|$
$\displaystyle\lesssim
N^{-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}\|f-G_{L}(f)\|_{p,\mu}$
$\displaystyle\lesssim
N^{-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}L^{-r}\asymp
n^{-\frac{r}{d}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}},$

which leads to

$e_{n}^{\rm ran}(BX_{p}^{r})\leq e^{\rm
ran}(BX_{p}^{r},(A_{n}^{\omega}))\lesssim
n^{-\frac{r}{d}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}}.$

This completes the proof of (4.1). $\hfill\Box$

##  5\.  Lower estimates

This section is devoted to proving the lower estimates of the quantities
$e_{n}^{\rm ran}(X_{p}^{r})$ given as in (1.5). That is, for $1\leq
p\leq\infty$, $r>(d+2\mu)/p$, and $0<\tau\leq\infty$,

(5.1) $e_{n}^{\rm ran}(BX_{p}^{r})\gtrsim
n^{-\frac{r}{d}-\frac{1}{2}+(\frac{1}{p}-\frac{1}{2})_{+}},$

where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or $B_{\tau}^{r}(L_{p,\mu})$.
Theorem 1.2 follows from (4.1) and (5.1) immediately.

The proof of (5.1) is based on the idea of Bakhvalov in [1] and Novak in [24,
25].

######  Lemma 5.1.

(See [24, Lemma 3].)

(a) Let $F\subset L_{1,\mu}$ and $\psi_{j},\,j=1,\dots,4n$, with the following
conditions:

(i) the $\psi_{j}$ have disjoint supports and satisfy

${\rm INT_{d}}(\psi_{j})=\int_{{B}^{d}}\psi_{j}(x)w_{\mu}(x)dx\geq{\delta},\
{\rm for}\ j=1,\dots,4n.$

(ii)
$F_{1}:=\big{\\{}\sum\limits_{j=1}^{4n}{\alpha}_{j}\psi_{j}\,\big{|}\,\alpha_{j}\in\\{-1,1\\}\big{\\}}\subset
F$.

Then

$e_{n}^{\rm ran}(F)\geq\frac{1}{2}{\delta}n^{\frac{1}{2}}.$

(b) We assume that instead of (ii) in statement (a) the property

(ii’) $F_{2}:=\big{\\{}\pm\psi_{j}\,\big{|}\,j=1,\dots,4n\big{\\}}\subset F$.

Then

$e^{\rm ran}_{n}(F)\geq\frac{1}{4}{\delta}.$

By this lemma, we proceed to construct a sequence of functions
$\\{\psi_{j}\\}_{j=1}^{4n}$ satisfying the conditions of Lemma 5.1 for
$F=BX_{p}^{r}$, where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or
$B_{\tau}^{r}(L_{p,\mu})$, $1\leq p\leq\infty,\ r>(d+2\mu)/p,\
0<\tau\leq\infty$.

For a given $n\in{N}$, choose a positive integer $m$ satisfying $n\asymp
m^{d}$, $m\geq 6$, and $\\{x_{j}\\}_{j=1}^{4n}\subset{\bf B}({\bf
0},\frac{2}{3})$ such that

${\bf B}(x_{i},\frac{2}{m})\bigcap{\bf B}(x_{j},\frac{2}{m})=\emptyset,\ \
{\rm if}\ \ i\neq j,$

where ${\bf B}(\xi,r)=\big{\\{}x\in{B}^{d}\,\big{|}\,|x-\xi|\leq r\big{\\}}$
for $\xi\in{B}^{d}$ and $r>0$.

Let $\varphi$ be a nonnegative $C^{\infty}$-function on $\mathbb{R}^{d}$
supported in ${B}^{d}$ and being equal to 1 on ${\bf B}({\bf 0},\frac{1}{2})$.
We define

$\varphi_{j}(x)=\varphi(m(x-x_{j})),\ j=1,\dots,4n.$

Clearly,

${\rm supp}\,\varphi_{j}\subset{\bf B}(x_{j},\frac{1}{m})\subset{\bf B}({\bf
0},\frac{5}{6}),\ j=1,\dots,4n,$

and

(5.2) ${\rm supp}\,\varphi_{i}\cap{\rm supp}\,\varphi_{j}=\emptyset,\ {\rm
for}\ i\neq j.$

It is easy to verify that

(5.3) $\|\varphi_{j}\|_{p,\mu}\asymp\Big{(}\int_{{\bf
B}(x_{j},\frac{1}{m})}|\varphi_{j}(x)|^{p}dx\Big{)}^{1/p}=\Big{(}\int_{{\bf
B}({\bf 0},\frac{1}{m})}|\varphi(mx)|^{p}dx\Big{)}^{1/p}\asymp m^{-d/p}.$

We set

$F_{0}:=\big{\\{}f_{\boldsymbol{{\alpha}}}:=\sum\limits_{j=1}^{4n}{\alpha}_{j}\varphi_{j}\,\big{|}\,{\boldsymbol{{\alpha}}}=({\alpha}_{1},\cdots,{\alpha}_{4n})\in\mathbb{R}^{4n}\big{\\}}.$

Then we have the following lemma.

######  Lemma 5.2.

If $f_{\boldsymbol{{\alpha}}}\in F_{0}$, then for $r>0$, $1\leq p\leq\infty$,
and $0<\tau\leq\infty$,

(5.4) $\displaystyle\|f_{{\boldsymbol{{\alpha}}}}\|_{X_{p}^{r}}\lesssim
m^{r-d/p}\|{\boldsymbol{{\alpha}}}\|_{l_{p}^{4n}},$

where $X_{p}^{r}$ denotes $W_{p,\mu}^{r}$ or $B_{\tau}^{r}(L_{p,\mu})$, and

$\|{\boldsymbol{{\alpha}}}\|_{\ell_{p}^{4n}}:=\left\\{\begin{aligned}
&\big{(}\sum_{j=1}^{4n}|{\alpha}_{j}|^{p}\big{)}^{1/p},\ \ &1\leq p<\infty,\\\
&\max\limits_{1\leq j\leq 4n}|{\alpha}_{j}|,\ \ \
&p=\infty.\end{aligned}\right.$

###### Proof.

Indeed, for any $f_{\boldsymbol{{\alpha}}}\in F_{0}$, it follows from (5.2)
and (5.3) that

(5.5) $\|f_{\boldsymbol{{\alpha}}}\|_{p,\mu}\asymp
m^{-d/p}\|{\boldsymbol{{\alpha}}}\|_{\ell_{p}^{4n}}.$

For a positive integer $v>r$, by the definition of $-D_{\mu}$ and (5.2), it is
easy to verify that

${\rm supp}\,(-D_{\mu})^{v}\varphi_{i}\,\bigcap\,{\rm
supp}\,(-D_{\mu})^{v}\varphi_{j}=\emptyset,\ {\rm for}\ i\neq j,$

and

$\|(-D_{\mu})^{v}\varphi_{j}\|_{p,\mu}\lesssim m^{2v-d/p},$

which leads to

(5.6) $\|(-D_{\mu})^{v}f_{\boldsymbol{{\alpha}}}\|_{p,\mu}\lesssim
m^{2v-d/p}\|{\boldsymbol{{\alpha}}}\|_{\ell_{p}^{4n}}.$

It follows from the Kolmogorov type inequality (see [8, Theorem 8.1]) that

(5.7)
$\|(-D_{\mu})^{r/2}f_{\boldsymbol{{\alpha}}}\|_{p,\mu}\lesssim\|(-D_{\mu})^{v}f_{\boldsymbol{{\alpha}}}\|_{p,\mu}^{\frac{r}{2v}}\,\|f_{\boldsymbol{{\alpha}}}\|_{p,\mu}^{\frac{2v-r}{2v}}\lesssim
m^{r-d/p}\|{\boldsymbol{{\alpha}}}\|_{\ell_{p}^{4n}},$

which combining with (5.5), we obtain (5.4) for $W_{p,\mu}^{r}$.

By the fact that

$\|f_{\boldsymbol{{\alpha}}}\|_{B_{\infty}^{r}(L_{p,\mu})}\lesssim\|f_{\boldsymbol{{\alpha}}}\|_{B_{\tau}^{r}(L_{p,\mu})},\
0<\tau<\infty,$

it suffices to show (5.4) for $B_{\tau}^{r}(L_{p,\mu})$, $0<\tau<\infty$.
Since
$E_{2^{j}}(f_{\boldsymbol{{\alpha}}})_{p,\mu}\leq\|f_{\boldsymbol{{\alpha}}}\|_{p,\mu}$
for any $j\geq 0$, by (5.4) we have

$\displaystyle\sum\limits_{2^{j}<m}\Big{(}2^{jr}E_{2^{j}}(f_{\boldsymbol{{\alpha}}})_{p,\mu}\Big{)}^{\tau}$
$\displaystyle\leq\|f_{\boldsymbol{{\alpha}}}\|_{p,\mu}^{\tau}\sum\limits_{2^{j}<m}2^{jr\tau}$
(5.8) $\displaystyle\asymp
m^{r\tau}\|f_{\boldsymbol{{\alpha}}}\|_{p,\mu}^{\tau}\asymp
m^{(r-d/p)\tau}\|{\boldsymbol{{\alpha}}}\|_{\ell_{p}^{4n}}^{\tau}.$

Choose a positive number $\upsilon>r$, by (2.4) we obtain for any $j\geq 0$,

$E_{2^{j}}(f_{\boldsymbol{{\alpha}}})_{p,\mu}\lesssim
2^{-j\upsilon}\|f_{\boldsymbol{{\alpha}}}\|_{W_{p,\mu}^{\upsilon}},$

which combining with (5.4) for $W_{p,\mu}^{r}$, we get

$\displaystyle\sum\limits_{2^{j}\geq
m}\Big{(}2^{jr}E_{2^{j}}(f_{\boldsymbol{{\alpha}}})_{p,\mu}\Big{)}^{\tau}$
$\displaystyle\leq\|f_{\boldsymbol{{\alpha}}}\|_{W_{p,\mu}^{\upsilon}}^{\tau}\sum\limits_{2^{j}\geq
m}2^{j(r-\upsilon)\tau}$ (5.9) $\displaystyle\asymp
m^{(r-\upsilon)\tau}\|f_{\boldsymbol{{\alpha}}}\|_{W_{p,\mu}^{\upsilon}}^{\tau}\lesssim
m^{(r-d/p)\tau}\|{\boldsymbol{{\alpha}}}\|_{\ell_{p}^{4n}}^{\tau}.$

It follows from (5.5), (5), and (5) that

$\displaystyle\|f\|_{B_{\tau}^{r}(L_{p,\mu})}$
$\displaystyle:=\|f\|_{p,\mu}+\Big{(}\sum\limits_{j=0}^{\infty}\Big{(}2^{jr}E_{2^{j}}(f_{\boldsymbol{{\alpha}}})_{p,\mu}\Big{)}^{\tau}\Big{)}^{1/\tau}\lesssim
m^{r-d/p}\|{\boldsymbol{{\alpha}}}\|_{\ell_{p}^{4n}}.$

This completes the proof of Lemma 5.2. ∎

Finally we turn to prove (5.1).

Proof of (5.1).

First we consider the case $2\leq p\leq\infty$. By the fact that

$X_{\infty}^{r}\subset X_{p}^{r},\ \ 2\leq p\leq\infty,$

it suffices to consider the case $p=\infty$. It follows from (5.4) that when
${\alpha}_{j}\in\\{-1,1\\},\,j=1,\dots,4n,$

$\|f_{\boldsymbol{{\alpha}}}\|_{X_{\infty}^{r}}\lesssim
m^{r}\|{\boldsymbol{{\alpha}}}\|_{\ell_{\infty}^{4n}}\lesssim m^{r}.$

Hence, there exists a positive constant $C_{1}$ such that
$C_{1}m^{-r}f_{\boldsymbol{{\alpha}}}\in BX_{\infty}^{r}$. Set

$\psi_{j}(x):=C_{1}m^{-r}\varphi_{j}(x),\ j=1,\dots,4n.$

We have

$F_{1}:=\Big{\\{}\sum\limits_{j=1}^{4n}{\alpha}_{j}\psi_{j}\ \big{|}\
\alpha_{j}\in\\{-1,1\\},\ j=1,\dots,4n\Big{\\}}\subset BX_{\infty}^{r}.$

It follows from (5.3) that

${\rm
INT}_{d}(\psi_{j})=\int_{{B}^{d}}\psi_{j}(x)w_{\mu}(x)dx=C_{1}m^{-r}\|\varphi_{j}\|_{1,\mu}\asymp
m^{-r-d},$

Applying Lemma 5.1 (a) we obtain for $2\leq p\leq\infty$,

(5.10) $e_{n}^{\rm ran}(BX_{p}^{r})\geq e_{n}^{\rm
ran}(BX_{\infty}^{r})\gtrsim m^{-r-d}n^{1/2}\asymp
n^{-\frac{r}{d}-\frac{1}{2}}.$

Next we consider the case $1\leq p<2$. It follows from (5.4) that

$\|\pm\varphi_{j}\|_{X_{p}^{r}}\lesssim m^{r-d/p}.$

Hence, there exists a positive constant $C_{2}$ such that

$\psi_{j}(x):=C_{2}m^{-r+d/p}\varphi_{j}(x)\in BX_{p}^{r},\ j=1,\dots,4n.$

We have

$F_{2}:=\\{\pm\psi_{j}:\ j=1,\dots,4n\\}\subset BX_{p}^{r}.$

It follows from (5.3) that

${\rm
INT}_{d}(\psi_{j})=\int_{{B}^{d}}\psi_{j}(x)w_{\mu}(x)dx=C_{2}m^{-r+d/p}\|\varphi_{j}\|_{1,\mu}\asymp
m^{-r+d/p-d}.$

Applying Lemma 5.1 (b), we obtain for $1\leq p<2$,

$e_{n}^{\rm ran}(BX_{p}^{r})\gtrsim m^{-r+d/p-d}\asymp
n^{-\frac{r}{d}+\frac{1}{p}-1},$

which combining with (5.10), gives the lower bounds of $e_{n}^{\rm
ran}(BX_{p}^{r})$ for $1\leq p\leq\infty$.

This completes the proof of (5.1). $\hfill\Box$

Acknowledgment Jiansong Li and Heping Wang were supported by the National
Natural Science Foundation of China (Project no. 11671271).

## References

  * [1] N. S. Bakhvalov, On approximate computation of integrals, Vestnik MGV, Ser. Math. Mech. Aston. Phys. Chem. 4 (1959) 3-18.
  * [2] N. S. Bakhvalov, On a rate of convergence of indeterministic integration processes within the functional classes $W_{p}^{l}$, Theory Probab. Appl. 7 (1962) 226-227.
  * [3] N. S. Bakhvalov, On the optimality of linear methods for operator approximation in convex classes of functions, USSR Computational Mathematics and Mathematical Physics, 11 (1971) 244-249.
  * [4] J. S. Brauchart, K. Hesse, Numerical integration over spheres of arbitrary dimension, Constr. Approx. 25 (1) (2007) 41-71.
  * [5] V. A. Bykovskii, On the correct order of the error of optimal cubature formulas in spaces with dominant derivative, and on quadratic deviations of grids. Akad. Sci. USSR, Vladivostok, Computing Center Far-Eastern Scientific Center, 1985.
  * [6] F. Dai, H. Wang, Optimal cubature formulas in weighted Besov spaces with $A_{\infty}$ weights on multivariate domains, Constr. Approx. 37 (2013) 167-194.
  * [7] F. Dai, Y. Xu, Approximation Theory and Harmonic Analysis on Spheres and Balls, Springer, 2013.
  * [8] Z. Ditzian, Fractional derivatives and best approximation, Acta Math. 81 (4) (1998) 323-348.
  * [9] L. Duan, P. Ye, Integration over the sphere $\mathbb{S}^{d-1}$ on Besov classes in different settings, Preprint.
  * [10] V. V. Dubinin, Cubature formulas for classes of functions with bounded mixed difference. Math. Sb. 183 (7) (1992) 23-34.
  * [11] V. V. Dubinin, Cubature formulas for Besov classes, Izv. Ross. Akad. Nauk Ser. Math. 61 (2) (1997) 27-52.
  * [12] D. Dung, T. Ullrich, Lower bounds for the integration error for multivariate functions with mixed smoothness and optimal Fibonacci cubature for functions on the square, Math. Nachr. 288 (7) (2015) 743-762.
  * [13] G. Fang, P. Ye, Complexity of deterministic and randomized methods for multivariate integration problems for the class $H^{p}(I_{d})$, IMA J. Numer. Anal. 25 (3) (2005) 473-485.
  * [14] K. K. Frolov, Upper bounds on the error of quadrature formulas on classes of functions, Doklady Akademy Nauk USSR, 231 (1976) 818-821.
  * [15] S. Heinrich, Random approximation in numerical analysis, Appl. Math. 150 (1994) 123-171.
  * [16] K. Hesse, I. H. Sloan, Hyperinterpolation on the sphere, in: “Frontiers in Interpolation and Approximation (Dedicated to the memory of Ambikeshwar Sharma)” (editors: N.K. Govil, H.N. Mhaskar, R.N. Mohapatra, Z. Nashed, J. Szabados), Chapman & Hall/CRC, 2006 pp. 213-248.
  * [17] K. Hesse, A lower bound for the worse-case cubature error on sphere of arbitrary dimension, Numer. Math. 103 (2006) 413-433.
  * [18] K. Hesse, H. N. Mhaskar, I. H. Sloan, Quadrature in Besov spaces on the Euclidean sphere, J. Complexity 23 (2007) 528-552.
  * [19] D. Krieg, E. Novak, A universal algorithm for multivariate integration, Found. Comput. Math. 17 (4) (2017) 895-916.
  * [20] G. Kyriazis, P. Petrushev, Y. Xu, Decomposition of weighted Triebel-Lizorkin and Besov spaces on the ball, Proc. London Math. Soc. 97 (2008) 477-513.
  * [21] Jiansong Li, Heping Wang, Weighted $\ell_{q}$ approximation problems on the ball and on the sphere, preprint.
  * [22] Jingyu Li, On Filtered Polynomial Approximation on the Unit Ball, Master Thesis, Capital Normal University, 2018.
  * [23] G.G. Lorentz, Approximation of Functions. Holt, Rinehart and Winston, New York, 1966.
  * [24] E. Novak, Stochastic properties of quadrature formulas, Numer. Math. 53 (1988) 609-620.
  * [25] E. Novak, Deterministic and Stochastic Error Bound in Numerical Analysis, Springer, Berlin, 1988.
  * [26] E. Novak, Some results on the complexity of numerical integration. Monte Carlo and quasi-Monte Carlo methods, Springer Proc. Math. Stat. 163 (2016) 161-183.
  * [27] V. K. Nguyen, M. Ullrich, T. Ullrich, Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube, Constr. Approx. 46 (2017) 69-108.
  * [28] P. Petrushev, Y. Xu, Localized polynomial frames on the ball, Constr. Approx. 27 (2008) 121-148.
  * [29] M. Reimer, Hyperinterpolation on the sphere at the minimal projection order, J. Approx. Theory 104 (2) (2000) 272-286.
  * [30] I. H. Sloan, R. S. Womersley, Filtered hyperinterpolation: a constructive polynomial approximation on the sphere, GEM Int. J. Geomath. 3 (1) (2012) 95-117.
  * [31] M. M. Skriganov, Constructions of uniform distributions in terms of geometry of numbers, St. Petersburg Math. J. 6 (1995) 635-664.
  * [32] V. N. Temlyakov, On a way of obtaining lower estimates for the error of quadrature formulas, Math. USSR Sb. Russian, 181 (1990) 1403-1413. English translation: Math. USSR Sbornik, 71 (1992) 247-257.
  * [33] J. F. Traub, G. W. Wasilkowski, H. Woźniakowski, Information-Based Complexity, Academic Press, New York, 1988.
  * [34] M. Ullrich, T. Ullrich, The role of Frolov’s cubature formula for functions with bounded mixed derivative, SIAM J. Numer. Anal. 54 (2) (2016) 969-993.
  * [35] M. Ullrich, A Monte Carlo method for integration of multivariate smooth functions, SIAM J. Numer. Anal. 55 (3) (2017) 1188-1200.
  * [36] H. Wang, Quadrature formulas for classes of functions with Bounded mixed derivative or difference. Science in China (Series A) 40 (5) (1997) 429-495.
  * [37] H. Wang, Optimal lower estimates for the worst case quadrature error and the approximation by hyperinterpolation operators in the Sobolev space setting on the sphere, Int. J. Wavelets Multiresolut. Inf. Process. 7 (6) (2009) 813-823.
  * [38] H. Wang, I. H. Sloan, On filtered polynomial approximation on the sphere, J. Fourier Anal. Appl. 23 (4) (2017) 863-876.
  * [39] H. Wang, Y. Zhang, Optimal randmized quadrature for Sobolev classes on the sphere, preprint.
  * [40] H. Wang, Z. Huang, C. Li, L. Wei, On the norm of the hyperinterpolation operator on the unit ball, J. Approx. Theory 192 (2015) 132-143.
  * [41] Y. Xu, Summability of Fourier orthogonal series for Jacobi weight on a ball in ${R}^{d}$, Trans. Amer. Math. Soc. 351 (1999) 2439-2458.
  * [42] Y. Xu, Weighted approximation of functions on the unit sphere, Constr. Approx. 21 (2005) 1-28.
  * [43] P. Ye, Computational complexity of the integration problem for anisotropic classes, Adv. Comput. Math. 23 (4) (2005) 375392.