# Subquadratic Kronecker Regression with Applications to Tensor Decomposition

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 73 references that are in the map.
- First posted on arXiv 11 Sep 2022.

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

- [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)
- [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)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [Active Regression via Linear-Sample Sparsification](https://mlsanity.com/paper/1711.10051/) (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)
- [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)
- [Tensor Completion Made Practical](https://mlsanity.com/paper/2006.03134/) (2020)
- [Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging](https://mlsanity.com/paper/1702.04837/) (2017)
- [Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor](https://mlsanity.com/paper/1708.05622/) (2017)
- [Learning from Multiway Data: Simple and Efficient Tensor Regression](https://mlsanity.com/paper/1607.02535/) (2016)
- [Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions](https://mlsanity.com/paper/2104.01101/) (2021)
- [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)
- [Decomposition of Big Tensors With Low Multilinear Rank](https://mlsanity.com/paper/1412.1885/) (2014)
- [Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling](https://mlsanity.com/paper/2107.10654/) (2021)
- [Sketching Algorithms and Lower Bounds for Ridge Regression](https://mlsanity.com/paper/2204.06653/) (2022)
- [Revisiting Approximate Leverage Score Sketching for Matrix Least Squares](https://mlsanity.com/paper/2201.10638/) (2022)
- [Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time](https://mlsanity.com/paper/1909.10850/) (2019)
- [A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decomposition](https://mlsanity.com/paper/2110.12564/) (2021)

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

- [Dynamic Tensor Product Regression](https://mlsanity.com/paper/2210.03961/) (2022)
- [A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guarantee](https://mlsanity.com/paper/2302.00248/) (2023)
- [Approximately Optimal Core Shapes for Tensor Decompositions](https://mlsanity.com/paper/2302.03886/) (2023)
- [Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks](https://mlsanity.com/paper/2210.03828/) (2022)
- [Fast Tensor Completion via Approximate Richardson Iteration](https://mlsanity.com/paper/2502.09534/) (2025)
- [A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decomposition](https://mlsanity.com/paper/2508.06693/) (2025)

## Abstract (arXiv)

Kronecker regression is a highly-structured least squares problem minx lVert Kx - b rVert22, where the design matrix K = A(1) otimes cdots otimes A(N) is a Kronecker product of factor matrices. This regression problem arises in each step of the widely-used alternating least squares (ALS) algorithm for computing the Tucker decomposition of a tensor. We present the first subquadratic-time algorithm for solving Kronecker regression to a (1+varepsilon)-approximation that avoids the exponential term O(varepsilon-N) in the running time. Our techniques combine leverage score sampling and iterative methods. By extending our approach to block-design matrices where one block is a Kronecker product, we also achieve subquadratic-time algorithms for (1) Kronecker ridge regression and (2) updating the factor matrices of a Tucker decomposition in ALS, which is not a pure Kronecker regression problem, thereby improving the running time of all steps of Tucker ALS. We demonstrate the speed and accuracy of this Kronecker regression algorithm on synthetic data and real-world image tensors.