Sharp inverse statements for kernel interpolation
HTML articles powered by AMS MathViewer
- by Tizian Wenzel;
- Math. Comp.
- DOI: https://doi.org/10.1090/mcom/4094
- Published electronically: April 9, 2025
- PDF | Request permission
Abstract:
While direct statements for kernel based interpolation on regions $\Omega \subset \mathbb {R}^d$ are well researched, far less is known about corresponding inverse statements. The available inverse statements for kernel based interpolation so far are not sharp.
In this paper, we derive sharp inverse statements for interpolation using finitely smooth kernels, such as popular radial basis function kernels like the class of Matérn or Wendland kernels. In particular, the results show that there is a one-to-one correspondence between the smoothness of a function and its approximation rate via kernel interpolation: If a function can be approximated with a given rate, it has a corresponding smoothness and vice versa.
References
- Mikhail S. Agranovich, Sobolev spaces, their generalizations and elliptic problems in smooth and Lipschitz domains, Springer Monographs in Mathematics, Springer, Cham, 2015. Revised translation of the 2013 Russian original. MR 3287270, DOI 10.1007/978-3-319-14648-5
- Rémi Arcangéli, María Cruz López de Silanes, and Juan José Torrens, An extension of a bound for functions in Sobolev spaces, with applications to $(m,s)$-spline interpolation and smoothing, Numer. Math. 107 (2007), no. 2, 181–211. MR 2328845, DOI 10.1007/s00211-007-0092-z
- Haïm Brezis and Petru Mironescu, Gagliardo-Nirenberg inequalities and non-inequalities: the full story, Ann. Inst. H. Poincaré C Anal. Non Linéaire 35 (2018), no. 5, 1355–1376. MR 3813967, DOI 10.1016/j.anihpc.2017.11.007
- P. L. Butzer and K. Scherer, On the fundamental approximation theorems of D. Jackson, S. N. Bernstein and theorems of M. Zamansky and S. B. Stečkin, Aequationes Math. 3 (1969), 170–185. MR 264301, DOI 10.1007/BF01817511
- Ka Chun Cheung, Leevan Ling, and Robert Schaback, $H^2$-convergence of least-squares kernel collocation methods, SIAM J. Numer. Anal. 56 (2018), no. 1, 614–633. MR 3765911, DOI 10.1137/16M1072863
- Stefano De Marchi, Robert Schaback, and Holger Wendland, Near-optimal data-independent point locations for radial basis function interpolation, Adv. Comput. Math. 23 (2005), no. 3, 317–330. MR 2136543, DOI 10.1007/s10444-004-1829-1
- R. DeVore and F. Richards, Saturation and inverse theorems for spline approximation, Spline functions and approximation theory (Proc. Sympos., Univ. Alberta, Edmonton, Alta., 1972) Internat. Ser. Numer. Math., Vol. 21, Birkhäuser Verlag, Basel-Stuttgart, 1973, pp. 73–82. MR 372491
- Jean Duchon, Sur l’erreur d’interpolation des fonctions de plusieurs variables par les $D^{m}$-splines, RAIRO Anal. Numér. 12 (1978), no. 4, 325–334, vi (French, with English summary). MR 519016, DOI 10.1051/m2an/1978120403251
- 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 and M. J. McCourt, Kernel-Based Approximation Methods Using MATLAB, vol. 19, World Scientific Publishing Company, 2015.
- M. Haas, D. Holzmüller, Ulrike Luxburg, and Ingo Steinwart, Mind the spikes: benign overfitting of kernels and neural networks in fixed dimension, Advances in Neural Information Processing Systems (A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, eds.), vol. 36, Curran Associates, Inc., 2023, pp. 20763–20826.
- T. Hangelbroek, F. J. Narcowich, C. Rieger, and J. D. Ward, An inverse theorem for compact Lipschitz regions in $\Bbb {R}^d$ using localized kernel bases, Math. Comp. 87 (2018), no. 312, 1949–1989. MR 3787398, DOI 10.1090/mcom/3256
- Thomas Hangelbroek, Francis J. Narcowich, Christian Rieger, and Joseph D. Ward, Direct and inverse results on bounded domains for meshless methods via localized bases on manifolds, Contemporary computational mathematics—a celebration of the 80th birthday of Ian Sloan. Vol. 1, 2, Springer, Cham, 2018, pp. 517–543. MR 3822249
- Shao-Bo Lin, Xiangyu Chang, and Xingping Sun, Kernel interpolation of high dimensional scattered data, SIAM J. Numer. Anal. 62 (2024), no. 3, 1098–1118. MR 4741504, DOI 10.1137/22M1519948
- H. N. Mhaskar, F. J. Narcowich, J. Prestin, and J. D. Ward, $L^p$ Bernstein estimates and approximation by spherical basis functions, Math. Comp. 79 (2010), no. 271, 1647–1679. MR 2630006, DOI 10.1090/S0025-5718-09-02322-9
- Davoud Mirzaei, A Petrov-Galerkin kernel approximation on the sphere, SIAM J. Numer. Anal. 56 (2018), no. 1, 274–295. MR 3749386, DOI 10.1137/16M1106626
- S. Müller, Komplexität und stabilität von kernbasierten rekonstruktionsmethoden (Complexity and stability of kernel-based reconstructions), Ph.D. Thesis, Fakultät für Mathematik und Informatik, Georg-August-Universität Göttingen, 2009.
- Francis J. Narcowich, Joseph D. Ward, and Holger Wendland, Sobolev error estimates and a Bernstein inequality for scattered data interpolation via radial basis functions, Constr. Approx. 24 (2006), no. 2, 175–186. MR 2239119, DOI 10.1007/s00365-005-0624-7
- Francis J. Narcowich, Xingping Sun, Joseph D. Ward, and Holger Wendland, Direct and inverse Sobolev error estimates for scattered data interpolation via spherical basis functions, Found. Comput. Math. 7 (2007), no. 3, 369–390. MR 2335250, DOI 10.1007/s10208-005-0197-7
- C. Rieger, Sampling inequalities and applications, Ph.D. Thesis, Universität Göttingen, 2008.
- Christian Rieger and Barbara Zwicknagl, Sampling inequalities for infinitely smooth functions, with applications to interpolation and machine learning, Adv. Comput. Math. 32 (2010), no. 1, 103–129. MR 2574569, DOI 10.1007/s10444-008-9089-0
- Vyacheslav S. Rychkov, On restrictions and extensions of the Besov and Triebel-Lizorkin spaces with respect to Lipschitz domains, J. London Math. Soc. (2) 60 (1999), no. 1, 237–257. MR 1721827, DOI 10.1112/S0024610799007723
- Gabriele Santin, Tizian Wenzel, and Bernard Haasdonk, On the optimality of target-data-dependent kernel greedy interpolation in Sobolev reproducing kernel Hilbert spaces, SIAM J. Numer. Anal. 62 (2024), no. 5, 2249–2275. MR 4798955, DOI 10.1137/23M1587956
- Robert Schaback, Error estimates and condition numbers for radial basis function interpolation, Adv. Comput. Math. 3 (1995), no. 3, 251–264. MR 1325034, DOI 10.1007/BF02432002
- Robert Schaback, Superconvergence of kernel-based interpolation, J. Approx. Theory 235 (2018), 1–19. MR 3845608, DOI 10.1016/j.jat.2018.05.002
- Robert Schaback and Holger Wendland, Inverse and saturation theorems for radial basis function interpolation, Math. Comp. 71 (2002), no. 238, 669–681. MR 1885620, DOI 10.1090/S0025-5718-01-01383-7
- Ingo Steinwart and Andreas Christmann, Support vector machines, Information Science and Statistics, Springer, New York, 2008. MR 2450103
- V. N. Temlyakov, The Marcinkiewicz-type discretization theorems, Constr. Approx. 48 (2018), no. 2, 337–369. MR 3848042, DOI 10.1007/s00365-018-9446-2
- Hans Triebel, Function spaces in Lipschitz domains and on Lipschitz manifolds. Characteristic functions as pointwise multipliers, Rev. Mat. Complut. 15 (2002), no. 2, 475–524. MR 1951822, DOI 10.5209/rev_{R}EMA.2002.v15.n2.16910
- John Paul Ward, $L^p$ Bernstein inequalities and inverse theorems for RBF approximation on $\Bbb R^d$, J. Approx. Theory 164 (2012), no. 12, 1577–1593. MR 3020939, DOI 10.1016/j.jat.2012.09.003
- Holger Wendland, Scattered data approximation, Cambridge Monographs on Applied and Computational Mathematics, vol. 17, Cambridge University Press, Cambridge, 2005. MR 2131724
- Holger Wendland and Christian Rieger, Approximate interpolation with applications to selecting smoothing parameters, Numer. Math. 101 (2005), no. 4, 729–748. MR 2195325, DOI 10.1007/s00211-005-0637-y
- Tizian Wenzel, Gabriele Santin, and Bernard Haasdonk, A novel class of stabilized greedy kernel approximation algorithms: convergence, stability and uniform point distribution, J. Approx. Theory 262 (2021), Paper No. 105508, 30. MR 4191314, DOI 10.1016/j.jat.2020.105508
- Tizian Wenzel, Gabriele Santin, and Bernard Haasdonk, Analysis of target data-dependent greedy kernel algorithms: convergence rates for $f$-, $f\cdot P$-, and $f/P$-greedy, Constr. Approx. 57 (2023), no. 1, 45–74. MR 4543165, DOI 10.1007/s00365-022-09592-3
- T. Wenzel, G. Santin, and B. Haasdonk, Stability of convergence rates: kernel interpolation on non-Lipschitz domains, IMA J. Numer. Anal. 44 (2024), no. 3.
Bibliographic Information
- Tizian Wenzel
- Affiliation: Institute for Applied Analysis and Numerical Simulation, University of Stuttgart, Germany
- Address at time of publication: Department of Mathematics, Ludwig-Maximilians-Universität München, Germany
- MR Author ID: 1413265
- Email: wenzel@math.lmu.de
- Received by editor(s): May 11, 2024
- Received by editor(s) in revised form: December 2, 2024, and March 12, 2025
- Published electronically: April 9, 2025
- Additional Notes: This work was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC 2075 - 390740016 and by the BMBF under contract 05M20VSA as well as supported by from the Studienstiftung des deutschen Volkes (German national Academic Foundation)
- © Copyright 2025 American Mathematical Society
- Journal: Math. Comp.
- MSC (2020): Primary 65D05, 46E22, 41A27, 41A17
- DOI: https://doi.org/10.1090/mcom/4094