Before revision: We show how to obliviously embed into the reproducing kernel Hilbert spaceassociated with Gaussian kernels, so that distance in this space (the kernel distance) only has (1+\varepsilon)-relative error .
After revision: We introduce a two versions of a new sketch for approximately embedding the Gaussian kernel into Euclidean inner product space. These work by truncating infinite expansions of the Gaussian inner product, and carefully invoking the TensorSketch. After providing concentration and approximation properties of these sketches, we demonstrate them to approximate the kernel distance between points sets. These sketches yield almost (1+\varepsilon)-relative error .