# Compact Random Feature Maps

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Dec 2013.

## Built on by (most cited first, 12 of 12)

- [Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding](https://mlsanity.com/paper/2106.02795/) (2021)
- [Nonparametric Modern Hopfield Models](https://mlsanity.com/paper/2404.03900/) (2024)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)
- [Dense Associative Memory Through the Lens of Random Features](https://mlsanity.com/paper/2410.24153/) (2024)
- [Hyperparameter Optimization for Randomized Algorithms: A Case Study on Random Features](https://mlsanity.com/paper/2407.00584/) (2024)
- [Local Random Feature Approximations of the Gaussian Kernel](https://mlsanity.com/paper/2204.05667/) (2022)
- [Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel](https://mlsanity.com/paper/2202.02031/) (2022)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Randomly Initialized Subnetworks with Iterative Weight Recycling](https://mlsanity.com/paper/2303.15953/) (2023)
- [Forward Operator Estimation in Generative Models with Kernel Transfer Operators](https://mlsanity.com/paper/2112.00305/) (2021)
- [An Exact Finite-dimensional Explicit Feature Map for Kernel Functions](https://mlsanity.com/paper/2410.12635/) (2024)
- [Nonlinear Principal Component Analysis with Random Bernoulli Features for Process Monitoring](https://mlsanity.com/paper/2503.12456/) (2025)

## Abstract (arXiv)

Kernel approximation using randomized feature maps has recently gained a lot of interest. In this work, we identify that previous approaches for polynomial kernel approximation create maps that are rank deficient, and therefore do not utilize the capacity of the projected feature space effectively. To address this challenge, we propose compact random feature maps (CRAFTMaps) to approximate polynomial kernels more concisely and accurately. We prove the error bounds of CRAFTMaps demonstrating their superior kernel reconstruction performance compared to the previous approximation schemes. We show how structured random matrices can be used to efficiently generate CRAFTMaps, and present a single-pass algorithm using CRAFTMaps to learn non-linear multi-class classifiers. We present experiments on multiple standard data-sets with performance competitive with state-of-the-art results.