Construction of quasi-localized dual bases in reproducing kernel Hilbert spaces

A straightforward way to represent the kernel approximant of a function, known by a finite set of samples, within a reproducing kernel Hilbert space is through the canonical dual pair. The canonical dual pair consists of the basis of kernel translates and the corresponding Lagrange basis. From a numerical perspective, one is particularly interested in dual pairs such that the dual basis is quasi-local meaning that it can be well approximated using only a small subset of the data sites. This implies that the inverse Gramian is approximately sparse. In this case, the kernel approximant is efficiently computable by multiplying a sparse matrix with the data vector. We present two methods for finding such quasi-localized dual bases. First, we adapt the idea of localizing the Lagrange basis, which yields an approximate canonical dual pair and extend this idea to derive a new, symmetric preconditioner for kernel matrices. Second, we use samplets to obtain multiresolution versions of dual bases. Samplets are localized discrete signed measures constructed such that their respective measure integrals of polynomials up to a certain degree vanish. Therefore, the kernel matrix and its inverse are compressible to sparse matrices in samplet coordinates for asymptotically smooth kernels. We provide benchmark experiments in two spatial dimensions to demonstrate the compression power of both approaches and apply the new preconditioner to implicit surface reconstruction in computer graphics.