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 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 lower bounds on the worst-case error of numerical integration in tensor product spaces. As reference we use the N-th minimal error of linear rules that use N function values. 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. 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 good lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function. This method can be seen as a generalization of the method of decomposable reproducing kernels, that is often successfully applied when integration in Hilbert spaces with a reproducing kernel is studied. The second method, although only applicable for positive quadrature rules, has the advantage, that it 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. The methods presented can be applied to problems beyond the Hilbert space setting. For demonstration purposes we apply them to several examples, notably to uniform integration over the unit-cube, weighted integration over the whole space, and integration of infinitely smooth functions over the cube. Some of these results have interesting consequences in discrepancy theory.
We study integration and L 2 L^2 -approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the n n -th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.
In this dissertation we study the tractability of the information-based complexity n(ε,d) for d-variate function approximation problems. In the deterministic setting for many unweighted problems the curse of dimensionality holds, that means, for some fixed error tolerance ε>0 the complexity n(ε,d) grows exponentially in d. For integration problems one can usually break the curse with the standard Monte Carlo method. For function approximation problems, however, similar effects of randomization have been unknown so far. The thesis contains results on three more or less stand-alone topics. For an extended five page abstract, see the section "Introduction and Results". Chapter 2 is concerned with lower bounds for the Monte Carlo error for general linear problems via Bernstein numbers. This technique is applied to the L∞-approximation of certain classes of C∞-functions, where it turns out that randomization does not affect the tractability classification of the problem. Chapter 3 studies the L∞-approximation of functions from Hilbert spaces with methods that may use arbitrary linear functionals as information. For certain classes of periodic functions from unweighted periodic tensor product spaces, in particular Korobov spaces, we observe the curse of dimensionality in the deterministic setting, while with randomized methods we achieve polynomial tractability. Chapter 4 deals with the L1-approximation of monotone functions via function values. It is known that this problem suffers from the curse in the deterministic setting. An improved lower bound shows that the problem is still intractable in the randomized setting. However, Monte Carlo breaks the curse, in detail, for any fixed error tolerance ε>0 the complexity n(ε,d) grows exponentially in d only.
Multi- and Infinite-variate Integration and L2-Approximation on Hilbert Spaces with Gaussian Kernels
We study integration and L2-approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the n-th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.
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 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.