We study multivariate approximation of periodic function in the worst case setting with the error measured in the $L_\infty$ norm. We consider algorithms that use standard information $Λ^{\rm std}$ consisting of function values or general linear information $Λ^{\rm all}$ consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for $Λ^{\rm std}$ and $Λ^{\rm all}$ under the absolute or normalized error criterion, and show that the power of $Λ^{\rm std}$ is the same as the one of $Λ^{\rm all}$ for some notions of algebraic and exponential tractability. Our result can be applied to weighted Korobov spaces and Korobov spaces with exponential weight. This gives a special solution to Open problem 145 as posed by Novak and Woźniakowski (2012).
On the power of standard information for tractability for L∞ approximation of periodic functions in the worst case setting
We study multivariate approximation of periodic function in the worst case setting with the error measured in the L∞ norm. We consider algorithms that use standard information Λstd consisting of function values or general linear information Λall consisting of arbitrary continuous linear functionals. We investigate the equivalences of various notions of algebraic and exponential tractability for Λstd and Λall under the absolute or normalized error criterion, and show that the power of Λstd is the same as the one of Λall for some notions of algebraic and exponential tractability. Our result can be applied to weighted Korobov spaces and Korobov spaces with exponential weight. This gives a special solution to Open problem 145 as posed by Novak and Woźniakowski (2012).
On the power of standard information for tractability for L2-approximation in the randomized setting
We study approximation of multivariate functions from a separable Hilbert space in the randomized setting with the error measured in the weighted L2 norm. We consider algorithms that use standard information Λstd consisting of function values or general linear information Λall consisting of arbitrary linear functionals. We use the weighted least squares regression algorithm to obtain the upper estimates of the minimal randomized error using Λstd. We investigate the equivalences of various notions of algebraic and exponential tractability for Λstd and Λall for the normalized or absolute error criterion. We show that in the randomized setting for the normalized or absolute error criterion, the power of Λstd is the same as that of Λall for all notions of exponential and algebraic tractability without any condition. Specifically, we solve four Open Problems 98, 100-102 as posed by E.Novak and H.Woźniakowski in the book: Tractability of Multivariate Problems, Volume III: Standard Information for Operators, EMS Tracts in Mathematics, Zürich, 2012.
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 Λ.
We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted L2-norm. We consider functions with an arbitrarily large number of variables, d, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the nth minimal errors, i.e., of the minimal errors among all algorithms using n function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor ε is polynomial in ε−1 (strong tractability), and polynomial in d and ε−1 (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of d, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.
A note about EC-(s,t)-weak tractability of multivariate approximation with analytic Korobov kernels
This note is devoted to discussing multivariate approximation of continuous functions on [0,1]d with analytic Korobov kernels in the worst and average case settings. We only consider algorithms that use finitely many evaluations of arbitrary continuous linear functionals. We study EC-(s,t)-weak tractability under the absolute or normalized error criterion, and obtain necessary and sufficient conditions for 0<min(s,t)<1 and max(s,t)≤1 in the worst case setting and for s,t>0 in the average case setting.
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.
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.