Generation of point sets by convex optimization for interpolation in reproducing kernel Hilbert spaces. (English) Zbl 1459.65020

Summary: We propose algorithms to take point sets for kernel-based interpolation of functions in reproducing kernel Hilbert spaces (RKHSs) by convex optimization. We consider the case of kernels with the Mercer expansion and propose an algorithm by deriving a second-order cone programming (SOCP) problem that yields \(n\) points at one sitting for a given integer \(n\). In addition, by modifying the SOCP problem slightly, we propose another sequential algorithm that adds an arbitrary number of new points in each step. Numerical experiments show that in several cases the proposed algorithms compete with the \(P\)-greedy algorithm, which is known to provide nearly optimal points.


65D05 Numerical interpolation
41A05 Interpolation in approximation theory
46E22 Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces)
Full Text: DOI arXiv


[1] Alizadeh, F.; Goldfarb, D., Second-order cone programming, Math. Program., Ser. B, 95, 3-51 (2003) · Zbl 1153.90522
[2] Atkinson, K.; Han, W., Spherical Harmonics and Approximations on the Unit Sphere: an Introduction (2012), Berlin: Springer, Berlin · Zbl 1254.41015
[3] Borwein, JM; Lewis, AS, Convex Analysis and Nonlinear Optimization: Theory and Examples (2006), New York: Springer, New York
[4] Briani, M.; Sommariva, A.; Vianello, M., Computing Fekete and Lebesgue points: simplex, square, disk, J. Comput. Appl. Math., 236, 2477-2486 (2012) · Zbl 1242.41002
[5] Buhmann, M., Radial basis functions, Acta Numer., 10, 1-38 (2000) · Zbl 1004.65015
[6] Dai, F.; Xu, Y., Approximation Theory and Harmonic Analysis on Spheres and Balls (2013), New York: Springer, New York · Zbl 1275.42001
[7] Fasshauer, G., Meshfree Approximation Methods with MATLAB (2007), Singapore: World Scientific, Singapore · Zbl 1123.65001
[8] Fasshauer, G.; McCourt, M., Kernel-Based Approximation Methods Using MATLAB (2015), Singapore: World Scientific, Singapore
[9] Lobo, MS; Vandenberghe, L.; Boyd, S.; Lebret, H., Applications of second-order cone programming, Linear Algebra Appl., 284, 193-228 (1998) · Zbl 0946.90050
[10] De Marchi, S., On optimal center locations for radial basis function interpolation: computational aspects, Rend. Sem. Mat. Univ. Pol. Torino, 61, 343-358 (2003) · Zbl 1121.41003
[11] De Marchi, S.: Geometric greedy and greedy points for RBF interpolation. In: Proceedings of the International Conference on Computational and Mathematical Methods in Science and Engineering, CMMSE 2009 (2009)
[12] De Marchi, S.; Schaback, R.; Wendland, H., Near-optimal data-independent point locations for radial basis function interpolation, Adv. Comput. Math., 23, 317-330 (2005) · Zbl 1070.65008
[13] Nguyen, VP; Rabczuk, T.; Bordas, S.; Duflot, M., Meshless methods: a review and computer implementation aspects, Math. Comput. Simul., 79, 763-813 (2008) · Zbl 1152.74055
[14] Müller, S.: Complexity and stability of kernel-based reconstructions (in German). dissertation, Georg-August-Universität Göttingen, Institut für Numerische und Angewandte Mathematik, Lotzestrasse 16-18, D-37083 Göttingen, Jan 2009. Göttinger Online Klassifikation: EDDF 050 (2009)
[15] Sangol, G., Computing optimal designs of multiresponse experiments reduces to second order cone programming, J. Statist. Plann. Inference, 141, 1684-1708 (2011) · Zbl 1207.62156
[16] Sangol, G.; Harman, R., Computing exact D-optimal designs by mixed integer second-order cone programming, Ann. Statist., 43, 2198-2224 (2015) · Zbl 1331.62384
[17] Santin, G.; Haasdonk, B., Convergence rate of the data-independent P-greedy algorithm in kernel-based approximation, Dolomites Research Notes on Approximation, 10, 68-78 (2017) · Zbl 1370.94401
[18] Schaback, R.; Wendland, H., Adaptive greedy techniques for approximate solution of large RBF systems, Numer. Algor., 24, 239-254 (2000) · Zbl 0957.65021
[19] Schaback, R.; Wendland, H., Kernel techniques: from machine learning to meshless methods, Acta Numer., 15, 543-639 (2006) · Zbl 1111.65108
[20] Tanaka, K.: Matlab programs for generating point sets for interpolation in reproducing kernel Hilbert spaces. https://github.com/KeTanakaN/mat_points_interp_rkhs (last accessed on October 19, 2018)
[21] Wendland, H., Scattered Data Approximation (2005), Cambridge: Cambridge University Press, Cambridge
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.