AbstractWe propose a sparse algebra for samplet compressed kernel matrices to enable efficient scattered data analysis. We show that the compression of kernel matrices by means of samplets produces optimally sparse matrices in a certain S-format. The compression can be performed in cost and memory that scale essentially linearly with the number of data points for kernels of finite differentiability. The same holds true for the addition and multiplication of S-formatted matrices. We prove that the inverse of a kernel matrix, given that it exists, is compressible in the S-format as well. The use of selected inversion allows to directly compute the entries in the corresponding sparsity pattern. Moreover, S-formatted matrix operations enable the efficient, approximate computation of more complicated matrix functions such as $${\varvec{A}}^\alpha $$ A α or $$\exp ({\varvec{A}})$$ exp ( A ) of a matrix $${\varvec{A}}$$ A . The matrix algebra is justified mathematically by pseudo differential calculus. As an application, we consider Gaussian process learning algorithms for implicit surfaces. Numerical results are presented to illustrate and quantify our findings.