We study integration and L2-approximation of functions of infinitely many variables in the following setting: The underlying function space is the countably infinite tensor product of univariate Hermite spaces and the probability measure is the corresponding product of the standard normal distribution. The maximal domain of the functions from this tensor product space is necessarily a proper subset of the sequence space RN. We establish upper and lower bounds for the minimal worst case errors under general assumptions; these bounds do match for tensor products of well-studied Hermite spaces of functions with finite or with infinite smoothness. In the proofs we employ embedding results, and the upper bounds are attained constructively with the help of multivariate decomposition methods.
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.
We prove lower bounds on the worst-case error of numerical integration in tensor product spaces. The information complexity is the minimal number N of function evaluations that is necessary such that the N -th minimal error is less than a factor ε times the initial error, i.e., the error for N = 0 , where ε belongs to ( 0 , 1 ) . We are interested to which extent the information complexity depends on the number d of variables of the integrands. If the information complexity grows exponentially fast in d , then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem, we present two methods for providing lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function and can be seen as a generalization of the method of decomposable reproducing kernels. The second method, although only applicable for positive quadrature rules, does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. Several applications of both methods are presented.
We study the numerical integration problem for functions with infinitely many variables which stem from a weighted reproducing kernel Hilbert space. We study the worst case ε \varepsilon -complexity which is defined as the minimal cost among all algorithms whose worst case error over the Hilbert space unit ball is at most ε \varepsilon . Here we assume that the cost of evaluating a function depends polynomially on the number of active variables. The infinite-dimensional integration problem is tractable if the ε \varepsilon -complexity is bounded by a constant times a power of 1 / ε 1/\varepsilon . The smallest such power is called the exponent of tractability. We provide improved lower bounds for the exponent of tractability for general finite-order weights and, with the help of multilevel algorithms, improved upper bounds for three newly defined classes of finite-order weights. The newly defined finite-intersection weights model the situation where each group of variables interacts with at most ρ \rho other groups of variables, ρ \rho some fixed number. For these weights we obtain sharp upper bounds for any decay of the weights and any polynomial degree of the cost function. For the other two classes of finite-order weights our upper bounds are sharp if, e.g., the decay of the weights is fast or slow enough. Furthermore, we deduce a lower bound for the exponent of tractability for arbitrary weights and a constructive upper bound for product weights.
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.