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 quasi–Monte Carlo algorithms based on low discrepancy sequences for multivariate integration. We consider the problem of how the minimal number of function evaluations needed to reduce the worst-case error from its initial error by a factor of ε \varepsilon depends on ε − 1 {\varepsilon }^{-1} and the dimension s s . Strong tractability means that it does not depend on s s and is bounded by a polynomial in ε − 1 {\varepsilon }^{-1} . The least possible value of the power of ε − 1 {\varepsilon }^{-1} is called the ε \varepsilon -exponent of strong tractability. Sloan and Woźniakowski established a necessary and sufficient condition of strong tractability in weighted Sobolev spaces, and showed that the ε \varepsilon -exponent of strong tractability is between 1 and 2. However, their proof is not constructive . In this paper we prove in a constructive way that multivariate integration in some weighted Sobolev spaces is strongly tractable with ε \varepsilon -exponent equal to 1, which is the best possible value under a stronger assumption than Sloan and Woźniakowski’s assumption. We show that quasi–Monte Carlo algorithms using Niederreiter’s ( t , s ) (t,s) -sequences and Sobol sequences achieve the optimal convergence order O ( N − 1 + δ ) O(N^{-1+\delta })
In this paper we study multivariate integration for a weighted Korobov space for which the Fourier coefficients of the functions decay exponentially fast. This implies that the functions of this space are infinitely times differentiable. Weights of the Korobov space monitor the influence of each variable and each group of variables. We show that there are numerical integration rules which achieve an exponential convergence of the worst-case integration error. We also investigate the dependence of the worst-case error on the number of variables s s , and show various tractability results under certain conditions on weights of the Korobov space. Tractability means that the dependence on s s is never exponential, and sometimes the dependence on s s is polynomial or there is no dependence on s s at all.
. We propose isotropic probability measures defined on classes of smooth multivariate functions. These provide a natural extension of the classical isotropic Wiener measure to multivariate functions from C 2r . We show that in the corresponding average case setting the minimal errors of algorithms that use n function values are \\Theta \\Gamma n \\Gamma(d+4r+1)=2d \\Delta and \\Theta \\Gamma n \\Gamma(4r+1)=2d \\Delta for the integration and L 2 -approximation problems respectively. Here d is the number of variables of the corresponding class of functions. This means that the minimal average errors depend essentially on the number d of variables. In particular, for d large relative to r, the L 2 -approximation problem is intractable. The integration and L 2 -approximation problems have been recently studied with measures whose covariance kernels are tensor products. The results for these measures and for isotropic measures differ significantly. 1 Introduction We study the integratio...
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.
In this paper, we present some new (in-)tractability results related to the integration problem in subspaces of the Wiener algebra over the d -dimensional unit cube. We show that intractability holds for multivariate integration in the standard Wiener algebra in the deterministic setting, in contrast to polynomial tractability in an unweighted subspace of the Wiener algebra recently shown by Goda (2023). Moreover, we prove that multivariate integration in the subspace of the Wiener algebra introduced by Goda is strongly polynomially tractable if we switch to the randomized setting, where we obtain a better ε -exponent than the one implied by the standard Monte Carlo method . We also identify subspaces in which multivariate integration in the deterministic setting are (strongly) polynomially tractable and we compare these results with the bound which can be obtained via Hoeffding's inequality.