Generation of point sets by convex optimization for interpolation in reproducing kernel Hilbert spaces
- PDF / 2,980,097 Bytes
- 31 Pages / 439.642 x 666.49 pts Page_size
- 32 Downloads / 207 Views
Generation of point sets by convex optimization for interpolation in reproducing kernel Hilbert spaces Ken’ichiro Tanaka1 Received: 22 October 2018 / Accepted: 31 July 2019 / © Springer Science+Business Media, LLC, part of Springer Nature 2019
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. Keywords Reproducing kernel Hilbert space · Kernel interpolation · Point set · Power function · Optimal design · Second-order cone programming Mathematics Subject Classification (2010) 65D05 · 65D15 · 41A05 · 46E22
1 Introduction We propose algorithms to take point sets for kernel-based interpolation of functions in reproducing kernel Hilbert spaces (RKHSs). The algorithms are based on a convex optimization problem derived by the Mercer series of the kernel. Kernel-based methods are useful in various fields of scientific computing and engineering. Their details and applications can be found in the references [5, 7, 8, 19, 21]. Many of the applications include approximation of multivariate functions by Ken’ichiro Tanaka
[email protected] 1
Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, 113-8656, Japan
Numerical Algorithms
scattered data as a fundamental component. Therefore, we focus on kernel interpolation in this paper. Let d be a positive integer and let Ω ⊂ Rd be a region. For a finite set {x1 , . . . , xn } ⊂ Ω of n pairwise distinct points and a set {y1 , . . . , yn } ⊂ R, we aim to find a function s : Ω → R with the interpolation condition s(xi ) = yi (i = 1, . . . , n). To this end, we consider a positive definite kernel K : Ω × Ω → R and the function s given by s(x) =
n
cj K(x, xj ),
(1.1)
j =1
where cj are determined by the interpolation condition. For a positive definite kernel K, there exists a unique Hilbert space HK (Ω) of functions from Ω to R where K is a reproducing kernel, that is, (a) ∀x ∈ Ω, K(·, x) ∈ HK (Ω), (b) ∀x ∈ Ω, ∀f ∈ HK (Ω), f, K(·, x)HK (Ω) = f (x).
(1.2) (1.3)
The reproducing kernel Hilbert space (RKHS) HK (Ω) is called the native space of K. As the kernel interpolation, we consider the case that yj = f (xj ) for f ∈ HK (Ω). Then, we encounter a problem of approximating functions in HK (Ω) by the kernel interpolation. Such approximation is widely used, for example, for the numerical solution of partial differential equations via collocation [13]. In such
Data Loading...
