Multiresolution kernel matrix algebra

We propose a sparse arithmetic for kernel matrices, enabling efficient scattered data analysis. The compression of kernel matrices by means of samplets yields sparse matrices such that assembly, addition, and multiplication of these matrices can be performed with essentially linear cost. Since the inverse of a kernel matrix is compressible, too, we have also fast access to the inverse kernel matrix by employing exact sparse selected inversion techniques. As a consequence, we can rapidly evaluate series expansions and contour integrals to access, numerically and approximately in a data-sparse format, more complicated matrix functions such as $A^\alpha$ and $\exp(A)$. By exploiting the matrix arithmetic, also efficient Gaussian process learning algorithms for spatial statistics can be realized. Numerical results are presented to quantify and quality our findings.