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.
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.
We study the multivariate integration problem for periodic functions from the weighted Korobov space in the randomized setting. We introduce a new randomized rank-1 lattice rule with a randomly chosen number of points, which avoids the need for component-by-component construction in the search for good generating vectors while still achieving nearly the optimal rate of the randomized error. Our idea is to exploit the fact that at least half of the possible generating vectors yield nearly the optimal rate of the worst-case error in the deterministic setting. By randomly choosing generating vectors r r times and comparing their corresponding worst-case errors, one can find one generating vector with a desired worst-case error bound with a very high probability, and the (small) failure probability can be controlled by increasing r r logarithmically as a function of the number of points. Numerical experiments are conducted to support our theoretical findings.
This paper studies the multivariate approximation of functions in weighted Korobov spaces using multiple rank-1 lattice rules. It has been shown by Kämmerer and Volkmer (2019) that algorithms based on multiple rank-1 lattices achieve the optimal convergence rate for the L∞ error in Wiener-type spaces, up to logarithmic factors. While this result was translated to weighted Korobov spaces in the recent monograph by Dick, Kritzer, and Pillichshammer (2022), the analysis requires the smoothness parameter α to be greater than 1 and is restricted to product weights. In this paper, we extend this result for multiple rank-1 lattice-based algorithms to the case where 1/2<α≤1 and for general weights, covering a broader range of periodic functions with low smoothness and general relative importance of variables. We also provide a summability condition on the weights to ensure strong polynomial tractability for any α>1/2. Furthermore, by incorporating random shifts into multiple rank-1 lattice-based algorithms, we prove that the resulting randomized algorithm achieves a nearly optimal convergence rate in terms of the worst-case root mean squared L2 error, while retaining the same tractability property.
We study the worst-case approximation of multivariate periodic functions from weighted Korobov spaces H d , α , γ with smoothness α > 1 / 2 and weights γ in L p ( [ 0 , 1 ] d ) , 1 ≤ p ≤ ∞ . We analyze a median lattice algorithm that reconstructs a truncated Fourier series by estimating coefficients on a hyperbolic-cross-type index set using R rank-1 lattice sampling rules with independent randomly chosen generating vectors, and then aggregating the coefficient estimators via the componentwise median. For odd R and odd prime lattice size N , where R depends logarithmically on N , we prove high-probability error bounds in both L ∞ and L 2 . Interpolation then yields the result for all p ∈ [ 1 , ∞ ] . In particular, with high probability, the worst-case L p -error is bounded, for any β > 0 , by C d , α , β , γ , τ , p R 1 2 + ( 1 2 − 1 p ) + N − α + ( 1 2 − 1 p ) + + β , where ( x ) + = max { x , 0 } , and the constant C d , α , β , γ , τ , p is independent of N and R . For p = ∞ , the constant is dimension-independent under the summability condition ∑ j = 1 ∞ γ j 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.
This paper studies the error bounds of multivariate integration in weighted function spaces using lattice rules of the Korobov form, in which the generating vector for an n-point rule with n prime has the form (1,a,...,a d -1 ) (mod,n). With the parameter a chosen optimally, we establish new error bounds for Korobov lattice rules in weighted Korobov spaces. In particular, we prove that if the weights decay sufficiently fast, the optimal Korobov lattice rule has an error bound of order O(n^{-\alpha/2 +\delta})$ (for arbitrary δ>0), with the implied constant depending at worst polynomially on the dimension. Here α>1 is the smoothness parameter of the weighted Korobov spaces. We generalize the construction to the case where n is a product of arbitrary distinct prime numbers, with the purpose of reducing the construction cost without sacrificing much of the quality of the lattice rules. A corresponding result is deduced for weighted Sobolev spaces of nonperiodic functions, using randomly shifted optimal Korobov lattice rules. A comparison of the worst-case errors for Korobov lattice rules and the recent component-by-component constructions is presented. The investigation establishes the usefulness of (shifted) optimal Korobov lattice rules for integration, even in high dimensions, if the weights which characterize the weighted spaces are suitably chosen.