We study $L_2$-approximation problems $\text{APP}_d$ 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,\text{APP}_d)$ 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,\text{APP}_d)$ converges to zero polynomially fast with increasing $n$. We recall the notions of polynomial, strongly polynomial, weak and $(t_1,t_2)$-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\}.$$
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 Hd,\a,\ga with parameter sequences \ga={\gaj} and \a={\azj} of positive real numbers 1≥\ga1≥\ga2≥⋯≥0 and 21<\az1≤\az2≤⋯. 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 \ga and \a for strongly polynomial tractability or polynomial tractability is \dz:=liminfj→∞lnjln\gaj−1>0, and the exponent of strongly polynomial tractability is pstr=2max{\dz1,2\az11}.
This paper is devoted to the study of tractability of the $ L_2 $-approximation and integration from weighted Korobov spaces of increasing smoothness in the worst-case setting. The considered algorithms use information from the class $ \Lambda^{\rm all} $, including all continuous linear functionals, and from the class $ \Lambda^{\rm std} $, including function evaluations. Necessary and sufficient conditions on the weights of the function space for strong polynomial tractability, polynomial tractability, quasi-polynomial tractability, uniform weak tractability, weak tractability and $ (\sigma, \tau) $-weak tractability, are provided. Our results give a comprehensive picture of the weight conditions for all standard notions of algebraic tractability. It may be helpful to study the tractability of nonhomogeneous tensor product spaces.
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.
L∞-approximation in Korobov spaces with Exponential Weights
We study multivariate L∞-approximation for a weighted Korobov space of 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 positive real numbers bounded away from zero. We study the minimal worst-case error eL∞−app,Λ(n,s) of all algorithms that use n information evaluations from a class Λ in the s-variate case. We consider two classes Λ in this paper: the class Λall of all linear functionals and the class Λstd of only function evaluations. We study exponential convergence of the minimal worst-case error, which means that eL∞−app,Λ(n,s) converges to zero exponentially fast with increasing n. Furthermore, we consider how the error depends on the dimension s. To this end, we define the notions of κ-EC-weak, EC-polynomial and EC-strong polynomial tractability, where EC stands for "exponential convergence". In particular, EC-polynomial tractability means that we need a polynomial number of information evaluations in s and 1+logε−1 to compute an ε-approximation. We derive necessary and sufficient conditions on the sequences a and b for obtaining exponential error convergence, and also for obtaining the various notions of tractability. The results are the same for both classes Λ.
Tractability of L2-approximation in hybrid function spaces
We consider multivariate L2-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d) of all algorithms that use N information evaluations from the class Λ in the d-dimensional case. The two classes Λ considered in this paper are the class Λall consisting of all linear functionals and the class Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d) on the dimension d. The main results are conditions for weak, polynomial, and strong polynomial tractability.
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.
Tractability of L2-approximation in hybrid function spaces
We consider multivariate L2-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d) of all algorithms that use N information evaluations from the class Λ in the d-dimensional case. The two classes Λ considered in this paper are the class Λall consisting of all linear functionals and the class Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d) on the dimension d. The main results are conditions for weak, polynomial, and strong polynomial tractability.