×

An introduction to the Hilbert-Schmidt SVD using iterated Brownian bridge kernels. (English) Zbl 1309.65016

Summary: Kernel-based approximation methods – often in the form of radial basis functions – have been used for many years now and usually involve setting up a kernel matrix which may be ill-conditioned when the shape parameter of the kernel takes on extreme values, i.e., makes the kernel “flat”. In this paper we present an algorithm we refer to as the Hilbert-Schmidt singular value decomposition (SVD) and use it to emphasize two important points which – while not entirely new – present a paradigm shift under way in the practical application of kernel-based approximation methods: (i) it is not necessary to form the kernel matrix (in fact, it might even be a bad idea to do so), and (ii) it is not necessary to know the kernel in closed form. While the Hilbert-Schmidt SVD and its two implications apply to general positive definite kernels, we introduce in this paper a class of so-called iterated Brownian bridge kernels which allow us to keep the discussion as simple and accessible as possible.

MSC:

65D05 Numerical interpolation
65D07 Numerical computation using splines
41A15 Spline approximation

Software:

Matlab; rbf_qr; DLMF
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allasia, G., Cavoretto, R., De Rossi, A.: Lobachevsky spline functions and interpolation to scattered data. Comput. Appl. Math. 32(1), 71-87 (2013) · Zbl 1273.65015 · doi:10.1007/s40314-013-0011-0
[2] Allasia, G., Cavoretto, R., De Rossi, A.: Numerical integration on multivariate scattered data by Lobachevsky splines. Int. J. Comput. Math. 90(9), 2003-2018 (2013) · Zbl 1291.65035 · doi:10.1080/00207160.2013.772144
[3] Beatson, R.K., Light, W.A., Billings, S.: Fast solution of the radial basis function interpolation equations: domain decomposition methods. SIAM. J. Sci. Comput. 22, 1717-1740 (2000) · Zbl 0982.65015
[4] Berlinet, A., Thomas-Agnan, C.: Reproducing Kernel Hilbert Spaces in Probability and Statistics. Springer (2004) · Zbl 1145.62002
[5] de Boor, C.: On interpolation by radial polynomials. Adv. Comput. Math. 24(1-4), 143-153 (2006) · Zbl 1093.41002 · doi:10.1007/s10444-004-7630-3
[6] Brinks, R.: On the convergence of derivatives of B-splines to derivatives of the Gaussian function. Comput. Appl. Math. 27(1), 79-92 (2008) · Zbl 1154.42304 · doi:10.1590/S1807-03022008000100005
[7] Cavoretto, R.: Meshfree approximation methods, algorithms and applications. Ph.D. thesis. University of Turin (2010) · Zbl 0242.41008
[8] Chen, W., Fu, Z.J., Chen, C.S.: Recent Advances on Radial Basis Function Collocation Methods. Springer Briefs in Applied Sciences and Technology. Springer (2014) · Zbl 1282.65160
[9] Courant, R., Hilbert, D.: Methods of Mathematical Physics, vol. 1. Wiley (1953). Reprinted 1989 · Zbl 0051.28802
[10] Online companion to [28] (2012) · Zbl 1111.65117
[11] Driscoll, T.A., Fornberg, B.: Interpolation in the limit of increasingly at radial basis functions. Comput. Math. Appl. 43(3-5), 413-422 (2002) · Zbl 1006.65013 · doi:10.1016/S0898-1221(01)00295-4
[12] Fasshauer, G.E.: Meshfree Approximation Methods with MATLAB. World Scientific Publishing Co., Inc., River Edge, NJ (2007) · Zbl 1123.65001 · doi:10.1142/6437
[13] Fasshauer, G.E., Hickernell, F.J., Woźniakowski, H.: On dimension-independent rates of convergence for function approximation with Gaussian kernels. SIAM J. Numer. Anal. 50(1), 247-271 (2012) · Zbl 1243.65025 · doi:10.1137/10080138X
[14] Fasshauer, G.E., McCourt, M.: Stable evaluation of Gaussian RBF interpolants. SIAM J. Sci. Comput. 34(2), A737-A762 (2012) · Zbl 1252.65028 · doi:10.1137/110824784
[15] Fornberg, B., Larsson, E., Flyer, N.: Stable computations with Gaussian radial basis functions. SIAM J. Sci. Comput. 33(2), 869-892 (2011) · Zbl 1227.65018 · doi:10.1137/09076756X
[16] Fornberg, B., Piret, C.: A stable algorithm for at radial basis functions on a sphere. SIAM J. Sci. Comput. 30(1), 60-80 (2008) · Zbl 1159.65307 · doi:10.1137/060671991
[17] Fornberg, B., Wright, G.: Stable computation of multiquadric interpolants for all values of the shape parameter. Comput. Math. Appl. 48(5-6), 853-867 (2004) · Zbl 1072.41001 · doi:10.1016/j.camwa.2003.08.010
[18] Glasserman, P.: Monte Carlo Methods in Financial Engineering. In: Applications of Mathematics, vol. 53. Springer-Verlag, New York (2004) · Zbl 1038.91045
[19] Golub, G.H., Van Loan, C.F., 3rd edn.: Matrix Computations. Johns Hopkins University Press, Baltimore, MD (1996) · Zbl 0865.65009
[20] Griebel, M., Rieger, C., Zwicknagl, B.: Multiscale approximation and reproducing kernel Hilbert space methods, INS Preprint No. 1312. University of Bonn (2013) · Zbl 1312.41025
[21] Hubbert, S., Müller, S.: Thin plate spline interpolation on the unit interval. Numer. Algoritm. 45(1-4), 167-177 (2007) · Zbl 1125.65011 · doi:10.1007/s11075-007-9103-5
[22] Larsson, E., Fornberg, B.: Theoretical and computational aspects of multivariate interpolation with increasingly at radial basis functions. Comput. Math. Appl. 49(1), 103-130 (2005) · Zbl 1074.41012 · doi:10.1016/j.camwa.2005.01.010
[23] Lee, Y.J., Yoon, G.J., Yoon, J.: Convergence of increasingly at radial basis interpolants to polynomial interpolants. SIAM J. Numer. Anal. 39(2), 537-553 (2007) · Zbl 1132.41303 · doi:10.1137/050642113
[24] Lyche, T., Schumaker, L.L.: On the convergence of cubic interpolating splines. In: Spline Functions and Approximation Theory (Proc. Sympos., Univ. Alberta, Edmonton, Alta., 1972), International Series Numerical Mathematical, vol. 21, pp 169-189. Basel, Birkhäuser (1973)
[25] Marsden, M.: Cubic spline interpolation of continuous functions. J. Approx. Theory 10(2), 103-111 (1974) · Zbl 0281.41002 · doi:10.1016/0021-9045(74)90109-9
[26] Mercer, J.: Functions of positive and negative type, and their connection with the theory of integral equations. Philosophical Transactions of the Royal Society of London. Ser. A Containing Pap. Math. Phys. Charact. 209(441-458), 415-446 (1909) · JFM 40.0408.02
[27] Novak, E., Woźniakowski, H.: Tractability of Multivariate Problems Volume 1: Linear Information. No. 6 in EMS Tracts in Mathematics. European Mathematical Society (2008) · Zbl 1156.65001
[28] Olver, F.W.J., Lozier, D.W., Boisvert, R.F., Clark, C.W. (eds.): NIST Handbook of Mathematical Functions. Cambridge University Press, New York. Print companion to [10] (2010) · Zbl 1198.00002
[29] Opfer, R.: Multiscale kernels. Adv. Comput. Math. 25(4), 357-380 (2006) · Zbl 1111.65117 · doi:10.1007/s10444-004-7622-3
[30] Rasmussen, C.E., Williams, C.K.I.: Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press (2005) · Zbl 1290.41014
[31] Rieger, C.; Schaback, R.; Zwicknagl, B.; Dæhlen, M. (ed.); Floater, M. (ed.); Lyche, T. (ed.); Merrien, JL (ed.); Mørken, K. (ed.); Schumaker, LL (ed.), Sampling and stability, 347-369 (2010), Berlin, Heidelberg
[32] Ritter, K.: Average-Case Analysis of Numerical Problems, Lecture Notes in Mathematics, vol. 1733. Springer (2000) · Zbl 0949.65146
[33] Schaback, R.: Limit problems for interpolation by analytic radial basis functions. J. Comput. Appl. Math. 212(2), 127-149 (2008) · Zbl 1129.41002 · doi:10.1016/j.cam.2006.11.023
[34] Schaback, R.: Kernel-Based Meshless Methods. Manuscript (2011) · Zbl 1165.65066
[35] Schmidt, E.: Über die Auflösung linearer Gleichungen mit unendlich vielen Unbekannten. Rend. Circ. Mat. Palermo 25(1), 53-77 (1908) · JFM 39.0401.01 · doi:10.1007/BF03029116
[36] Schultz, M.H., Varga, R.S.: L-splines. Numer. Math. 10(4), 345-369 (1967) · Zbl 0183.44402 · doi:10.1007/BF02162033
[37] Schumaker, L.L.: Spline Functions: Basic Theory. Wiley, New York (1993). Reprinted by Krieger Publishing · Zbl 1123.41008
[38] Shreve, S.E.: Stochastic Calculus for Finance II: Continuous-time Models, vol. 11. Springer (2004) · Zbl 1068.91041
[39] Song, G., Riddle, J., Fasshauer, G.E., Hickernell, F.J.: Multivariate interpolation with increasingly at radial basis functions of finite smoothness. Adv. Comput. Math. 36(3), 485-501 (2012) · Zbl 1250.41002 · doi:10.1007/s10444-011-9192-5
[40] Stein, M.L.: Interpolation of Spatial Data: Some Theory for Kriging. Springer Series in Statistics. Springer (1999) · Zbl 0924.62100
[41] Steinwart, I., Christmann, A.: Support Vector Machines. Information Science and Statistics. Springer (2008) · Zbl 1203.68171
[42] Swartz, B.K., Varga, R.S.: Error bounds for spline and L-spline interpolation. J. Approx. Theory 6(1), 6-49 (1972) · Zbl 0242.41008 · doi:10.1016/0021-9045(72)90079-2
[43] Wahba, G.: Spline Models for Observational Data. SIAM, Philadelphia (1990) · Zbl 0813.62001 · doi:10.1137/1.9781611970128
[44] Zwicknagl, B.: Power series kernels. Constr. Approx. 29(1), 61-84 (2008) · Zbl 1184.41004 · doi:10.1007/s00365-008-9012-4
[45] Zwicknagl, B., Schaback, R.: Interpolation and approximation in Taylor spaces. J. Approx. Theory 171, 65-83 (2013) · Zbl 1290.41014 · doi:10.1016/j.jat.2013.03.006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.