The authors analyze the Fastfood feature map of Le, Sarlós, and Smola (ICML 2013), which approximates a Gaussian kernel by applying a series of structured random matrices—including a randomized Hadamard transform—to compute m random features in O((d+m)log d) time rather than the O(md) time of standard random Fourier features (RFF).
Near-linear time random Fourier features with strong concentration guarantees
New analysis of the Fastfood feature map proves it can achieve subgaussian concentration while running in O((d+m)log d) time.
Big Tech
Sepideh Mahabadi · Sandeep Silwal · Tal Wagner
Microsoft Research · University of Wisconsin-Madison · Tel Aviv University
Research Digest··3 min read
The authors revisit the Fastfood random feature map for shift-invariant kernels, known to be computable in near-linear time but previously thought to give weak concentration.
Why this paper
From Microsoft Research and 2 others
In one line
Random Fourier features for shift-invariant kernels can be computed in near-linear time with near-subgaussian concentration.
What we could check
- ·No code link found
- ·No weights link found
- ·No dataset link found
- ·No compute details found
- ·No stated limitations found
- ·No benchmark numbers found
Observed from the paper text and links we have. Absence here means we did not find it, not that it does not exist.
§