# Fastfood: Approximate Kernel Expansions in Loglinear Time

arXiv: https://arxiv.org/abs/1408.3060 · HTML: https://mlsanity.com/paper/1408.3060/

## Key facts

- Cited by 74 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2014.

## Built on by (most cited first, 30 of 74)

- [Compacter: Efficient Low-Rank Hypercomplex Adapter Layers](https://mlsanity.com/paper/2106.04647/) (2021)
- [Knowledge Editing for Large Language Models: A Survey](https://mlsanity.com/paper/2310.16218/) (2023)
- [Scaling Down to Scale Up: A Guide to Parameter-Efficient Fine-Tuning](https://mlsanity.com/paper/2303.15647/) (2023)
- [Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding](https://mlsanity.com/paper/2106.02795/) (2021)
- [Modular Deep Learning](https://mlsanity.com/paper/2302.11529/) (2023)
- [Parameter-efficient Model Adaptation for Vision Transformers](https://mlsanity.com/paper/2203.16329/) (2022)
- [PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization](https://mlsanity.com/paper/2211.13609/) (2022)
- [VB-LoRA: Extreme Parameter Efficient Fine-Tuning with Vector Banks](https://mlsanity.com/paper/2405.15179/) (2024)
- [Exploring Universal Intrinsic Task Subspace via Prompt Tuning](https://mlsanity.com/paper/2110.07867/) (2021)
- [FrameQuant: Flexible Low-Bit Quantization for Transformers](https://mlsanity.com/paper/2403.06082/) (2024)
- [Learning with Density Matrices and Random Features](https://mlsanity.com/paper/2102.04394/) (2021)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [DiJiang: Efficient Large Language Models through Compact Kernelization](https://mlsanity.com/paper/2403.19928/) (2024)
- [Random Representations Outperform Online Continually Learned Representations](https://mlsanity.com/paper/2402.08823/) (2024)
- [A Call for Clarity in Beam Search: How It Works and When It Stops](https://mlsanity.com/paper/2204.05424/) (2022)
- [Low-Precision Arithmetic for Fast Gaussian Processes](https://mlsanity.com/paper/2207.06856/) (2022)
- [Localized Contrastive Learning on Graphs](https://mlsanity.com/paper/2212.04604/) (2022)
- [Efficient Sketches for Training Data Attribution and Studying the Loss Landscape](https://mlsanity.com/paper/2402.03994/) (2024)
- [SuperLoRA: Parameter-Efficient Unified Adaptation of Multi-Layer Attention Modules](https://mlsanity.com/paper/2403.11887/) (2024)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Deformable Butterfly: A Highly Structured and Sparse Linear Transform](https://mlsanity.com/paper/2203.13556/) (2022)
- [Bayesian Disturbance Injection: Robust Imitation Learning of Flexible Policies for Robot Manipulation](https://mlsanity.com/paper/2211.03393/) (2022)
- [LookupFFN: Making Transformers Compute-lite for CPU inference](https://mlsanity.com/paper/2403.07221/) (2024)
- [Provable Quantization with Randomized Hadamard Transform](https://mlsanity.com/paper/2605.13810/) (2026)
- [Hyperparameter Optimization for Randomized Algorithms: A Case Study on Random Features](https://mlsanity.com/paper/2407.00584/) (2024)
- [Uni-LoRA: One Vector is All You Need](https://mlsanity.com/paper/2506.00799/) (2025)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [Faster Kernel Interpolation for Gaussian Processes](https://mlsanity.com/paper/2101.11751/) (2021)
- [Nearest Neighbor Sampling for Covariate Shift Adaptation](https://mlsanity.com/paper/2312.09969/) (2023)
- [Motion Attribution for Video Generation](https://mlsanity.com/paper/2601.08828/) (2026)

## Abstract (arXiv)

Despite their successes, what makes kernel methods difficult to use in many large scale problems is the fact that storing and computing the decision function is typically expensive, especially at prediction time. In this paper, we overcome this difficulty by proposing Fastfood, an approximation that accelerates such computation significantly. Key to Fastfood is the observation that Hadamard matrices, when combined with diagonal Gaussian matrices, exhibit properties similar to dense Gaussian random matrices. Yet unlike the latter, Hadamard and diagonal matrices are inexpensive to multiply and store. These two matrices can be used in lieu of Gaussian matrices in Random Kitchen Sinks proposed by Rahimi and Recht (2009) and thereby speeding up the computation for a large range of kernel functions. Specifically, Fastfood requires O(n log d) time and O(n) storage to compute n non-linear basis functions in d dimensions, a significant improvement from O(nd) computation and storage, without sacrificing accuracy. Our method applies to any translation invariant and any dot-product kernel, such as the popular RBF kernels and polynomial kernels. We prove that the approximation is unbiased and has low variance. Experiments show that we achieve similar accuracy to full kernel expansions and Random Kitchen Sinks while being 100x faster and using 1000x less memory. These improvements, especially in terms of memory usage, make kernel methods more practical for applications that have large training sets and/or require real-time prediction.