Abstract
We study worst-case optimal approximation of positive linear functionals in reproducing kernel Hilbert spaces induced by increasingly flat Gaussian kernels. This provides a new perspective and some generalisations to the problem of interpolation with increasingly flat radial basis functions. When the evaluation points are fixed and unisolvent, we show that the worst-case optimal method converges to a polynomial method. In an additional one-dimensional extension, we allow also the points to be selected optimally and show that in this case convergence is to the unique Gaussian quadrature–type method that achieves the maximal polynomial degree of exactness. The proofs are based on an explicit characterisation of the reproducing kernel Hilbert space of the Gaussian kernel in terms of exponentially damped polynomials.
Article PDF
Similar content being viewed by others
References
Barrar, R. B., Loeb, H. L., Werner, H.: On the existence of optimal integration formulas for analytic functions. Numer. Math. 23(2), 105–117 (1974)
Barrow, D. L.: On multiple node Gaussian quadrature formulae. Math. Comput. 32(142), 431–439 (1978)
Bojanov, B. D.: On the existence of optimal quadrature formulae for smooth functions. Calcolo 16(1), 61–70 (1979)
Braess, D., Dyn, N.: On the uniqueness of monosplines and perfect splines of least L1- and L2-norm. J. d’Analyse Math. 41(1), 217–233 (1982)
Cavoretto, R., Fasshauer, G. E., McCourt, M.: An introduction to the Hilbert-Schmidt SVD using iterated Brownian bridge kernels. Num. Algorithms 68 (2), 393–422 (2015)
de Boor, C.: Polynomial interpolation in several variables. In: Rice, J., DeMillo, R.A. (eds.) Studies in Computer Science, pp 87–109 (1994)
de Boor, C., Ron, A.: The least solution for the polynomial interpolation problem. Math. Z. 210(1), 347–378 (1992)
De Marchi, S., Schaback, R.: Nonstandard kernels and their applications. Dolomites Research Notes on Approximation 2(1), 16–43 (2009)
Dick, J.: A Taylor space for multivariate integration. Monte Carlo Methods Appl. 12(2), 99–112 (2006)
Driscoll, T. A., Fornberg, B.: Interpolation in the limit of increasingly flat radial basis functions. Comput. Math. Appl. 43(3–5), 413–422 (2002)
Fasshauer, G., McCourt, M.: Kernel-based Approximation Methods Using MATLAB. Number 19 in Interdisciplinary Mathematical Sciences. World Scientific Publishing (2015)
Fasshauer, G. E., McCourt, M. J.: Stable evaluation of Gaussian radial basis function interpolants. SIAM J. Sci. Comput. 34(2), A737–A762 (2012)
Fornberg, B., Wright, G., Larsson, E.: Some observations regarding interpolants in the limit of flat radial basis functions. Comput. Math. Appl. 47(1), 37–55 (Jan 2004)
Fornberg, B., Lehto, E., Powell, C.: Stable calculation of Gaussian-based RBF-FD stencils. Comput. Math. Appl. 65(4), 627–637 (2013)
Gautschi, W.: Orthogonal Polynomials: Computation and Approximation. Numerical mathematics and scientific computation. Oxford University Press, Oxford (2004)
Karlin, S.: Tchebycheff Systems: With Applications in Analysis and Statistics. Interscience Publishers, New York (1966)
Karvonen, T., Särkkä, S.: Gaussian kernel quadrature at scaled Gauss–Hermite nodes. BIT Numer. Math. 59(4), 877–902 (2019)
Larkin, F. M.: Optimal approximation in Hilbert spaces with reproducing kernel functions. Math. Comput. 24(112), 911–921 (1970)
Larsson, E., Fornberg, B.: Theoretical and computational aspects of multivariate interpolation with increasingly flat radial basis functions. Comput. Math. Appl. 49 (1), 103–130 (2005)
Lee, Y. J., Yoon, G. J., Yoon, J.: Convergence of increasingly flat radial basis interpolants to polynomial interpolants. SIAM J. Math. Anal. 39(2), 537–553 (2007)
Lee, Y. J., Micchelli, C. A., Yoon, J.: On convergence of flat multivariate interpolation by translation kernels with finite smoothness. Constr. Approx. 40(1), 37–60 (2014)
Lee, Y. J., Micchelli, C. A., Yoon, J.: A study on multivariate interpolation by increasingly flat kernel functions. J. Math. Anal. Appl. 427(1), 74–87 (2015)
Minh, H. Q.: Some properties of Gaussian reproducing kernel Hilbert spaces and their implications for function approximation and learning theory. Constr. Approx. 32(2), 307–338 (2010)
Minka, T.: Deriving quadrature rules from Gaussian processes. Technical report, Statistics Department, Carnegie Mellon University (2000)
Oettershagen, J.: Construction of Optimal Cubature Algorithms with Applications to Econometrics and Uncertainty Quantification. PhD thesis. Institut für Numerische Simulation, Universität Bonn (2017)
O’Hagan, A.: Bayes–Hermite quadrature. J. Stat. Plan. Inference 29(3), 245–260 (1991)
Rasmussen, C. E., Williams, C.K.I.: Gaussian Processes for Machine Learning Adaptive Computation and machine learning. MIT Press, Cambridge (2006)
Richter, N.: Properties of minimal integration rules. SIAM J. Numer. Anal. 7 (1), 67–79 (1970)
Richter-Dyn, N.: Properties of minimal integration rules. II. SIAM J. Numer. Anal. 8(3), 497–508 (1971)
Schaback, R.: Comparison of radial basis function interpolants. In: Multivariate approximation: From CAGD to wavelets, pp. 293–305. World Scientific (1993)
Schaback, R.: Multivariate interpolation by polynomials and radial basis functions. Constr. Approx. 21(3), 293–317 (2005)
Schaback, R.: Limit problems for interpolation by analytical radial basis functions. J. Comput. Appl. Math. 212(2), 127–149 (2008)
Song, G., Riddle, J., Fasshauer, G. E., Hickernell, F. J.: Multivariate interpolation with increasingly flat radial basis functions of finite smoothness. Adv. Comput. Math. 36(3), 485–501 (2012)
Särkkä, S., Hartikainen, J., Svensson, L., Sandblom, F.: On the relation between Gaussian process quadratures and sigma-point methods. J. Adv. Inform. Fus. 11(1), 31–46 (2016)
Steinwart, I., Christmann, A.: Support Vector Machines. Information science and statistics. Springer, Berlin (2008)
Steinwart, I., Hush, D., Scovel, C.: An explicit description of the reproducing kernel Hilbert spaces of Gaussian RBF kernels. IEEE Trans. Inf. Theory 52(10), 4635–4643 (2006)
Wendland, H.: Scattered Data Dpproximation. Number 17 in Cambridge monographs on applied and computational mathematics. Cambridge University Press, Cambridge (2005)
Wright, G. B., Fornberg, B.: Stable computations with flat radial basis functions using vector-valued rational approximations. J. Comput. Phys. 331, 137–156 (2017)
Zwicknagl, B.: Power series kernels. Constr. Approx. 29(1), 61–84 (2009)
Zwicknagl, B., Schaback, R.: Interpolation and approximation in Taylor spaces. J. Approx. Theory 171, 65–83 (2013)
Acknowledgements
We thank the reviewers for numerous comments that helped in improving the presentation.
Funding
Open access funding provided by Aalto University. This work was supported by the Aalto ELEC Doctoral School and the Academy of Finland.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: Robert Schaback
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Karvonen, T., Särkkä, S. Worst-case optimal approximation with increasingly flat Gaussian kernels. Adv Comput Math 46, 21 (2020). https://doi.org/10.1007/s10444-020-09767-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10444-020-09767-1