Quasi-Monte Carlo methods can be efficient for integration over products of spheres (Q1772684): Difference between revisions

The paper deals with multivariate quasi-Monte Carlo (QMC) integration of functions defined on the product of \(d\) copies of the unit sphere like, e.~g., \[ \int_{S^2} \cdots \int_{S^2} f(x_1, \ldots, x_d) d \omega(x_1) \cdots d \omega(x_d) \] where \(S^2 \subseteq \mathbb{R}^3\) denotes the usual unit sphere and \(d \omega(x)\) is the surface measure of the unit sphere. Most deterministic numerical methods for such problems have a cost (the number of function evaluations) that grows exponentially with \(d\). An important theoretical question, discussed in the paper, is the possibility to find a function space setting in which the cost, given by the number of function evaluations \(n(\varepsilon,d)\) needed to reduce the initial error by a factor \(\varepsilon\), is bounded independently on \(d\). The authors prove that it is possible, but with arguments that tell us nothing about the construction of appropriate numerical schemes to reach it. The study is similar in spirit to that made earlier for the product of unit cubes. The integrands \(f\) are assumed to belong to some Sobolev space \(H_d\), which is a tensor product of \(d\) reproducing kernel Hilbert spaces with the factors in the tensor product weighted by certain parameters \(\gamma_{d,j}\), where \(j=1, 2, \dots, d\). The QMC tractability and strong tractability is discussed according to the definition that the tractability in the space \(H_d\) means that \[ n(\varepsilon,d) \leq C \varepsilon^{-p} d^q \] holds for some nonnegative constants \(C\), \(p\), and \(q\) independent of \(\varepsilon\) and \(d\), whereas the strong QMC tractability corresponds to \(q=0\). The main result is the proof that for positive and uniformly bounded parameters \(\gamma_{d,j}\) strong QMC tractability holds if and only if \[ \lim\limits_{d \to \infty} \sup \sum\limits_{j=1}^{d} \gamma_{d,j} < \infty \] and the QMC tractability holds if and only if \[ \lim\limits_{d \to \infty} \sup \frac{\sum\limits_{j=1}^{d} \gamma_{d,j}}{\log(d+1)} < \infty \;. \] The results of this paper asserts the existence of a sequence of QMC rules for integration on the product of spheres with the Monte Carlo rate of convergence \(O \left( n^{-1/2} \right)\), although the proof is nonconstructive in the sense that it does not tell us how to achieve the bound.