Fast nonlinear function classes are crucial for nonparametric estimation, such as
in kernel methods. This paper proposes an improvement to random kitchen sinks that
offers significantly faster computation in log-linear time without sacrificing
accuracy. Furthermore, we show how one may adjust the regularization properties of
the kernel simply by changing the spectral distribution of the projection matrix.
We provide experimental results which show that even for for moderately small
problems we already achieve two orders of magnitude faster computation and three
orders of magnitude lower memory footprint.