# Improving TensorSketch Using Complex Random Variables

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 31 references that are in the map.
- First posted on arXiv 11 Aug 2026.

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

- [Multimodal Compact Bilinear Pooling for Visual Question Answering and Visual Grounding](https://mlsanity.com/paper/1606.01847/) (2016)
- [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)
- [Scaling Neural Tangent Kernels via Sketching and Random Features](https://mlsanity.com/paper/2106.07880/) (2021)
- [But How Does It Work in Theory? Linear SVM with Random Features](https://mlsanity.com/paper/1809.04481/) (2018)
- [Improved Random Features for Dot Product Kernels](https://mlsanity.com/paper/2201.08712/) (2022)
- [Complex-to-Real Sketches for Tensor Products with Applications to the Polynomial Kernel](https://mlsanity.com/paper/2202.02031/) (2022)
- [Hutchinson's Estimator is Bad at Kronecker-Trace-Estimation](https://mlsanity.com/paper/2309.04952/) (2023)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Improving textitTug-of-War sketch using Control-Variates method](https://mlsanity.com/paper/2203.02432/) (2022)

## Abstract (arXiv)

textttTensorSketch by~citepham2013fast,kar2012random provides efficient sketching algorithms for high-dimensional polynomial kernels vecxotimes p ∈ Rdp. citekar2012random uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost O(pDd), where D denotes the sketch dimension, whereas~citepham2013fast extends the sparse textttCountSketch~citepcountsketch algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time Obig(p(nnzvecx + D log D)big). However, the variance of both estimators grows exponentially with the polynomial degree p, scaling as 3p/D. Recent work by~citepmlr-v206-wacker23a showed that using complex-valued distribution reduces this dependence to 2p/D for the approach of~citekar2012random. However, their method relies on dense JL-type projections with computational cost O(pDd) and does not extend to the algorithm of~citepham2013fast. In this work, we introduce a simple variant of textttTensorSketch~citeppham2013fast that achieves the same variance bound as~citepmlr-v206-wacker23a, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.