Abstract We study the $$L_2$$ L 2 -approximation of functions from a Hilbert space and compare the sampling numbers with the approximation numbers. The sampling number $$e_n$$ e n is the minimal worst-case error that can be achieved with n function values, whereas the approximation number $$a_n$$ a n is the minimal worst-case error that can be achieved with n pieces of arbitrary linear information (like derivatives or Fourier coefficients). We show that $$\begin{aligned} e_n \,\lesssim \, \sqrt{\frac{1}{k_n} \sum _{j\ge k_n} a_j^2}, \end{aligned}$$ e n ≲ 1 k n ∑ j ≥ k n a j 2 , where $$k_n \asymp n/\log (n)$$ k n ≍ n / log ( n ) . This proves that the sampling numbers decay with the same polynomial rate as the approximation numbers and therefore that function values are basically as powerful as arbitrary linear information if the approximation numbers are square-summable. Our result applies, in particular, to Sobolev spaces $$H^s_\mathrm{mix}(\mathbb {T}^d)$$ H mix s ( T d ) with dominating mixed smoothness $$s>1/2$$ s > 1 / 2 and dimension $$d\in \mathbb {N}$$ d ∈ N , and we obtain $$\begin{aligned} e_n \,\lesssim \, n^{-s} \log ^{sd}(n). \end{aligned}$$ e n ≲ n <mm
Abstract We study the L2 L 2 -approximation of functions from a Hilbert space and compare the sampling numbers with the approximation numbers. The sampling number en e n is the minimal worst-case error that can be achieved with n function values, whereas the approximation number an a n is the minimal worst-case error that can be achieved with n pieces of arbitrary linear information (like derivatives or Fourier coefficients). We show that en≲kn1j≥kn∑aj2, e n ≲ 1 k n ∑ j ≥ k n a j 2 , where kn≍n/log(n) k n ≍ n / log ( n ) . This proves that the sampling numbers decay with the same polynomial rate as the approximation numbers and therefore that function values are basically as powerful as arbitrary linear information if the approximation numbers are square-summable. Our result applies, in particular, to Sobolev spaces Hmixs(Td) H mix s ( T d ) with dominating mixed smoothness s>1/2 s > 1 / 2 and dimension d∈N d ∈ N , and we obtain en≲n−slogsd(n). e n ≲ n <mm
On L2-approximation in Hilbert spaces using function values
We study L2-approximation of functions from Hilbert spaces H in which
function evaluation is a continuous linear functional, using function values as
information. Under certain assumptions on H, we prove that the n-th minimal
worst-case error en satisfies en≲an/log(n), where
an is the n-th minimal worst-case error for algorithms using arbitrary
linear information, i.e., the n-th approximation number. Our result applies,
in particular, to Sobolev spaces with dominating mixed smoothness H=Hmixs(Td) with s>1/2 and we obtain en≲n−slogsd(n). This improves upon previous bounds whenever d>2s+1.
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\}.$$
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 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.
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.
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.