Fourier Sparse Leverage Scores and Approximate Kernel Learning

Tamás Erdélyi, Cameron Musco, Christopher Musco

We prove new explicit upper bounds on the leverage scores of Fourier sparse functions under both the Gaussian and Laplace measures. In particular, we study $s$-sparse functions of…