ISSN 1088-6842(online) ISSN 0025-5718(print)

On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation

Authors: Michael Griebel and Henryk Wozniakowski
Journal: Math. Comp. 75 (2006), 1259-1286
MSC (2000): Primary 65D30, 65D15, 41A45
DOI: https://doi.org/10.1090/S0025-5718-06-01865-5
Published electronically: May 1, 2006
MathSciNet review: 2219028
Full-text PDF

Abstract: We study the maximal rate of convergence (mrc) of algorithms for (multivariate) integration and approximation of -variate functions from reproducing kernel Hilbert spaces . Here is an arbitrary kernel all of whose partial derivatives up to order satisfy a Hölder-type condition with exponent . Algorithms use function values and we analyze their rate of convergence as tends to infinity. We focus on universal algorithms which depend on , , and but not on the specific kernel , and nonuniversal algorithms which may depend additionally on .

For universal algorithms the mrc is for both integration and approximation, and for nonuniversal algorithms it is for integration and with for approximation. Hence, the mrc for universal algorithms suffers from the curse of dimensionality if is large relative to , whereas the mrc for nonuniversal algorithms does not since it is always at least for integration, and for approximation. This is the price we have to pay for using universal algorithms. On the other hand, if is large relative to , then the mrc for universal and nonuniversal algorithms is approximately the same.

We also consider the case when we have the additional knowledge that the kernel has product structure, . Here are some univariate kernels whose all derivatives up to order satisfy a Hölder-type condition with exponent . Then the mrc for universal algorithms is for both integration and approximation, and for nonuniversal algorithms it is for integration and with for approximation. If or for all , then the mrc is at least , and the curse of dimensionality is not present. Hence, the product form of reproducing kernels breaks the curse of dimensionality even for universal algorithms.

References [Enhancements On Off] (What's this?)

Retrieve articles in Mathematics of Computation with MSC (2000): 65D30, 65D15, 41A45

Retrieve articles in all journals with MSC (2000): 65D30, 65D15, 41A45

Michael Griebel
Affiliation: Institut für Numerische Simulation, Universität Bonn, Wegelerstrasse 6, D-53113 Bonn, Germany
Email: griebel@ins.uni-bonn.de

Henryk Wozniakowski
Affiliation: Department of Computer Science, Columbia University, New York, NY 10027, USA; and Institute of Applied Mathematics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland
Email: henryk@cs.columbia.edu

DOI: https://doi.org/10.1090/S0025-5718-06-01865-5
Received by editor(s): July 25, 2005
Received by editor(s) in revised form: August 15, 2005
Published electronically: May 1, 2006
Additional Notes: The research of the first author was supported in part by the Sonderforschungsbereich 611 Singuläre Phänomene und Skalierung in Mathematischen Modellen sponsored by the Deutsche Forschungsgemeinschaft.
The research of the second author was supported in part by the National Science Foundation.