# Fast and Guaranteed Tensor Decomposition via Sketching

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Jun 2015.

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

- [Reconstructing Training Data from Model Gradient, Provably](https://mlsanity.com/paper/2212.03714/) (2022)
- [Sketch-GNN: Scalable Graph Neural Networks with Sublinear Training Complexity](https://mlsanity.com/paper/2406.15575/) (2024)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [Tensor Random Projection for Low Memory Dimension Reduction](https://mlsanity.com/paper/2105.00105/) (2021)
- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Nonconvex Robust High-Order Tensor Completion Using Randomized Low-Rank Approximation](https://mlsanity.com/paper/2305.11495/) (2023)
- [Probabilistic methods for approximate archetypal analysis](https://mlsanity.com/paper/2108.05767/) (2021)
- [DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors](https://mlsanity.com/paper/2203.12798/) (2022)
- [Tensor Sketch: Fast and Scalable Polynomial Kernel Approximation](https://mlsanity.com/paper/2505.08146/) (2025)
- [Canonical convolutional neural networks](https://mlsanity.com/paper/2206.01509/) (2022)
- [Comfetch: Federated Learning of Large Networks on Constrained Clients via Sketching](https://mlsanity.com/paper/2109.08346/) (2021)
- [Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions](https://mlsanity.com/paper/2108.10129/) (2021)
- [Defensive Tensorization](https://mlsanity.com/paper/2110.13859/) (2021)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [Efficient Tensor Contraction via Fast Count Sketch](https://mlsanity.com/paper/2106.13062/) (2021)
- [Sample Efficient Learning of Factored Embeddings of Tensor Fields](https://mlsanity.com/paper/2209.00372/) (2022)
- [Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iteration](https://mlsanity.com/paper/2211.14828/) (2022)
- [Combining Monte Carlo and Tensor-network Methods for Partial Differential Equations via Sketching](https://mlsanity.com/paper/2305.17884/) (2023)

## Abstract (arXiv)

Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in statistical learning of latent variable models and in data mining. In this paper, we propose fast and randomized tensor CP decomposition algorithms based on sketching. We build on the idea of count sketches, but introduce many novel ideas which are unique to tensors. We develop novel methods for randomized computation of tensor contractions via FFTs, without explicitly forming the tensors. Such tensor contractions are encountered in decomposition methods such as tensor power iterations and alternating least squares. We also design novel colliding hashes for symmetric tensors to further save time in computing the sketches. We then combine these sketching ideas with existing whitening and tensor power iterative techniques to obtain the fastest algorithm on both sparse and dense tensors. The quality of approximation under our method does not depend on properties such as sparsity, uniformity of elements, etc. We apply the method for topic modeling and obtain competitive results.