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.