Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 

 

Multivariate integration for analytic functions with Gaussian kernels


Authors: Frances Y. Kuo, Ian H. Sloan and Henryk Woźniakowski
Journal: Math. Comp. 86 (2017), 829-853
MSC (2010): Primary 41A63, 41A99; Secondary 65D30
DOI: https://doi.org/10.1090/mcom/3144
Published electronically: June 29, 2016
MathSciNet review: 3584550
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study multivariate integration of analytic functions defined on  $ \mathbb{R}^d$. These functions are assumed to belong to a reproducing kernel Hilbert space whose kernel is Gaussian, with nonincreasing shape parameters. We prove that a tensor product algorithm based on the univariate Gauss-Hermite quadrature rules enjoys exponential convergence and computes an $ \varepsilon $-approximation for the $ d$-variate integration using an order of $ (\ln \,\varepsilon ^{-1})^d$ function values as $ \varepsilon $ goes to zero. We prove that the exponent $ d$ is sharp by proving a lower bound on the minimal (worst case) error of any algorithm based on finitely many function values. We also consider four notions of tractability describing how the minimal number $ n(\varepsilon ,d)$ of function values needed to find an $ \varepsilon $-approximation in the $ d$-variate case behaves as a function of $ d$ and $ \ln \,\varepsilon ^{-1}$. One of these notions is new. In particular, we prove that for all positive shape parameters, the minimal number $ n(\varepsilon ,d)$ is larger than any polynomial in $ d$ and $ \ln \,\varepsilon ^{-1}$ as $ d$ and $ \varepsilon ^{-1}$ go to infinity. However, it is not exponential in $ d^{\,t}$ and $ \ln \,\varepsilon ^{-1}$ whenever $ t>1$.


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


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 41A63, 41A99, 65D30

Retrieve articles in all journals with MSC (2010): 41A63, 41A99, 65D30


Additional Information

Frances Y. Kuo
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, New South Wales 2052, Australia
Email: f.kuo@unsw.edu.au

Ian H. Sloan
Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, New South Wales 2052, Australia
Email: i.sloan@unsw.edu.au

Henryk Woźniakowski
Affiliation: Department of Computer Science, Columbia University, New York, New York 10027 – 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/mcom/3144
Received by editor(s): October 9, 2014
Received by editor(s) in revised form: August 5, 2015
Published electronically: June 29, 2016
Article copyright: © Copyright 2016 American Mathematical Society