large-scale kernel approximation is an important problem in machine learning research. Approaches using random fourier features have become increasingly popular [Rahimi and Recht, 2007], where kernel approximatio