Multiscale Scattered Data Approximation in Samplet Coordinates
Please login to view abstract download link
We study multiscale scattered data interpolation schemes for globally supported radial basis functions, with a focus on the Matérn kernels. The multiscale approximation is constructed through a sequence of residual corrections, where radial basis functions with different lengthscale parameters capture varying levels of detail. To apply this approach to large data sets, we suggest to represent the resulting generalized Vandermonde matrices in samplet coordinates. Samplets are localized, discrete signed measures exhibiting vanishing moments and allow for the sparse approximation of generalized Vandermonde matrices issuing from a vast class of radial basis functions. Given a quasi-uniform set of N data sites, and local approximation spaces with geometrically decreasing dimension, the full multiscale system can be assembled with cost O(N log^2 N). We prove that the condition numbers of the linear systems at each level remain bounded independent of the particular level, allowing us to use Conjugate Gradient solver with a bounded number of iterations for the numerical solution.
