# Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 35 references that are in the map.
- First posted on arXiv 4 Feb 2022.

## Builds on (most cited first, 12 of 12)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [ImageNet Large Scale Visual Recognition Challenge](https://mlsanity.com/paper/1409.0575/) (2014)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Return of the Devil in the Details: Delving Deep into Convolutional Nets](https://mlsanity.com/paper/1405.3531/) (2014)
- [Compact Bilinear Pooling](https://mlsanity.com/paper/1511.06062/) (2015)
- [Random Fourier Features for Kernel Ridge Regression: Approximation Bounds and Statistical Guarantees](https://mlsanity.com/paper/1804.09893/) (2018)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)
- [Optimality of the Johnson-Lindenstrauss Lemma](https://mlsanity.com/paper/1609.02094/) (2016)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [Compact Random Feature Maps](https://mlsanity.com/paper/1312.4626/) (2013)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)

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

- [Tanimoto Random Features for Scalable Molecular Machine Learning](https://mlsanity.com/paper/2306.14809/) (2023)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [Improving TensorSketch Using Complex Random Variables](https://mlsanity.com/paper/2608.10523/) (2026)
- [Rationally Linearized MLPs](https://mlsanity.com/paper/2610.13568/) (2026)

## Abstract (arXiv)

Randomized sketches of a tensor product of p vectors follow a tradeoff between statistical efficiency and computational acceleration. Commonly used approaches avoid computing the high-dimensional tensor product explicitly, resulting in a suboptimal dependence of O(3p) in the embedding dimension. We propose a simple Complex-to-Real (CtR) modification of well-known sketches that replaces real random projections by complex ones, incurring a lower O(2p) factor in the embedding dimension. The output of our sketches is real-valued, which renders their downstream use straightforward. In particular, we apply our sketches to p-fold self-tensored inputs corresponding to the feature maps of the polynomial kernel. We show that our method achieves state-of-the-art performance in terms of accuracy and speed compared to other randomized approximations from the literature.