# Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 85 references that are in the map.
- First posted on arXiv 13 May 2025.

## Builds on (most cited first, 30 of 33)

- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding](https://mlsanity.com/paper/1606.01847/) (2016)
- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Katyusha: The First Direct Acceleration of Stochastic Gradient Methods](https://mlsanity.com/paper/1603.05953/) (2016)
- [Random Features for Kernel Approximation: A Survey on Algorithms, Theory, and Beyond](https://mlsanity.com/paper/2004.11154/) (2020)
- [On the Power and Limitations of Random Features for Understanding Neural Networks](https://mlsanity.com/paper/1904.00687/) (2019)
- [Compact Bilinear Pooling](https://mlsanity.com/paper/1511.06062/) (2015)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [Learning to Evaluate Image Captioning](https://mlsanity.com/paper/1806.06422/) (2018)
- [Acceleration Methods](https://mlsanity.com/paper/2101.09545/) (2021)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Faster Kernel Ridge Regression Using Sketching and Preconditioning](https://mlsanity.com/paper/1611.03220/) (2016)
- [What can a Single Attention Layer Learn? A Study Through the Random Features Lens](https://mlsanity.com/paper/2307.11353/) (2023)
- [Optimal Rates for Random Fourier Features](https://mlsanity.com/paper/1506.02155/) (2015)
- [Hashing-Based-Estimators for Kernel Density in High Dimensions](https://mlsanity.com/paper/1808.10530/) (2018)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [High-Order Attention Models for Visual Question Answering](https://mlsanity.com/paper/1711.04323/) (2017)
- [Fast and Guaranteed Tensor Decomposition via Sketching](https://mlsanity.com/paper/1506.04448/) (2015)
- [Randomized Nonlinear Component Analysis](https://mlsanity.com/paper/1402.0119/) (2014)
- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [Compact Random Feature Maps](https://mlsanity.com/paper/1312.4626/) (2013)
- [Random Fourier Features via Fast Surrogate Leverage Weighted Sampling](https://mlsanity.com/paper/1911.09158/) (2019)
- [Scalable Spectral Clustering Using Random Binning Features](https://mlsanity.com/paper/1805.11048/) (2018)

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

- [Step-resolved data attribution for looped transformers](https://mlsanity.com/paper/2602.10097/) (2026)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [Improving TensorSketch Using Complex Random Variables](https://mlsanity.com/paper/2608.10523/) (2026)
- [Accurate Trace Estimation with Fewer Random Bits via Recursive TensorSketch](https://mlsanity.com/paper/2609.18577/) (2026)

## Abstract (arXiv)

Approximation of non-linear kernels using random feature maps has become a powerful technique for scaling kernel methods to large datasets. We propose textitTensor Sketch, an efficient random feature map for approximating polynomial kernels. Given n training samples in ℝd Tensor Sketch computes low-dimensional embeddings in ℝD in time Oleft( n(d+D logD) right) making it well-suited for high-dimensional and large-scale settings. We provide theoretical guarantees on the approximation error, ensuring the fidelity of the resulting kernel function estimates. We also discuss extensions and highlight applications where Tensor Sketch serves as a central computational tool.