nach oben

Numerical Algorithms

Erschienen in:

15.08.2019 | Original Paper

Generation of point sets by convex optimization for interpolation in reproducing kernel Hilbert spaces

verfasst von: Ken’ichiro Tanaka

Erschienen in: Numerical Algorithms | Ausgabe 3/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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.

Vorheriger Artikel A second-order artificial compression method for the evolutionary Stokes-Darcy system

Nächster Artikel Fast conservative numerical algorithm for the coupled fractional Klein-Gordon-Schrödinger equation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

If K is translation-invariant, we can choose a starting point x₁ arbitrarily.

As shown in [3, Proposition 3.3.3], the function \(X \mapsto \log \det X\) is concave on the set of positive definite matrices. Then, the objective function of Problem (3.12) can be regarded as the restriction of this function to the affine subset of the set of positive definite matrices. Therefore, the objective function is log-concave.

The authors of [16] consider the more general case that a_j are matrices with a common number of rows.

For example, we observed that Algorithm 1 failed for n = 100 in the case of Example 2 because of this phenomenon.

Therefore, the optimal value of SOCP (4.6) is \(2^{(p-1)2^{p-1}}\) (the optimal value of Problem (4.1))^1/ℓ.

Alizadeh, F., Goldfarb, D.: Second-order cone programming. Math. Program., Ser. B 95, 3–51 (2003)CrossRefMathSciNetMATH

Atkinson, K., Han, W.: Spherical Harmonics and Approximations on the Unit Sphere: an Introduction. Springer, Berlin (2012)CrossRefMATH

Borwein, J.M., Lewis, A.S.: Convex Analysis and Nonlinear Optimization: Theory and Examples, 2nd edn. Springer, New York (2006)CrossRefMATH

Briani, M., Sommariva, A., Vianello, M.: Computing Fekete and Lebesgue points: simplex, square, disk. J. Comput. Appl. Math. 236, 2477–2486 (2012)CrossRefMathSciNetMATH

Buhmann, M.: Radial basis functions. Acta Numer. 10, 1–38 (2000)CrossRefMathSciNetMATH

Dai, F., Xu, Y.: Approximation Theory and Harmonic Analysis on Spheres and Balls. Springer, New York (2013)CrossRefMATH

Fasshauer, G.: Meshfree Approximation Methods with MATLAB. World Scientific, Singapore (2007)CrossRefMATH

Fasshauer, G., McCourt, M.: Kernel-Based Approximation Methods Using MATLAB. World Scientific, Singapore (2015)CrossRefMATH

Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl. 284, 193–228 (1998)CrossRefMathSciNetMATH

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)MATHMathSciNet

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)CrossRefMathSciNetMATH

13.

Nguyen, V.P., Rabczuk, T., Bordas, S., Duflot, M.: Meshless methods: a review and computer implementation aspects. Math. Comput. Simul. 79, 763–813 (2008)CrossRefMathSciNetMATH

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)CrossRefMathSciNet

16.

Sangol, G., Harman, R.: Computing exact D-optimal designs by mixed integer second-order cone programming. Ann. Statist. 43, 2198–2224 (2015)CrossRefMathSciNetMATH

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)MATHMathSciNet

18.

Schaback, R., Wendland, H.: Adaptive greedy techniques for approximate solution of large RBF systems. Numer. Algor. 24, 239–254 (2000)CrossRefMathSciNetMATH

19.

Schaback, R., Wendland, H.: Kernel techniques: from machine learning to meshless methods. Acta Numer. 15, 543–639 (2006)CrossRefMathSciNetMATH

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. Cambridge University Press, Cambridge (2005)MATH

Titel: Generation of point sets by convex optimization for interpolation in reproducing kernel Hilbert spaces
verfasst von: Ken’ichiro Tanaka
Publikationsdatum: 15.08.2019
Verlag: Springer US
Erschienen in: Numerical Algorithms / Ausgabe 3/2020
Print ISSN: 1017-1398
Elektronische ISSN: 1572-9265
DOI: https://doi.org/10.1007/s11075-019-00792-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Weitere Artikel der Ausgabe 3/2020

A convergence study for reduced rank extrapolation on nonlinear systems

A second-order artificial compression method for the evolutionary Stokes-Darcy system

Family weak conjugate gradient algorithms and their convergence analysis for nonconvex functions

Numerical approximation of the fractional Cahn-Hilliard equation by operator splitting method

An ADMM-based scheme for distance function approximation

Condition numbers of the multidimensional total least squares problems having more than one solution

Premium Partner