  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}^\alpha$ 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.
