Paper detail

Better bases for kernel spaces

In this article we investigate the feasibility of constructing stable, local bases for computing with kernels. In particular, we are interested in constructing families $(b_ξ)_{ξ\inΞ}$ that function as bases for kernel spaces $S(k,Ξ)$ so that each basis function is constructed using very few kernels. In other words, each function $b_ζ(x) = \sum_{ξ\inΞ} A_{ζ,ξ} k(x,ξ)$ is a linear combination of samples of the kernel with few nonzero coefficients $A_{ζ,ξ}$. This is reminiscent of the construction of the B-spline basis from the family of truncated power functions. We demonstrate that for a large class of kernels (the Sobolev kernels as well as many kernels of polyharmonic and related type) such bases exist. In fact, the basis elements can be constructed using a combination of roughly $O(\log N)^d$ kernels, where $d$ is the local dimension of the manifold and $N$ is the dimension of the kernel space (i.e. $N=#Ξ$). Viewing this as a preprocessing step -- the construction of the basis has computational cost $O(N(\log N)^d)$. Furthermore, we prove that the new basis is $L_p$ stable and satisfies polynomial decay estimates that are stationary with respect to the density of $Ξ$.