Periodization strategy may fail in high dimensions

DOI10.1007/S11075-007-9145-8MaRDI QIDQ2471079zbMATH OpenOpenAlexFDO

Authors F. Y. Kuo, Ian H. Sloan, H. Woźniakowski

Publication date 18 February 2008

Published in Numerical Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11075-007-9145-8

error bounds lattice rules multivariate integration periodization quadrature quasi-Monte Carlo methods worst case error

Monte Carlo methods (65C05) Numerical quadrature and cubature formulas (65D32) Complexity and performance of numerical algorithms (65Y20)

Review text

The authors discuss a well known periodization strategy for the numerical evaluation of the integral of a smooth function \(f\) over the \(d\)-dimensional unit cube \[ I_{d}(f)=\int_{[0,1]^{d}}f(x)\,dx, \] where \(d\) may be arbitrarily large. Periodization of the integrand means that the integrand \(f\) is transformed into another function \(F\) defined on \([0,1]^{d}\) in such a way that \[ I_{d}(f)=I_{d}(F), \] with \(F\) having similar smoothness characteristics to \(f\) over the unit cube, but being also at least continuous, and preferably somewhat smoother, when extended as a 1-periodic function on \(\mathbb R^{d}\). The authors consider only the version of periodization that rests upon a single \(C^{\infty}\) scalar function \(\psi\) that is increasing on \([0,1]\), maps from \([0,1]\) onto \([0,1]\), and has some number of derivatives \(r\geq 1\) vanishing at the two ends. The function \(F\) is defined such that \[ F(t):=f(\psi(t))\omega_{d}(t), \] where \( \psi (t)=(\psi(t_{1}),\dots,\psi(t_{d}))\), \(\omega_{d}(t):=\prod_{j=1}^{d}\omega(t_{j})\) and \(\omega(t)= \psi^{\prime}(t).\) The authors compare the error bounds for different approaches of the integration, and show that under the periodization strategy the norm of the periodized function \(F\) can be exponentially large in \(d\) compared to the norm of the original function \(f\). The worst case error for a quadrature approximation \(Q_{n,d}\) in some function space \(H\) is defined by \[ e^{\text{wor}}(Q_{n,d}):=\sup_{\|f\|_{H}\leq 1}|I_{d}(f)-Q_{n,d}(f)|, \] where \(\|\cdot\|_{H}\) denotes the norm in \(H\). Let \(Q_{n,d}^{\text{qmc}}(f)={\frac{1}{n}\sum_{k=1}^{n}f(\tau_{k})}\) be a quasi-Monte Carlo (QMC) rule, where \(\tau_{1},\dots,\tau_{n}\) are points in \([0,1]^{d}\) chosen in some deterministic way. A rank-1 lattice rule \(Q_{n,d}^{\text{lat}}\) is a QMC rule with quadrature points given by \[ \tau_{k}=\biggl\{\frac{kz}{n}\biggr\},\quad k=1,2,\dots, n, \] where \(z\in Z^{d}\) is the generating vector, and the braces around a vector indicate that each component in the vector is to be replaced by its fractional part. The authors study the periodization strategy for th special case \(f=1\). In this case \(F(t)=\omega_{d}(t)\) and the exact integral is of course 1. The authors show that, depending on the choice of \(z\), for fixed \(n\), the quadrature sum \( Q_{n,d}^{\text{lat}}(F)= Q_{n,d}^{\text{lat}}(\omega_{d})\) can be exponentially large in \(d\) or exponentially small in \(d\). The authors study lower bounds for the worst case error of the lattice rule and conjecture that all lattice rules fail for large \(d\). That is, if the number of points \(n\) is fixed and let \(d\) go to infinity then the worst case error of any lattice rule is bounded from below by a positive constant independent of \(n\). The authors present a number of cases suggesting that this conjecture is indeed true, but the most interesting case, when the sum of the weights of the corresponding Sobolev space is bounded in \(d\), remains open.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Periodization strategy may fail in high dimensions

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