# Multiresolution kernel matrix algebra

arXiv: https://arxiv.org/abs/2211.11681 · HTML: https://mlsanity.com/paper/2211.11681/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 4 of its 70 references that are in the map.
- First posted on arXiv 21 Nov 2022.

## Builds on (most cited first, 4 of 4)

- [Multipole Graph Neural Operator for Parametric Partial Differential Equations](https://mlsanity.com/paper/2006.09535/) (2020)
- [Randomly pivoted Cholesky: Practical approximation of a kernel matrix with few entry evaluations](https://mlsanity.com/paper/2207.06503/) (2022)
- [A representer theorem for deep kernel learning](https://mlsanity.com/paper/1709.10441/) (2017)
- [New frontiers in Bayesian modeling using the INLA package in R](https://mlsanity.com/paper/1907.10426/) (2019)

## Built on by (most cited first, 6 of 6)

- [Samplet basis pursuit: Multiresolution scattered data approximation with sparsity constraints](https://mlsanity.com/paper/2306.10180/) (2023)
- [Multiscale scattered data analysis in samplet coordinates](https://mlsanity.com/paper/2409.14791/) (2024)
- [Multiresolution local smoothness detection in non-uniformly sampled multivariate signals](https://mlsanity.com/paper/2507.13480/) (2025)
- [Bespoke multiresolution analysis of graph signals](https://mlsanity.com/paper/2507.19181/) (2025)
- [Data-intrinsic approximation in metric spaces](https://mlsanity.com/paper/2510.13496/) (2025)
- [On Quasi-Localized Dual Pairs in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/2408.11389/) (2024)

## Abstract (arXiv)

We propose a sparse algebra for samplet compressed kernel matrices, to enable efficient scattered data analysis. We show the compression of kernel matrices by means of samplets produces optimally sparse matrices in a certain S-format. It can be performed in cost and memory that scale essentially linearly with the matrix size N, for kernels of finite differentiability, along with addition and multiplication of S-formatted matrices. We prove and exploit the fact that the inverse of a kernel matrix (if it exists) is compressible in the S-format as well. Selected inversion allows to directly compute the entries in the corresponding sparsity pattern. The S-formatted matrix operations enable the efficient, approximate computation of more complicated matrix functions such as bm Aα or exp(bm A). The matrix algebra is justified mathematically by pseudo differential calculus. As an application, efficient Gaussian process learning algorithms for spatial statistics is considered. Numerical results are presented to illustrate and quantify our findings.