Optimal cubature in Besov spaces with dominating mixed smoothness on the unit square

Jiansong Li, Heping Wang

Shu Tezuka, Anargyros Papageorgiou

Fred J. Hickernell, Lluís Antoni Jiménez Rugama, Da Li

Michael Gnewuch, Josef Dick, Lev Markhasin +1 more

We study the integration problem over the $s$-dimensional unit cube on four types of Banach spaces of integrands. First we consider Haar wavelet spaces, consisting of functions whose Haar wavelet coefficients exhibit a certain decay behavior measured by a parameter $α>0$. We study the worst case error of integration over the norm unit ball and provide upper error bounds for quasi-Monte Carlo (QMC) cubature rules based on arbitrary $(t,m,s)$-nets as well as matching lower error bounds for arbitrary cubature rules. These results show that using arbitrary $(t,m,s)$-nets as sample points yields the best possible rate of convergence. Afterwards we study spaces of integrands of fractional smoothness $α\in (0,1)$ and state a sharp Koksma-Hlawka-type inequality. More precisely, we show that on those spaces the worst case error of integration is equal to the corresponding fractional discrepancy. Those spaces can be continuously embedded into tensor product Bessel potential spaces, also known as Sobolev spaces of dominated mixed smoothness, with the same set of parameters. The latter spaces can be embedded into suitable Besov spaces of dominating mixed smoothness $α$, which in turn can be embedded into the Haar wavelet spaces with the same set of parameters. Therefore our upper error bounds on Haar wavelet spaces for QMC cubatures based on $(t,m,s)$-nets transfer (with possibly different constants) to the corresponding spaces of integrands of fractional smoothness and to Sobolev and Besov spaces of dominating mixed smoothness. Moreover, known lower error bounds for periodic Sobolev and Besov spaces of dominating mixed smoothness show that QMC integration based on arbitrary $(t,m,s)$-nets yields the best possible convergence rate on periodic as well as on non-periodic Sobolev and Besov spaces of dominating smoothness.

Ðinh Dũng, Tino Ullrich

We prove lower bounds for the error of optimal cubature formulas for $d$-variate functions from Besov spaces of mixed smoothness $B^{\alpha}_{p,\theta}({\mathbb G}^d)$ in the case $0 1/p$, and upper bounds for QMC methods on the Fibonacci lattice for two-variate periodic functions from $B^{\alpha}_{p,\theta}({\mathbb G}^2)$ in the case $1\leq p \leq \infty$, $0 1/p$, where ${\mathbb G}^d$ is either the $d$-dimensional torus ${\mathbb T}^d$ or the $d$-dimensional cube $[0,1]^d$. In combination these results yield the correct asymptotic of the error of optimal cubature formulas for functions from $B^{\alpha}_{p,\theta}({\mathbb G}^2)$ and indicate that a corresponding results is most likely also true in case $d>2$. This is compared to the obtained correct asymptotic of optimal cubature formulas on Smolyak grids which results in the observation that any cubature formula on Smolyak grids is never optimal for the general setting.

Bernd Käßemodel, Tino Ullrich

We study the complexity of high-dimensional integration of periodic functions from Besov spaces $S^r_{p,q}B(\mathbb{T}^d)$ with mixed smoothness in the quantum model of computation. We construct new quantum algorithms based on the multivariate Faber-Schauder decomposition of such functions and analyze their convergence rates. We show a gain of one convergence order compared to the well-known deterministic rates of convergence. We additionally obtain lower bounds showing the optimality of our results up to logarithms.