We analyse the worst case error (w.c.e) for approximation of d-variate non-periodic functions belonging to the weighted half-period cosine space. We use the so called "tent-transformation" on rank-1 lattice rules for the same. We briefly present some known results about cubature in these spaces and then present the results for approximation. We will start with the analysis of the approximation operator App:H_d -> L_2 where H_d is the half period cosine space. It can be shown that the w.c.e in these spaces can be related to the w.c.e in the Korobov space.
We analyse the worst case error (w.c.e) for approximation of d-variate non-periodic functions belonging to the weighted half-period cosine space. We use the so called "tent-transformation" on rank-1 lattice rules for the same. We briefly present some known results about cubature in these spaces and then present the results for approximation. We will start with the analysis of the approximation operator App:H_d -> L_2 where H_d is the half period cosine space. It can be shown that the w.c.e in these spaces can be related to the w.c.e in the Korobov space.
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 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.
Numerical integration in log-Korobov and log-cosine spaces
QMC rules are equal weight quadrature rules for approximating integrals over [0,1]s. One line of research studies the integration error of functions in the unit ball of so-called Korobov spaces, which are Hilbert spaces of periodic functions on [0,1]s with square integrable partial mixed derivatives of order α. Using Parseval's identity, this smoothness can be defined for all real numbers α>1/2. This condition is necessary as otherwise the Korobov space contains discontinuous functions for which function evaluation is not well defined. This paper is concerned with more precise endpoint estimates of the integration error using QMC rules for Korobov spaces with α arbitrarily close to 1/2. To obtain such estimates we introduce a log-scale for functions with smoothness close to 1/2, which we call log-Korobov spaces. We show that lattice rules can be used to obtain an integration error of order O(N−1/2(logN)−μ(1−λ)/2) for any 1/μ<λ≤1, where μ>1 is a power in the log-scale. We also consider tractability of numerical integration for weighted Korobov spaces with product weights (γj)j∈N. It is known that if ∑j=1∞γjτ<∞ for some 1/(2α)<τ≤1 one can obtain error bounds which are independent of the dimension. In this paper we give a more refined estimate for the case where τ is close to 1/(2α), namely we show dimension independent error bounds under the condition that ∑j=1∞γjmax{1,logγj−1}μ(1−λ)<∞ for some 1/μ<λ≤1. The essential tool in our analysis is a log-scale Jensen's inequality. The results described above also apply to integration in log-cosine spaces using tent-transformed lattice rules.
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 multivariate L2-approximation for a weighted Korobov space of analytic periodic functions for which the Fourier coefficients decay exponentially fast. The weights are defined, in particular, in terms of two sequences a={aj} and b={bj} of numbers no less than one. Let eL2−app,Λ(n,s) be the minimal worst-case error of all algorithms that use n information functionals from the class Λ in the s-variate case. We consider two classes Λ: the class Λall consists of all linear functionals and the class Λstd consists of only function valuations. We study (EXP) exponential convergence. This means that eL2−app,Λ(n,s)≤C(s)q(n/C1(s))p(s)foralln,s∈N where q∈(0,1), and C,C1,p:N→(0,∞). If we can take p(s)=p>0 for all s then we speak of (UEXP) uniform exponential convergence. We also study EXP and UEXP with (WT) weak, (PT) polynomial and (SPT) strong polynomial tractability. These concepts are defined as follows. Let $n(\e,s)$ be the minimal n for which $e^{L_2-\mathrm{app},Λ}(n,s)\le \e$. Then WT holds iff $\lim_{s+\log\,\e^{-1}\to\infty}(\log n(\e,s))/(s+\log\,\e^{-1})=0$, PT holds iff there are c,τ1,τ2 such that $n(\e,s)\le cs^{τ_1}(1+\log\,\e^{-1})^{τ_2}$ for all s and $\e\in(0,1)$, and finally SPT holds iff the last estimate holds for τ1=0. The infimum of τ2 for which SPT holds is called the exponent τ∗ of SPT. We prove that the results are the same for both classes Λ, and obtain conditions for WT, PT, SPT with and without EXP and UEXP.