  The method of random Fourier features (RFF), proposed in a seminal paper by
Rahimi and Recht (NIPS'07), is a powerful technique to find approximate
low-dimensional representations of points in (high-dimensional) kernel space,
for shift-invariant kernels. While RFF has been analyzed under various notions
of error guarantee, the ability to preserve the kernel distance with
\emph{relative} error is less understood. We show that for a significant range
of kernels, including the well-known Laplacian kernels, RFF cannot approximate
the kernel distance with small relative error using low dimensions. We
complement this by showing as long as the shift-invariant kernel is analytic,
RFF with $\mathrm{poly}(\epsilon^{-1} \log n)$ dimensions achieves
$\epsilon$-relative error for pairwise kernel distance of $n$ points, and the
dimension bound is improved to $\mathrm{poly}(\epsilon^{-1}\log k)$ for the
specific application of kernel $k$-means. Finally, going beyond RFF, we make
the first step towards data-oblivious dimension-reduction for general
shift-invariant kernels, and we obtain a similar $\mathrm{poly}(\epsilon^{-1}
\log n)$ dimension bound for Laplacian kernels. We also validate the
dimension-error tradeoff of our methods on simulated datasets, and they
demonstrate superior performance compared with other popular methods including
random-projection and Nystr\"{o}m methods.
