A hybrid stochastic interpolation and compression method for kernel matrices

Kernel functions play an important role in a wide range of scientific computing and machine learning problems. These functions lead to dense kernel matrices that impose great challenges in computational costs at large scale. In this paper, we develop a set of fast kernel matrix compressing algorithms, which can reduce computation cost of matrix operations in the related applications. The foundation of these algorithms is the polyharmonic spline interpolation, which includes a set of radial basis functions that allow flexible choices of interpolating nodes, and a set of polynomial basis functions that guarantee the solvability and convergence of the interpolation. With these properties, original data points in the interacting kernel function can be randomly sampled with great flexibility, so the proposed method is suitable for complicated data structures, such as high-dimensionality, random distribution, or manifold. To further boost the algorithm accuracy and efficiency, this scheme is equipped with a QR sampling strategy, and combined with a recently developed fast stochastic SVD to form a hybrid method. If the overall number of degree of freedom is $$, then the compressing algorithm has complexity of $$ for low-rank matrices, and $$ for general matrices with a hierarchical structure. Numerical results for data on various domains and different kernel functions validate the accuracy and efficiency of the proposed method.