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 L 2 error, while retaining the same tractability property.
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 L 2 error, while retaining the same tractability property.
We propose a randomized lattice algorithm for approximating multivariate periodic functions over the d -dimensional unit cube from the weighted Korobov space with mixed smoothness α > 1 / 2 and product weights γ 1 , γ 2 , … ∈ [ 0 , 1 ] . Building upon the deterministic lattice algorithm by Kuo et al. (2006), we incorporate a randomized quadrature rule by Dick et al. (2022) to accelerate the convergence rate. This randomization involves drawing the number of points for function evaluations randomly, and selecting a good generating vector for rank-1 lattice points using the randomized component-by-component algorithm. We prove that our randomized algorithm achieves a worst-case root mean squared L 2 -approximation error of order ɛ M − α ( 2 α + 1 ) / ( 4 α + 1 ) + ɛ for an arbitrarily small ɛ ɛ > 0 , where M denotes the maximum number of function evaluations, and that the error bound is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 / α < ∞ . Our upper bound converges faster than a lower bound on the worst-case L 2 -approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid et al. (2017). We also show a lower error bound of order M − α / 2 − 1 / 2 for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.
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.
L2-Approximation Using Median Lattice Algorithms
Abstract In this paper, we study the problem of multivariate L2 L 2 -approximation of functions belonging to a weighted Korobov space. We propose and analyze a median lattice-based algorithm, inspired by median integration rules, which have attracted significant attention in the theory of quasi-Monte Carlo methods. Our algorithm approximates the Fourier coefficients associated with a suitably chosen frequency index set, where each coefficient is estimated by taking the median over approximations from randomly shifted rank-1 lattice rules with independently chosen generating vectors. We prove that the algorithm achieves, with high probability, a convergence rate of the L2 L 2 -approximation error that is arbitrarily close to optimal with respect to the number of function evaluations. Furthermore, we show that the error bound depends only polynomially on the dimension, or is even independent of the dimension, under certain summability conditions on the weights. Numerical experiments illustrate the performance of the proposed median lattice-based algorithm.
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 α ) < ∞ .
Worst case tractability of L2-approximation for weighted Korobov spaces
We study L2-approximation problems APPd in the worst case setting in the weighted Korobov spaces $H_{d,\a,{\bm \ga}}$ with parameter sequences ${\bm \ga}=\{\ga_j\}$ and $\a=\{\az_j\}$ of positive real numbers $1\ge \ga_1\ge \ga_2\ge \cdots\ge 0$ and $\frac1 2<\az_1\le \az_2\le \cdots$. We consider the minimal worst case error e(n,APPd) of algorithms that use n arbitrary continuous linear functionals with d variables. We study polynomial convergence of the minimal worst case error, which means that e(n,APPd) converges to zero polynomially fast with increasing n. We recall the notions of polynomial, strongly polynomial, weak and (t1,t2)-weak tractability. In particular, polynomial tractability means that we need a polynomial number of arbitrary continuous linear functionals in d and $\va^{-1}$ with the accuracy $\va$ of the approximation. We obtain that the matching necessary and sufficient condition on the sequences ${\bm \ga}$ and $\a$ for strongly polynomial tractability or polynomial tractability is $$\dz:=\liminf_{j\to\infty}\frac{\ln \ga_j^{-1}}{\ln j}>0,$$ and the exponent of strongly polynomial tractability is $$p^{\text{str}}=2\max\big\{\frac 1 \dz, \frac 1 {2\az_1}\big\}.$$
We study numerical integration for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. In particular, we are interested in how the error depends on the dimension d. Many recent papers deal with this problem or similar problems and provide matching necessary and sufficient conditions for various notions of tractability. In most cases even simple algorithms are known which allow to achieve these notions of tractability. However, there is a gap in the literature: while for the notion of exponential-weak tractability one knows matching necessary and sufficient conditions, so far no explicit algorithm has been known which yields the desired result. In this paper we close this gap and prove that Korobov lattice rules are suitable algorithms in order to achieve exponential-weak tractability for integration in weighted Korobov spaces of analytic periodic functions.