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$.
- 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
- 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
- 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
- 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 https://doi.org/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 https://doi.org/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
- 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 https://doi.org/10.1007/978-3-642-27440-4_16
- 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 https://doi.org/10.1137/10080138X
- Ervin Feldheim, Relations entre les polynomes de Jacobi, Laguerre et Hermite, Acta Math. 75 (1943), 117–138 (French). MR 12724, DOI https://doi.org/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
- F. B. Hildebrand, Introduction to numerical analysis, 2nd ed., McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. International Series in Pure and Applied Mathematics. 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 https://doi.org/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 https://doi.org/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 https://doi.org/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
- 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
- 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
- Anargyros Papageorgiou and Iasonas Petras, A new criterion for tractability of multivariate problems, J. Complexity 30 (2014), no. 5, 604–619. MR 3239269, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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
- 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 https://doi.org/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
- 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 https://doi.org/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
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
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
Article copyright:
© Copyright 2016
American Mathematical Society