mlsanityData to 7 Oct 2026

Subquadratic Kronecker Regression with Applications to Tensor Decomposition

arXiv 2209.04876 ↗First posted 11 Sep 2022cs.DS cs.LG math.STcited by 6

Not on the map. Why?

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.

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

Builds on

29 of 73 references.

References · 29

  1. 2014Sketching as a Tool for Numerical Linear Algebracited by 285
  2. 2016Tensor Decomposition for Signal Processing and Machine Learningcited by 223
  3. 2016TensorLy: Tensor Learning in Pythoncited by 104
  4. 2020A Refined Laser Method and Faster Matrix Multiplicationcited by 56
  5. 2015Input Sparsity Time Low-Rank Approximation via Ridge Leverage Score Samplingcited by 46
  6. 2017Relative Error Tensor Low Rank Approximationcited by 45
  7. 2017Introduction to Tensor Decompositions and their Applications in Machine Learningcited by 45
  8. 2017Active Regression via Linear-Sample Sparsificationcited by 36
  9. 2014Provable Tensor Factorization with Missing Datacited by 31
  10. 2014Uniform Sampling for Matrix Approximationcited by 31
  11. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  12. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
17 more
  1. 2016Low-rank tensor completion: a Riemannian manifold preconditioning approachcited by 19
  2. 2016Sharper Bounds for Regularized Data Fittingcited by 19
  3. 2019Low-Rank Tucker Approximation of a Tensor From Streaming Datacited by 15
  4. 2020Tensor Completion Made Practicalcited by 15
  5. 2017Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averagingcited by 13
  6. 2017Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensorcited by 13
  7. 2016Learning from Multiway Data: Simple and Efficient Tensor Regressioncited by 11
  8. 2021Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositionscited by 11
  9. 2020Optimization Landscape of Tucker Decompositioncited by 10
  10. 2017A dual framework for low-rank tensor completioncited by 9
  11. 2018Ridge Regression and Provable Deterministic Ridge Leverage Score Samplingcited by 9
  12. 2014Decomposition of Big Tensors With Low Multilinear Rankcited by 7
  13. 2021Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Samplingcited by 5
  14. 2022Sketching Algorithms and Lower Bounds for Ridge Regressioncited by 4
  15. 2022Revisiting Approximate Leverage Score Sketching for Matrix Least Squarescited by 3
  16. 2019Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Timecited by 2
  17. 2021A rank-adaptive higher-order orthogonal iteration algorithm for truncated Tucker decompositioncited by 2

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 2; 2024: 0; 2025: 2.

6 papers.

  1. 2022Dynamic Tensor Product Regressioncited by 17
  2. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  3. 2023Approximately Optimal Core Shapes for Tensor Decompositionscited by 8
  4. 2022Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networkscited by 2
  5. 2025Fast Tensor Completion via Approximate Richardson Iterationcited by 0
  6. 2025A Tight Lower Bound for the Approximation Guarantee of Higher-Order Singular Value Decompositioncited by 0