Random Fourier Features in Near-Linear Time
The authors developed a randomized map for kernels like Gaussian kernels that can be computed in near-linear time, specifically O((d + m) log d). This improves upon previous fast variants by achieving strong concentration guarantees, meaning the approximation of the kernel function is very reliable. The method extends to other radial kernels and provides efficient solutions for tasks like Kernel Density Estimation.