Approximation of analytic functions in Korobov spaces

We study multivariate L2L2-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 positive real numbers bounded away from zero. We study the minimal worst-case error eL2−app,Λ(n,s) of all algorithms that use nn information evaluations from the class  ΛΛ in the ss-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 eL2−app,Λ(n,s) converges to zero exponentially fast with increasing nn. Furthermore, we consider how the error depends on the dimension ss. To this end, we define the notions of weak, polynomial and strong polynomial tractability. In particular, polynomial tractability means that we need a polynomial number of information evaluations in ss and 1+logε−11+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 ΛΛ. They are also constructive with the exception of one particular sub-case for which we provide a semi-constructive algorithm.