Adaptive residual subsampling algorithms for kernel interpolation based on cross validation techniques

Abstract

In this article we present an adaptive residual subsampling scheme designed for kernel based interpolation. For an optimal choice of the kernel shape parameter we consider some cross validation (CV) criteria, using efficient algorithms of $k$-fold CV and leave-one-out CV (LOOCV) as a special case. In this framework, the selection of the shape parameter within the residual subsampling method is totally automatic, provides highly reliable and accurate results for any kind of kernel, and guarantees existence and uniqueness of the kernel based interpolant. Numerical results show the performance of this new adaptive scheme, also giving a comparison with other computational techniques.

Keywords

• adaptive interpolation
• meshfree methods
• RBF approximation
• shape parameter optimization
• cross validation schemes

References

1. M. Bozzini, L. Lenarduzzi and R. Schaback: Adaptive interpolation by scaled multiquadrics, Adv. Comput. Math., 16 (2002), 375–387.
2. M. Bozzini, L. Lenarduzzi, M. Rossini and R. Schaback: Interpolation with variably scaled kernels, IMA J. Numer. Anal., 35 (2015), 199–219.
3. M. D. Buhmann: Radial Basis Functions: Theory and Implementation, Cambridge Monogr. Appl. Comput. Math., vol. 12, Cambridge Univ. Press, Cambridge (2003).
4. R. Cavoretto, A. De Rossi, E. Perracchione and E. Venturino: Reliable approximation of separatrix manifolds in competition models with safety niches, Int. J. Comput. Math., 92 (2015), 1826–1837.
5. R. Cavoretto, A. De Rossi: A two-stage adaptive scheme based on RBF collocation for solving elliptic PDEs, Comput. Math. Appl., 79 (2020), 3206–3222.
6. R. Cavoretto, A. De Rossi: Adaptive refinement procedures for meshless RBF unsymmetric and symmetric collocation methods, Appl. Math. Comput., 382 (2020), 125354.
7. R. Cavoretto: Adaptive radial basis function partition of unity interpolation: A bivariate algorithm for unstructured data, J. Sci. Comput., 87 (2021), Article ID: 41.
8. R. Cavoretto, A. De Rossi, M. S. Mukhametzhanov and Y. D. Sergeyev: On the search of the shape parameter in radial basis functions using univariate global optimization methods, J. Global Optim., 79 (2021), 305–327.

9. R. Cavoretto, A. De Rossi and W. Erb: Partition of unity methods for signal processing on graphs, J. Fourier Anal. Appl., 27 (2021), Article ID: 66.
10. R. Cavoretto: Adaptive LOOCV-based kernel methods for solving time-dependent BVPs, Appl. Math. Comput., 429 (2022), Article ID: 127228.
11. R. Cavoretto, A. De Rossi, A. Sommariva and M. Vianello: RBFCUB: A numerical package for near-optimal meshless cubature on general polygons, Appl. Math. Lett., 125 (2022), Article ID: 107704.
12. R. Cavoretto, A. De Rossi: An adaptive residual sub-sampling algorithm for kernel interpolation based on maximum likelihood estimations, J. Comput. Appl. Math., 418 (2023), Article ID: 114658.
13. R. Cavoretto, A. De Rossi and S. Lancellotti: Bayesian approach for radial kernel parameter tuning, J. Comput. Appl. Math., 441 (2024), Article ID: 115716.
14. R. Cavoretto, A. De Rossi, F. Dell’Accio, F. Di Tommaso, N. Siar, A. Sommariva and M. Vianello: Numerical cubature on scattered data by adaptive interpolation, J. Comput. Appl. Math., 444 (2024), Article ID: 115793.
15. R. Cavoretto, A. De Rossi, A. Haider and S. Lancellotti: Comparing deterministic and statistical optimization techniques for the shape parameter selection in RBF interpolation, Dolomites Res. Notes Approx., 17 (2024), 48–55.
16. A. Celisse, S. Robin: Nonparametric density estimation by exact leave-p-out cross-validation, CSDA, 52 (2008), 2350–2368.
17. S. De Marchi: Padua points and fake nodes for polynomial approximation: old, new and open problems, Constr. Math. Anal., 5 (2022), 14–36.
18. T. A. Driscoll, A. R. H. Heryudono, Adaptive residual subsampling methods for radial basis function interpolation and collocation problems, Comput. Math. Appl., 53 (2007), 927–939.
19. G. E. Fasshauer: Meshfree Approximation Methods with MATLAB, Interdisciplinary Mathematical Sciences, vol. 6, World Scientific Publishing Co., Singapore (2007).
20. G. E. Fasshauer: Positive definite kernels: Past, present and future, Dolomites Res. Notes Approx., 4 (2011), 21–63.
21. G. E. Fasshauer, M. J. McCourt: Kernel-based Approximation Methods using MATLAB, Interdisciplinary Mathematical Sciences, Vol. 19, World Scientific Publishing Co., Singapore (2015).
22. G. E. Fasshauer, J. G. Zhang: On choosing “optimal” shape parameters for RBF approximation, Numer. Algorithms, 45 (2007), 345–368.
23. B. Fornberg, J. Zuev: The Runge phenomenon and spatially variable shape parameters in RBF interpolation, Comput. Math. Appl., 54 (2007), 379–398.
24. K. Gao, G. Mei, S. Cuomo, F. Piccialli and N. Xu: ARBF: adaptive radial basis function interpolation algorithm for irregularly scattered point sets, Soft Computing, 24 (2020), 17693–17704.
25. A. Golbabai, E. Mohebianfar and H. Rabiei: On the new variable shape parameter strategies for radial basis functions, Comput. Appl. Math., 34 (2015), 691–704.
26. F. J. Hickernell, Y. C. Hon: Radial basis function approximations as smoothing splines, Appl. Math. Comput., 102 (1999), 1–24.
27. M. Karimnejad Esfahani, S. De Marchi and F. Marchetti: Moving least squares approximation using variably scaled discontinuous weight function, Constr. Math. Anal., 6 (2023), 38–54.
28. L. Lenarduzzi, R. Schaback: Kernel-based adaptive approximation of functions with discontinuities, Appl. Math. Comput., 307 (2017), 113–123.
29. L. Ling, F. Marchetti: A stochastic extended rippa’s algorithm for LpOCV, Appl. Math. Lett., 129 (2022), Article ID: 107955.
30. F. Marchetti: The extension of Rippa’s algorithm beyond LOOCV, Appl. Math. Lett., 120 (2021), Article ID: 107262.
31. MATLAB version: 9.13.0.2553342 (R2022b) Update 9, Natick, Massachusetts, The MathWorks Inc. (2022).
32. A. Noorizadegan, C.-S. Chen, R. Cavoretto and A. De Rossi: Efficient truncated randomized SVD for mesh-free kernel methods, Comput. Math. Appl., 164 (2024), 12–20.
33. A. Noorizadegan, R. Schaback: Introducing the evaluation condition number: A novel assessment of conditioning in radial basis function methods, Eng. Anal. Bound. Elem., 166 (2024), Article ID: 105827.
34. S. Rippa: An algorithm for selecting a good value for the parameter c in radial basis function interpolation, Adv. Comput. Math., 11 (1999), 193–210.
35. R. Schaback: Error estimates and condition numbers for radial basis function interpolation, Adv. Comput. Math., 3 (1995), 251–264.
36. M. Scheuerer: An alternative procedure for selecting a good value for the parameter c in RBF-interpolation, Adv. Comput. Math., 34 (2011), 105–126.
37. M. Scheuerer, R. Schaback and M. Schlather: Interpolation of spatial data – A stochastic or a deterministic problem?, European J. Appl. Math., 24 (2013), 601–629.
38. G. K. Veni, C. Satyanarayana and M. C. Krishnareddy: Residual error based adaptive method with an optimal variable scaling parameter for RBF interpolation, International Journal of Applied Mechanics and Engineering, 28 (2023), 37–46.
39. H. Wendland: Scattered Data Approximation, Cambridge Monogr. Appl. Comput. Math., vol. 17, Cambridge Univ. Press, Cambridge (2005).
40. Q. Zhang, Y. Zhao and J. Levesley: Adaptive radial basis function interpolation using an error indicator, Numer. Algorithms, 76 (2017), 441–471.