# Efficient Tensor Contraction via Fast Count Sketch

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 40 references that are in the map.
- First posted on arXiv 24 Jun 2021.

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

- [Fashion-MNIST: a Novel Image Dataset for Benchmarking Machine Learning Algorithms](https://mlsanity.com/paper/1708.07747/) (2017)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Regression Networks](https://mlsanity.com/paper/1707.08308/) (2017)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [Optimal Sketching for Kronecker Product Regression and Low Rank Approximation](https://mlsanity.com/paper/1909.13384/) (2019)
- [Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates](https://mlsanity.com/paper/1402.5180/) (2014)
- [Bayesian Tensor Regression](https://mlsanity.com/paper/1509.06490/) (2015)
- [Fast and Guaranteed Tensor Decomposition via Sketching](https://mlsanity.com/paper/1506.04448/) (2015)
- [Low-Rank Tucker Approximation of a Tensor From Streaming Data](https://mlsanity.com/paper/1904.10951/) (2019)
- [Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction](https://mlsanity.com/paper/1901.01652/) (2019)
- [Tensorized Random Projections](https://mlsanity.com/paper/2003.05101/) (2020)
- [Tensor Regression Networks with various Low-Rank Tensor Approximations](https://mlsanity.com/paper/1712.09520/) (2017)
- [Provable Tensor Ring Completion](https://mlsanity.com/paper/1903.03315/) (2019)
- [Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix](https://mlsanity.com/paper/1905.11616/) (2019)

## Abstract (arXiv)

Sketching uses randomized Hash functions for dimensionality reduction and acceleration. The existing sketching methods, such as count sketch (CS), tensor sketch (TS), and higher-order count sketch (HCS), either suffer from low accuracy or slow speed in some tensor based applications. In this paper, the proposed fast count sketch (FCS) applies multiple shorter Hash functions based CS to the vector form of the input tensor, which is more accurate than TS since the spatial information of the input tensor can be preserved more sufficiently. When the input tensor admits CANDECOMP/PARAFAC decomposition (CPD), FCS can accelerate CS and HCS by using fast Fourier transform, which exhibits a computational complexity asymptotically identical to TS for low-order tensors. The effectiveness of FCS is validated by CPD, tensor regression network compression, and Kronecker product compression. Experimental results show its superior performance in terms of approximation accuracy and computational efficiency.