# Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 41 references that are in the map.
- First posted on arXiv 22 Jul 2021.

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

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition](https://mlsanity.com/paper/1503.02101/) (2015)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [A Refined Laser Method and Faster Matrix Multiplication](https://mlsanity.com/paper/2010.05846/) (2020)
- [Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Sampling](https://mlsanity.com/paper/1511.07263/) (2015)
- [Introduction to Tensor Decompositions and their Applications in Machine Learning](https://mlsanity.com/paper/1711.10781/) (2017)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Uniform Sampling for Matrix Approximation](https://mlsanity.com/paper/1408.5099/) (2014)
- [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)
- [Low-rank tensor completion: a Riemannian manifold preconditioning approach](https://mlsanity.com/paper/1605.08257/) (2016)
- [Tensor Completion Made Practical](https://mlsanity.com/paper/2006.03134/) (2020)
- [Learning from Multiway Data: Simple and Efficient Tensor Regression](https://mlsanity.com/paper/1607.02535/) (2016)
- [Optimization Landscape of Tucker Decomposition](https://mlsanity.com/paper/2006.16297/) (2020)
- [A dual framework for low-rank tensor completion](https://mlsanity.com/paper/1712.01193/) (2017)
- [Ridge Regression and Provable Deterministic Ridge Leverage Score Sampling](https://mlsanity.com/paper/1803.06010/) (2018)

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

- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions](https://mlsanity.com/paper/2207.07417/) (2022)
- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [Gradient Coding with Iterative Block Leverage Score Sampling](https://mlsanity.com/paper/2308.03096/) (2023)

## Abstract (arXiv)

Low-rank tensor decomposition generalizes low-rank matrix approximation and is a powerful technique for discovering low-dimensional structure in high-dimensional data. In this paper, we study Tucker decompositions and use tools from randomized numerical linear algebra called ridge leverage scores to accelerate the core tensor update step in the widely-used alternating least squares (ALS) algorithm. Updating the core tensor, a severe bottleneck in ALS, is a highly-structured ridge regression problem where the design matrix is a Kronecker product of the factor matrices. We show how to use approximate ridge leverage scores to construct a sketched instance for any ridge regression problem such that the solution vector for the sketched problem is a (1+varepsilon)-approximation to the original instance. Moreover, we show that classical leverage scores suffice as an approximation, which then allows us to exploit the Kronecker structure and update the core tensor in time that depends predominantly on the rank and the sketching parameters (i.e., sublinear in the size of the input tensor). We also give upper bounds for ridge leverage scores as rows are removed from the design matrix (e.g., if the tensor has missing entries), and we demonstrate the effectiveness of our approximate ridge regressioni algorithm for large, low-rank Tucker decompositions on both synthetic and real-world data.