Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

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?)

  • [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.
  • [2] Alain Berlinet and Christine Thomas-Agnan, Reproducing Kernel Hilbert Spaces in Probability and Statistics, with a preface by Persi Diaconis, Kluwer Academic Publishers, Boston, MA, 2004. MR 2239907
  • [3] 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
  • [4] Felipe Cucker and Ding-Xuan Zhou, Learning Theory: An Approximation Theory Viewpoint, with a foreword by Stephen Smale, Cambridge Monographs on Applied and Computational Mathematics, vol. 24, Cambridge University Press, Cambridge, 2007. MR 2354721
  • [5] 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, https://doi.org/10.1090/S0025-5718-2010-02433-0
  • [6] 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, https://doi.org/10.1016/j.jco.2013.05.001
  • [7] 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
  • [8] 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, https://doi.org/10.1007/978-3-642-27440-4_16
  • [9] 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, https://doi.org/10.1137/10080138X
  • [10] Ervin Feldheim, Relations entre les polynomes de Jacobi, Laguerre et Hermite, Acta Math. 75 (1943), 117-138 (French). MR 0012724
  • [11] A. I. J. Forrester, A. Sóbester, and A. J. Keane, Engineering Design via Surrogate Modelling: A Practical Guide, Wiley, Chichester, 2008.
  • [12] Trevor Hastie, Robert Tibshirani, and Jerome Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, 2nd ed., Springer Series in Statistics, Springer, New York, 2009. MR 2722294
  • [13] 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
  • [14] 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, https://doi.org/10.1016/j.jco.2014.08.004
  • [15] 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, https://doi.org/10.1090/S0025-5718-2013-02739-1
  • [16] 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
  • [17] 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, https://doi.org/10.1007/s10543-011-0358-9
  • [18] 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
  • [19] 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
  • [20] 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
  • [21] Anargyros Papageorgiou and Iasonas Petras, A new criterion for tractability of multivariate problems, J. Complexity 30 (2014), no. 5, 604-619. MR 3239269, https://doi.org/10.1016/j.jco.2014.03.001
  • [22] 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
  • [23] Robert Schaback and Holger Wendland, Kernel techniques: from machine learning to meshless methods, Acta Numer. 15 (2006), 543-639. MR 2269747, https://doi.org/10.1017/S0962492906270016
  • [24] B. Schölkopf and A. J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, Massachusetts, 2002.
  • [25] 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, https://doi.org/10.1016/j.jat.2015.07.007
  • [26] I. H. Sloan and H. Woźniakowski, An intractability result for multiple integration, Math. Comp. 66 (1997), no. 219, 1119-1124. MR 1401946, https://doi.org/10.1090/S0025-5718-97-00834-X
  • [27] S. A. Smolyak, On optimal restoration of functions and functionals of them, (in Russian), Candidate Dissertation, Moscow State University, 1965.
  • [28] Michael L. Stein, Interpolation of Spatial Data: Some Theory for Kriging, Springer Series in Statistics, Springer-Verlag, New York, 1999. MR 1697409
  • [29] Ingo Steinwart and Andreas Christmann, Support Vector Machines, Information Science and Statistics, Springer, New York, 2008. MR 2450103
  • [30] 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, https://doi.org/10.1109/TIT.2006.881713
  • [31] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-Based Complexity, with contributions by A. G. Werschulz and T. Boult, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. MR 958691
  • [32] 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
  • [33] G. N. Watson, A note on the polynomials of Hermite and Laguerre, J. London Math. Soc. S1-13, no. 1, 29. MR 1574524, https://doi.org/10.1112/jlms/s1-13.1.29
  • [34] Holger Wendland, Scattered Data Approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 17, Cambridge University Press, Cambridge, 2005. MR 2131724

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

American Mathematical Society