# Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 73 references that are in the map.
- First posted on arXiv 2 Apr 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares](https://mlsanity.com/paper/1411.0347/) (2014)
- [Sketching for Kronecker Product Regression and P-splines](https://mlsanity.com/paper/1712.09473/) (2017)
- [Sharper Bounds for Regularized Data Fitting](https://mlsanity.com/paper/1611.03225/) (2016)
- [Low-Rank Tucker Approximation of a Tensor From Streaming Data](https://mlsanity.com/paper/1904.10951/) (2019)
- [Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries](https://mlsanity.com/paper/1710.02261/) (2017)
- [Provable Deterministic Leverage Score Sampling](https://mlsanity.com/paper/1404.1530/) (2014)
- [Decomposition of Big Tensors With Low Multilinear Rank](https://mlsanity.com/paper/1412.1885/) (2014)
- [A Practical Guide to Randomized Matrix Computations with MATLAB Implementations](https://mlsanity.com/paper/1505.07570/) (2015)
- [Load-Balanced Sparse MTTKRP on GPUs](https://mlsanity.com/paper/1904.03329/) (2019)
- [Efficient parallel CP decomposition with pairwise perturbation and multi-sweep dimension tree](https://mlsanity.com/paper/2010.12056/) (2020)
- [Nesterov Acceleration of Alternating Least Squares for Canonical Tensor Decomposition: Momentum Step Size Selection and Restart Mechanisms](https://mlsanity.com/paper/1810.05846/) (2018)
- [SGD_Tucker: A Novel Stochastic Optimization Strategy for Parallel Sparse Tucker Decomposition](https://mlsanity.com/paper/2012.03550/) (2020)

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

- [Matrix Compression via Randomized Low Rank and Low Precision Factorization](https://mlsanity.com/paper/2310.11028/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [Approximately Optimal Core Shapes for Tensor Decompositions](https://mlsanity.com/paper/2302.03886/) (2023)
- [ATD: Augmenting CP Tensor Decomposition by Self Supervision](https://mlsanity.com/paper/2106.07900/) (2021)
- [Nonconvex Robust High-Order Tensor Completion Using Randomized Low-Rank Approximation](https://mlsanity.com/paper/2305.11495/) (2023)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs](https://mlsanity.com/paper/2205.13163/) (2022)
- [Enabling All In-Edge Deep Learning: A Literature Review](https://mlsanity.com/paper/2204.03326/) (2022)
- [A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition](https://mlsanity.com/paper/2110.12564/) (2021)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)
- [Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iteration](https://mlsanity.com/paper/2211.14828/) (2022)

## Abstract (arXiv)

Low-rank Tucker and CP tensor decompositions are powerful tools in data analytics. The widely used alternating least squares (ALS) method, which solves a sequence of over-determined least squares subproblems, is costly for large and sparse tensors. We propose a fast and accurate sketched ALS algorithm for Tucker decomposition, which solves a sequence of sketched rank-constrained linear least squares subproblems. Theoretical sketch size upper bounds are provided to achieve O(ε) relative error for each subproblem with two sketching techniques, TensorSketch and leverage score sampling. Experimental results show that this new ALS algorithm, combined with a new initialization scheme based on randomized range finder, yields up to 22.0% relative decomposition residual improvement compared to the state-of-the-art sketched randomized algorithm for Tucker decomposition of various synthetic and real datasets. This Tucker-ALS algorithm is further used to accelerate CP decomposition, by using randomized Tucker compression followed by CP decomposition of the Tucker core tensor. Experimental results show that this algorithm not only converges faster, but also yields more accurate CP decompositions.