mlsanityData to 14 Oct 2026

Optimal Sketching for Kronecker Product Regression and Low Rank Approximation

arXiv 1909.13384 ↗First posted 29 Sep 2019cs.DS cs.LG stat.MLcited by 29

Not on the map. Why?

Abstract (arXiv)

We study the Kronecker product regression problem, in which the design matrix is a Kronecker product of two or more matrices. Given Ai ∈ ℝni × di for i=1,2,dots,q where ni gg di for each i, and b ∈ ℝn1 n2 cdots nq, let A = A1 otimes A2 otimes cdots otimes Aq. Then for p ∈ [1,2], the goal is to find x ∈ ℝd1 cdots dq that approximately minimizes |Ax - b|p. Recently, Diao, Song, Sun, and Woodruff (AISTATS, 2018) gave an algorithm which is faster than forming the Kronecker product A Specifically, for p=2 their running time is O(sumi=1q nnz(Ai) + nnz(b)), where nnz(Ai) is the number of non-zero entries in Ai. Note that nnz(b) can be as large as n1 cdots nq. For p=1, q=2 and n1 = n2, they achieve a worse bound of O(n13/2 poly(d1d2) + nnz(b)). In this work, we provide significantly faster algorithms. For p=2, our running time is O(sumi=1q nnz(Ai) ), which has no dependence on nnz(b). For p<2, our running time is O(sumi=1q nnz(Ai) + nnz(b)), which matches the prior best running time for p=2. We also consider the related all-pairs regression problem, where given A ∈ ℝn × d, b ∈ ℝn, we want to solve minx |barAx - barb|p, where barA ∈ ℝn2 × d, barb ∈ ℝn2 consist of all pairwise differences of the rows of A,b. We give an O(nnz(A)) time algorithm for p ∈[1,2], improving the Omega(n2) time needed to form barA. Finally, we initiate the study of Kronecker product low rank and low t-rank approximation. For input A as above, we give O(sumi=1q nnz(Ai)) time algorithms, which is much faster than computing A.

Key facts. Cited by 29 papers in the map (data through 14 Oct 2026). First posted on arXiv 29 Sep 2019.

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 6; 2022: 3; 2023: 13; 2024: 4; 2025: 3.

29 papers.

Sort:

  1. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  2. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  3. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  4. 2023In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trickcited by 32
  5. 2023Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Timecited by 31
  6. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  7. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  8. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  9. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  10. 2023Solving Attention Kernel Regression Problem via Pre-conditionercited by 20
  11. 2022Dynamic Tensor Product Regressioncited by 17
  12. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
17 more
  1. 2023Efficient SGD Neural Network Training via Sublinear Activated Neuron Identificationcited by 11
  2. 2023Efficient Alternating Minimization with Applications to Weighted Low Rank Approximationcited by 9
  3. 2023Solving Tensor Low Cycle Rank Approximationcited by 8
  4. 2021More Efficient Sampling for Tensor Decomposition With Worst-Case Guaranteescited by 7
  5. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  6. 2022Subquadratic Kronecker Regression with Applications to Tensor Decompositioncited by 6
  7. 2021Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Samplingcited by 5
  8. 2022Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositionscited by 4
  9. 2023Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basiscited by 4
  10. 2021Fast Graph Neural Tangent Kernel via Kronecker Sketchingcited by 2
  11. 2024Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walkcited by 2
  12. 2024Quantum Speedup for Spectral Approximation of Kronecker Productscited by 1
  13. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  14. 2021Efficient Tensor Contraction via Fast Count Sketchcited by 0
  15. 2023Online Adaptive Mahalanobis Distance Estimationcited by 0
  16. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  17. 2025Fast Tensor Completion via Approximate Richardson Iterationcited by 0