Construction of quasi-Monte Carlo rules for multivariate integration in spaces of permutation-invariant functions (Q524414)

The efficient calculation of multidimensional integrals has become more and more important, especially when working with a very high number of dimensions. These problems are numerically feasible only of certain additional assumptions on the integrands. In the present paper the authors consider problems related to the quasi-Monte Carlo algorithms for approximate calculation of multidimensional integrals of integrands that belong to reproducing kernel Hilbert spaces (RKHS). Here, two semi-explicit construction schemes are provided. First, a procedure that is inspired by the well-known component-by-component (CBC) search algorithm for lattice rules is presented. It is proved that the generating vector of a randomly shifted rank-1 lattice rule that achieves an order of the convergence of the worst case error arbitrary close to \({\mathcal O}(N^{-\alpha})\) can be found component-by-component. Here \(\displaystyle \alpha > {1 \over 2}\) denotes the smoothness of the integrands. Second, a completely different approach towards cubature rules that does not rely on the concept of the lattice points is presented. Based on the knowledge about sampling points that are suitable for approximation, iteratively is derived a cubature rule that attaints the desired order of convergence for solving the integration problem in RKHS. In Section 2 the problem setting ise discussed. The basic Hilbert space of periodic functions is introduced. The permutation-invariant subspaces of periodic RKHS are defined. The explicit definition of the main reproducing kernel is given. Section 3 is devoted to the study of the worst case error of the quasi-Monte Carlo rules. The concept of the tractability is briefly recalled. The main tractability result is presented in Proposition 3.1. In Section 4 the main CBC construction is presented. The concept of the \(d\)-dimensional shifted rank-1 lattice rule is given. The concept of the root mean squared worst case error is developed. This approach is based on using the so-called shift invariant kernel which is shown in explicit form. In Proposition 4.1 an upper bound of the worst case error of the integration of permutation-invariant functions by using a shifted rank-1 lattice rule is presented. This is only an existing result. In Subsection 4.2 the CBC construction to search for a generating vector is derived. In Theorem 4.5 it is shown that there exists a shift \(\Delta^* \in [0,1)^d\) such that the worst case error of the integration of \(I_d\)-permutation-invariant functions by using shifted rank-1 lattice rule has an order \({\mathcal O}(n^{-\alpha})\). This is the main result of this section. Section 5 is devoted to the alternative approach. In Section 5.1 a short overview of basic facts related to \(L_2\) approximation problem on more general RKHS is realized. In Subsection 5.2 the cubature rule for general RKHS is derived. The corresponding error analysis is presented in Theorem 5.8. An order \({\mathcal O}(N^{-{p_d + 1\over 2}})\) of the proposed cubature rule is obtained. In Subsection 5.3 the obtained results are applied to the permutation-invariant setting, described in Section 2. The paper is concluded with an Appendix that contains the proofs of some technical lemmas.