A Randomised Lattice Rule Algorithm with Pre-determined Generating Vector and Random Number of Points for Korobov Spaces with 0<α≤1/2
A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with 0<α≤1/2
In previous work (Kuo, Nuyens, Wilkes, 2023), we showed that a lattice rule with a pre-determined generating vector but random number of points can achieve the near optimal convergence of O(n−α−1/2+ε), ε>0, for the worst case expected error, commonly referred to as the randomised error, for numerical integration of high-dimensional functions in the Korobov space with smoothness α>1/2. Compared to the optimal deterministic rate of O(n−α+ε), ε>0, such a randomised algorithm is capable of an extra half in the rate of convergence. In this paper, we show that a pre-determined generating vector also exists in the case of 0<α≤1/2. Also here we obtain the near optimal convergence of O(n−α−1/2+ε), ε>0; or in more detail, we obtain O(rn−α−1/2+1/(2r)+ε′) which holds for any choices of ε′>0 and r∈N with r>1/(2α).
We two distinct practical problems in high-dimensional approximation. The first concerns the approximation of integrals using a particular randomised lattice rule, while the second focuses on function approximation with a generalisation of the rank-1 lattice known as the generated set. These algorithms are applied to functions in reproducing kernel Hilbert spaces defined on the torus, which are contained within the Wiener algebra. Our randomised lattice algorithm extends previous approaches by reducing the randomness, allowing for greater control over the structure of the sample points. The generating vector of the lattice is predetermined before the algorithm runs, with the only random element being the selection of the number of sample points. We demonstrate that there exist generating vectors for which this algorithm achieves a near-optimal rate of randomised error convergence. Furthermore, we produce a method by which such a generating vector can be constructed component by component. This method can be implemented efficiently using a fast algorithm, where the time required to produce a suitable generating vector exceeds that of computing the randomised error by only a logarithmic factor. We also introduce a random shift to this randomised algorithm in order to produce results for a larger function space where pointwise evaluation is not well defined and provide lower bounds on the error which can be achieved by these fixed vector algorithms. Generated sets are an extension of rank-1 lattice rules which allow the generator to have real, rather than strictly integer, components. While rank-1 lattices can be shown to only achieve at best half the optimal order of error convergence for function approximation in the worst-case L²-setting, we show that this restriction does not apply to generated sets, which are capable of achieving the optimal order. In a function space that generalises the Korobov space, we will demonstrate the existence of generators for which a least squares approximation algorithm is able to produce an error rate very close to the optimal bound. Additionally, we show that rational generating vectors with sufficiently large common denominators can achieve a comparable rate. Finally, we specialise these results to the weighted Korobov space, where we provide a more precise error bound and prove a tractability result, subject to a common condition on the weights of the space.
We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich [J. Approx. Theory 240 (2019), pp. 96–113] shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, γ j \gamma _j , satisfy the summability condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty , where α \alpha is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition ∑ j = 1 ∞ γ j 1 / α > ∞ \sum _{j=1}^{\infty }\gamma _j^{1/\alpha }>\infty holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.