arXiv:2610.20266v1 Announce Type: new Abstract: Deep Gaussian processes (DGPs) use iterative sampling to create non-stationary random fields. This is notoriously expensive because the covariance at each non-initial layer depends on the realised field from the layer below, so it changes with every sample. Moreover, standard fast sampling techniques like circulant embedding or matrix compression fail since the underlying kernel usually lacks the necessary regularity and structure. We develop and analyse a wavelet compression method for convolution Mat\'ern DGPs. At each layer the covariance matrix is compressed using wavelets and a Lanczos algorithm computes the random sample. For specific parameter ranges involving the smoothness of the Mat\'ern kernel as well as the smoothness of the wavelets, we show that the accumulative compression and sampling errors through all layers decay exponentially with increasing truncation parameter. We obtain a practical DGP sampling algorithm by choosing a truncation that gives log-linear covariance storage and matrix-vector costs, enabling DGP sampling at nearly linear computational cost.