## Multivariate integration for analytic functions with Gaussian kernels

HTML articles powered by AMS MathViewer

- by Frances Y. Kuo, Ian H. Sloan and Henryk Woźniakowski PDF
- Math. Comp.
**86**(2017), 829-853 Request permission

## 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

- N. S. Bakhvalov,
*On the optimality of linear methods for operator approximations in convex classes of functions*, USSR Comp. Math. Mech. Phys.**11**(1971), 244–249. - Alain Berlinet and Christine Thomas-Agnan,
*Reproducing kernel Hilbert spaces in probability and statistics*, Kluwer Academic Publishers, Boston, MA, 2004. With a preface by Persi Diaconis. MR**2239907**, DOI 10.1007/978-1-4419-9096-9 - M. D. Buhmann,
*Radial basis functions: theory and implementations*, Cambridge Monographs on Applied and Computational Mathematics, vol. 12, Cambridge University Press, Cambridge, 2003. MR**1997878**, DOI 10.1017/CBO9780511543241 - Felipe Cucker and Ding-Xuan Zhou,
*Learning theory: an approximation theory viewpoint*, Cambridge Monographs on Applied and Computational Mathematics, vol. 24, Cambridge University Press, Cambridge, 2007. With a foreword by Stephen Smale. MR**2354721**, DOI 10.1017/CBO9780511618796 - Josef Dick, Gerhard Larcher, Friedrich Pillichshammer, and Henryk Woźniakowski,
*Exponential convergence and tractability of multivariate integration for Korobov spaces*, Math. Comp.**80**(2011), no. 274, 905–930. MR**2772101**, DOI 10.1090/S0025-5718-2010-02433-0 - Josef Dick, Peter Kritzer, Friedrich Pillichshammer, and Henryk Woźniakowski,
*Approximation of analytic functions in Korobov spaces*, J. Complexity**30**(2014), no. 2, 2–28. MR**3166518**, DOI 10.1016/j.jco.2013.05.001 - Gregory E. Fasshauer,
*Meshfree approximation methods with MATLAB*, Interdisciplinary Mathematical Sciences, vol. 6, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2007. With 1 CD-ROM (Windows, Macintosh and UNIX). MR**2357267**, DOI 10.1142/6437 - G. E. Fasshauer, F. J. Hickernell, and H. Woźniakowski,
*Average case approximation: convergence and tractability of Gaussian kernels*, Monte Carlo and quasi-Monte Carlo methods 2010, Springer Proc. Math. Stat., vol. 23, Springer, Heidelberg, 2012, pp. 329–344. MR**3173842**, DOI 10.1007/978-3-642-27440-4_{1}6 - Gregory E. Fasshauer, Fred J. Hickernell, and Henryk Woźniakowski,
*On dimension-independent rates of convergence for function approximation with Gaussian kernels*, SIAM J. Numer. Anal.**50**(2012), no. 1, 247–271. MR**2888312**, DOI 10.1137/10080138X - Ervin Feldheim,
*Relations entre les polynomes de Jacobi, Laguerre et Hermite*, Acta Math.**75**(1943), 117–138 (French). MR**12724**, DOI 10.1007/BF02404102 - A. I. J. Forrester, A. Sóbester, and A. J. Keane,
*Engineering Design via Surrogate Modelling: A Practical Guide*, Wiley, Chichester, 2008. - Trevor Hastie, Robert Tibshirani, and Jerome Friedman,
*The elements of statistical learning*, 2nd ed., Springer Series in Statistics, Springer, New York, 2009. Data mining, inference, and prediction. MR**2722294**, DOI 10.1007/978-0-387-84858-7 - F. B. Hildebrand,
*Introduction to numerical analysis*, 2nd ed., International Series in Pure and Applied Mathematics, McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. MR**0347033** - Christian Irrgeher, Peter Kritzer, Gunther Leobacher, and Friedrich Pillichshammer,
*Integration in Hermite spaces of analytic functions*, J. Complexity**31**(2015), no. 3, 380–404. MR**3325680**, DOI 10.1016/j.jco.2014.08.004 - Peter Kritzer, Friedrich Pillichshammer, and Henryk Woźniakowski,
*Multivariate integration of infinitely many times differentiable functions in weighted Korobov spaces*, Math. Comp.**83**(2014), no. 287, 1189–1206. MR**3167455**, DOI 10.1090/S0025-5718-2013-02739-1 - Peter Kritzer, Friedrich Pillichshammer, and Henryk Woźniakowski,
*Tractability of multivariate analytic problems*, Uniform distribution and quasi-Monte Carlo methods, Radon Ser. Comput. Appl. Math., vol. 15, De Gruyter, Berlin, 2014, pp. 147–170. MR**3287364** - Frances Y. Kuo and Henryk Woźniakowski,
*Gauss-Hermite quadratures for functions from Hilbert spaces with Gaussian reproducing kernels*, BIT**52**(2012), no. 2, 425–436. MR**2931357**, DOI 10.1007/s10543-011-0358-9 - Erich Novak and Henryk Woźniakowski,
*Tractability of multivariate problems. Vol. 1: Linear information*, EMS Tracts in Mathematics, vol. 6, European Mathematical Society (EMS), Zürich, 2008. MR**2455266**, DOI 10.4171/026 - Erich Novak and Henryk Woźniakowski,
*Tractability of multivariate problems. Volume II: Standard information for functionals*, EMS Tracts in Mathematics, vol. 12, European Mathematical Society (EMS), Zürich, 2010. MR**2676032**, DOI 10.4171/084 - Erich Novak and Henryk Woźniakowski,
*Tractability of multivariate problems. Volume III: Standard information for operators*, EMS Tracts in Mathematics, vol. 18, European Mathematical Society (EMS), Zürich, 2012. MR**2987170**, DOI 10.4171/116 - Anargyros Papageorgiou and Iasonas Petras,
*A new criterion for tractability of multivariate problems*, J. Complexity**30**(2014), no. 5, 604–619. MR**3239269**, DOI 10.1016/j.jco.2014.03.001 - Carl Edward Rasmussen and Christopher K. I. Williams,
*Gaussian processes for machine learning*, Adaptive Computation and Machine Learning, MIT Press, Cambridge, MA, 2006. MR**2514435** - Robert Schaback and Holger Wendland,
*Kernel techniques: from machine learning to meshless methods*, Acta Numer.**15**(2006), 543–639. MR**2269747**, DOI 10.1017/S0962492906270016 - B. Schölkopf and A. J. Smola,
*Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond*, MIT Press, Cambridge, Massachusetts, 2002. - PawełSiedlecki and Markus Weimar,
*Notes on $(s,t)$-weak tractability: a refined classification of problems with (sub)exponential information complexity*, J. Approx. Theory**200**(2015), 227–258. MR**3400427**, DOI 10.1016/j.jat.2015.07.007 - I. H. Sloan and H. Woźniakowski,
*An intractability result for multiple integration*, Math. Comp.**66**(1997), no. 219, 1119–1124. MR**1401946**, DOI 10.1090/S0025-5718-97-00834-X - S. A. Smolyak,
*On optimal restoration of functions and functionals of them*, (in Russian), Candidate Dissertation, Moscow State University, 1965. - Michael L. Stein,
*Interpolation of spatial data*, Springer Series in Statistics, Springer-Verlag, New York, 1999. Some theory for Kriging. MR**1697409**, DOI 10.1007/978-1-4612-1494-6 - Ingo Steinwart and Andreas Christmann,
*Support vector machines*, Information Science and Statistics, Springer, New York, 2008. MR**2450103** - Ingo Steinwart, Don Hush, and Clint Scovel,
*An explicit description of the reproducing kernel Hilbert spaces of Gaussian RBF kernels*, IEEE Trans. Inform. Theory**52**(2006), no. 10, 4635–4643. MR**2300845**, DOI 10.1109/TIT.2006.881713 - J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski,
*Information-based complexity*, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR**958691** - Grace Wahba,
*Spline models for observational data*, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1990. MR**1045442**, DOI 10.1137/1.9781611970128 - G. N. Watson,
*A Note on the Polynomials of Hermite and Laguerre*, J. London Math. Soc.**13**(1938), no. 1, 29–32. MR**1574524**, DOI 10.1112/jlms/s1-13.1.29 - Holger Wendland,
*Scattered data approximation*, Cambridge Monographs on Applied and Computational Mathematics, vol. 17, Cambridge University Press, Cambridge, 2005. MR**2131724**

## Additional Information

**Frances Y. Kuo**- Affiliation: School of Mathematics and Statistics, University of New South Wales, Sydney, New South Wales 2052, Australia
- MR Author ID: 703418
- 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
- MR Author ID: 163675
- ORCID: 0000-0003-3769-0538
- 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
- Received by editor(s): October 9, 2014
- Received by editor(s) in revised form: August 5, 2015
- Published electronically: June 29, 2016
- © Copyright 2016 American Mathematical Society
- Journal: Math. Comp.
**86**(2017), 829-853 - MSC (2010): Primary 41A63, 41A99; Secondary 65D30
- DOI: https://doi.org/10.1090/mcom/3144
- MathSciNet review: 3584550