  We propose the use of low bit-depth Sigma-Delta and distributed noise-shaping
methods for quantizing the Random Fourier features (RFFs) associated with
shift-invariant kernels. We prove that our quantized RFFs -- even in the case
of $1$-bit quantization -- allow a high accuracy approximation of the
underlying kernels, and the approximation error decays at least polynomially
fast as the dimension of the RFFs increases. We also show that the quantized
RFFs can be further compressed, yielding an excellent trade-off between memory
use and accuracy. Namely, the approximation error now decays exponentially as a
function of the bits used. Moreover, we empirically show by testing the
performance of our methods on several machine learning tasks that our method
compares favorably to other state of the art quantization methods in this
context.
