Randomized sparse grid algorithms for multivariate integration on Haar-Wavelet spaces

DOI10.1093/IMANUM/DRAB085zbMATH Open1508.65016arXiv2001.08558MaRDI QIDQ6333379FDOQ6333379

Authors: M. Wnuk, Michael Gnewuch 

Publication date: 23 January 2020

Abstract: The emph{deterministic} sparse grid method, also known as Smolyak's method, is a well-established and widely used tool to tackle multivariate approximation problems, and there is a vast literature on it. Much less is known about emph{randomized} versions of the sparse grid method. In this paper we analyze randomized sparse grid algorithms, namely randomized sparse grid quadratures for multivariate integration on the $D$-dimensional unit cube $[0,1{)}^D$. Let $d,sinmathbbN$ be such that $D=dcdots$. The $s$-dimensional building blocks of the sparse grid quadratures are based on stratified sampling for $s=1$ and on scrambled $(0,m,s)$-nets for $sge2$. The spaces of integrands and the error criterion we consider are Haar wavelet spaces with parameter $alpha$ and the randomized error (i.e., the worst case root mean square error), respectively. We prove sharp (i.e., matching) upper and lower bounds for the convergence rates of the $N$-th mininimal errors for all possible combinations of the parameters $d$ and $s$. Our upper error bounds still hold if we consider as spaces of integrands Sobolev spaces of mixed dominated smoothness with smoothness parameters $1/2<alpha<1$ instead of Haar wavelet spaces.

Mathematics Subject Classification ID

Numerical integration (65D30) Numerical methods for wavelets (65T60)

This page was built for publication: Randomized sparse grid algorithms for multivariate integration on Haar-Wavelet spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333379)