Abstract
In this work we extend some ideas about greedy algorithms, which are well-established tools for, e.g., kernel bases, and exponential-polynomial splines whose main drawback consists in possible overfitting and consequent oscillations of the approximant. To partially overcome this issue, we develop some results on theoretically optimal interpolation points. Moreover, we introduce two algorithms which perform an adaptive selection of the spline interpolation points based on the minimization either of the sample residuals (f-greedy), or of an upper bound for the approximation error based on the spline Lebesgue function (\(\lambda\)-greedy). Both methods allow us to obtain an adaptive selection of the sampling points, i.e., the spline nodes. While the f-greedy selection is tailored to one specific target function, the \(\lambda\)-greedy algorithm enables us to define target-data-independent interpolation nodes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bos, L., De Marchi, S., Vianello, M.: Polynomial approximation on Lissajous curves in the \(d-\)cube. Appl. Num. Math. 116, 47–56 (2017)
Campagna, R., Conti, C.: Penalized hyperbolic-polynomial splines. Appl. Math. Lett. 118 (2021). https://doi.org/10.1016/j.aml.2021.107159
Fasshauer, G.E., McCourt, M.: Kernel-based Approximation Methods Using MATLAB. World scientific, Singapore (2015)
Wendland, H.: Scattered Data Approximation. Cambridge Monographs on Applied and Computational Mathematics, vol. 17. Cambridge University Press, Cambridge (2005)
Conti, C., Romani, L., Schenone, D.: Semi-automatic spline fitting of planar curvilinear profiles in digital images using the Hough transform. Pattern Recogn. 74, 64–76 (2018)
Bohra, P., Campos, J., Gupta, H., Aziznejad, S., Unser, M.: Learning activation functions in deep (spline) neural networks. IEEE Open J. Signal Process. 1, 295–309 (2020)
Unser, M.: A representer theorem for deep neural networks. J. Machine Learning Res. 20, 1–30 (2019)
Cohen, E., Riesenfeld, R., Elber, G.: Geometric Modeling with Splines. CRC Press, New York (2001)
Uhlmann, V., Delgado-Gonzalo, R., Conti, C., Romani, L., Unser, M.: Exponential Hermite splines for the analysis of biomedical images. In: IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2014, Florence, Italy, May 4-9, 2014, pp. 1631–1634. IEEE, (2014). https://doi.org/10.1109/ICASSP.2014.6853874
Unser, M., Blu, T.: Cardinal exponential splines: part I - theory and filtering algorithms. IEEE Trans. Signal Process. 53(4), 1425–1438 (2005). https://doi.org/10.1109/TSP.2005.843700
Campagna, R., Bayona, V., Cuomo, S.: Using local PHS+poly approximations for Laplace transform inversion by Gaver-Stehfest algorithm. Dolomites Res. Notes Approx. 13, 55–64 (2020)
Campagna, R., Conti, C., Cuomo, S.: Smoothing exponential-polynomial splines for multiexponential decay data. Dolomites Res. Notes Approx. 12(1), 86–100 (2019)
Campagna, R., Conti, C., Cuomo, S.: Computational error bounds for Laplace transform inversion based on smoothing splines. Appl. Math. Comput. 383, 125376 (2020)
Brutman, L.: On the Lebesgue function for polynomial interpolation. SIAM J. Numer. Anal. 15, 694–704 (1978)
Brutman, L.: Lebesgue functions for polynomial interpolation - a survey. Ann. Numer. Math. 4, 111–127 (1997)
Bayliss, A., Turkel, E.: Mappings and accuracy for Chebyshev pseudo-spectral approximations. J. Comput. Phys. 101, 349–359 (1992)
Berrut, J.P., Mittelmann, H.D.: Lebesgue constant minimizing linear rational interpolation of continuous functions over the interval. Comput. Math. Appl. 33(6), 77–86 (1997)
Bos, L., Caliari, M., De Marchi, S., Vianello, M., Xu, Y.: Bivariate Lagrange interpolation at the Padua points: The generating curve approach. J. Approx. Theory 143(1), 15–25 (2006)
Bos, L., De Marchi, S., Hormann, K.: On the Lebesgue constant of Berrut’s rational interpolant at equidistant nodes. J. Comput. Appl. Math. 236(4), 504–510 (2011)
De Marchi, S., Marchetti, F., Perracchione, E., Poggiali, D.: Multivariate approximation at fake nodes. Appl. Math. Comput. 391, 125628 (2021)
Temlyakov, V.N.: Greedy approximation. Acta Numer 17, 235–409 (2008). https://doi.org/10.1017/S0962492906380014
Haasdonk, B., Santin, G.: Greedy kernel approximation for sparse surrogate modeling. In: Keiper, W., Milde, A., Volkwein, S. (eds.) Reduced-Order Modeling (ROM) for Simulation and Optimization: Powerful Algorithms as Key Enablers for Scientific Computing, pp. 21–45. Springer, Cham (2018)
Marchi, S.D., Schaback, R., Wendland, H.: Near-optimal data-independent point locations for radial basis function interpolation. Adv. Comput. Math. 23, 317–330 (2005)
Santin, G., Haasdonk, B.: Convergence rate of the data-independent \(P\)-greedy algorithm in kernel-based approximation. Dolomites Res. Notes Approx. 10(2), 68–78 (2017)
Wirtz, D., Haasdonk, B.: A Vectorial Kernel Orthogonal Greedy Algorithm. Dolomites Res. Notes Approx. 6, 83–100 (2013). https://doi.org/10.14658/pupj-drna-2013-Special_Issue
Wenzel, T., Santin, G., Haasdonk, B.: A novel class of stabilized greedy kernel approximation algorithms: Convergence, stability and uniform point distribution. Journal of Approximation Theory 262, 105508 (2021). https://doi.org/10.1016/j.jat.2020.105508
Wenzel, T., Santin, G., Haasdonk, B.: Analysis of target data-dependent greedy kernel algorithms: Convergence rates for f-, f\(\cdot\)P- and f\(/\)P-greedy. https://arxiv.org/abs/2105.07411, Accepted for publication in Constructive Approximation (2021)
Dutta, S., Farthing, M.W., Perracchione, E., Savant, G., Putti, M.: A greedy non-intrusive reduced order model for shallow water equations. J. Comput. Phys. 439, 110378 (2021)
Seatzu, S.: Un metodo per la costruzione di smoothing splines naturali mono e bidimensionali. Calcolo 12, 259–273 (1975)
Stoer, J., Bulirsch, R.: Introduction to Numerical Analysis vol. 3. Springer (2002)
Atkinson, K.E.: An Introduction to Numerical Analysis. John Wiley & Sons (2008)
Campagna, R., Conti, C., Cuomo, S.: Data-driven selection of HP-splines frequency parameter. Manuscript (2022)
Yueh, W.-C.: Eigenvalues of several tridiagonal matrices. Applied Mathematics E-Notes [electronic only] 5, 66–74 (2005)
Schaback, R., Wendland, H.: Adaptive greedy techniques for approximate solution of large RBF systems. Numer. Algorithms 24(3), 239–254 (2000). https://doi.org/10.1023/A:1019105612985
Köppel, M., Franzelin, F., Kröker, I., Oladyshkin, S., Santin, G., Wittwar, D., Barth, A., Haasdonk, B., Nowak, W., Pflüger, D., Rohde, C.: Comparison of data-driven uncertainty quantification methods for a carbon dioxide storage benchmark scenario. Comput. Geosci. 23(2), 339–354 (2019). https://doi.org/10.1007/s10596-018-9785-x
Romano, A., Campagna, R., Masi, P., Toraldo, G.: NMR data analysis of water mobility in wheat flour dough: A computational approach. In: Sergeyev, Y.D., Kvasov, D.E. (eds.) Numerical Computations: Theory and Algorithms, pp. 146–157. Springer, Cham (2020)
Campagna, R., Perracchione, E.: Feature augmentation for numerical inversion of multi-exponential decay curves. AIP Conference Proceedings 2425(1), 050004 (2022) https://aip.scitation.org/doi/pdf/10.1063/5.0081505. https://doi.org/10.1063/5.0081505
Perracchione, E., Massone, A.M., Piana, M.: Feature augmentation for the inversion of the Fourier transform with limited data. Inverse Problems (2021). https://doi.org/10.1088/1361-6420/ac1ad7
Acknowledgements
We thank the support of the GNCS-INdAM project “Interpolazione e smoothing: aspetti teorici, computazionali e applicativi”. This research has been carried out within the Italian Network on Approximation (RITA) and the thematic group on “ Approximation Theory and Applications” of the Italian Mathematical Union (UMI). We sincerely thank the reviewers for helping us to significantly improve the paper.
Funding
Open access funding provided by Politecnico di Torino within the CRUI-CARE Agreement.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare no competing interests.
Additional information
Communicated by Anthony Patera.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix. Proof of Lemma 1
Appendix. Proof of Lemma 1
Proof
We use the values
which give
It follows that
Now using the fact that \(\cosh (x) \ge 1\) for all \(x\in {\mathbb R}\), and the Taylor expansion \(\sinh (\alpha ) = \sum _{n=0}^\infty \frac{\alpha ^{2n + 1}}{(2 n + 1)!}\), we have
where we used the fact that only even powers occur in the sum.
Moreover,
and in particular \(\kappa (-\alpha ) = \kappa (\alpha )\) since \(\tanh (\alpha /2)^2\) is even and \(\sinh\) is odd. To study the behavior of \(\kappa (\alpha )\) we can thus restrict to non-negative values of \(\alpha\). It clearly holds that \(\kappa (\alpha )\ge 1\) by definition. Moreover \(\lim _{\alpha \rightarrow \infty }\tanh (\alpha )=1\), and \(\lim _{\alpha \rightarrow \infty } \frac{\sinh (\alpha )+\alpha }{\sinh (\alpha )-\alpha } = 1\) since \(\sinh\) has a super-linear growth, and thus \(\lim _{\alpha \rightarrow \infty } \kappa (\alpha ) = 1\). The Taylor expansion of \(\kappa (\alpha )\) around zero gives \(\kappa (\alpha ) = 3 - \frac{2}{5}\alpha ^5 + \mathcal O(\alpha ^4)\) for small \(\alpha\), which in turn gives the desired asymptotic in zero.
Finally, we have
The denominator of \(\kappa '(\alpha )\) is non-negative. Moreover
and thus \(\kappa '(\alpha )\) has the same sign of \(-\tanh (\alpha /2)\), i.e., \(\kappa '(\alpha )\le 0\) if \(\alpha \ge 0\). Since \(\lim _{\alpha \rightarrow \infty } \kappa (\alpha ) = 1\), and \(\lim _{\alpha \rightarrow 0} \kappa (\alpha ) = 3\), we have \(1\le \kappa (\alpha )\le 3\).
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
Campagna, R., De Marchi, S., Perracchione, E. et al. Stable interpolation with exponential-polynomial splines and node selection via greedy algorithms. Adv Comput Math 48, 69 (2022). https://doi.org/10.1007/s10444-022-09986-8
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10444-022-09986-8