Tree-Adaptive Multiscale Kernel Lasso in Samplet Coordinates
This work addresses computational challenges in kernel methods for scattered data problems, offering an incremental improvement in efficiency and sparsity for applications in domains like spatial modeling.
The authors tackled the problem of large scattered data approximation by developing a sparse multiscale kernel framework that reduces the effective problem size through adaptive data site selection, achieving accurate reconstructions with sparser representations and good computational efficiency.
We develop a novel framework for sparse multiscale kernel approximation of large scattered data problems based on a samplet representation. Samplets form a multiresolution analysis of localized discrete signed measures and enable quasi-sparse representations of kernel matrices associated to asymptotically smooth kernels as well as smoothness detection of scattered data. Building on the latter, we introduce an adaptive data site selection strategy based on the localization of the native reproducing kernel Hilbert space norm in the samplet expansion coefficients. The selection results in a small set of representative data sites, significantly reducing the effective problem size. On the corresponding reduced kernel subspace, we solve an $\ell^1$-regularized least-squares problem using a trust-region semismooth Newton method in a normal-map formulation, stabilized by an online low-rank SVD on the active set to handle the notorious ill-conditioning of kernel matrices. Numerical experiments in two and three dimensions, including multi-kernel models with varying lengthscales, demonstrate that the proposed approach achieves accurate reconstructions with considerably sparser representations and good computational efficiency.