# Optimal Sketching for Kronecker Product Regression and Low Rank Approximation

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

## Key facts

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

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

- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [In-Context Learning for Attention Scheme: from Single Softmax Regression to Multiple Softmax Regression via a Tensor Trick](https://mlsanity.com/paper/2307.02419/) (2023)
- [Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time](https://mlsanity.com/paper/2302.11068/) (2023)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time](https://mlsanity.com/paper/2309.07418/) (2023)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [GradientCoin: A Peer-to-Peer Decentralized Large Language Models](https://mlsanity.com/paper/2308.10502/) (2023)
- [Solving Attention Kernel Regression Problem via Pre-conditioner](https://mlsanity.com/paper/2308.14304/) (2023)
- [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)
- [Efficient SGD Neural Network Training via Sublinear Activated Neuron Identification](https://mlsanity.com/paper/2307.06565/) (2023)
- [Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation](https://mlsanity.com/paper/2306.04169/) (2023)
- [Solving Tensor Low Cycle Rank Approximation](https://mlsanity.com/paper/2304.06594/) (2023)
- [More Efficient Sampling for Tensor Decomposition With Worst-Case Guarantees](https://mlsanity.com/paper/2110.07631/) (2021)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Subquadratic Kronecker Regression with Applications to Tensor Decomposition](https://mlsanity.com/paper/2209.04876/) (2022)
- [Fast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling](https://mlsanity.com/paper/2107.10654/) (2021)
- [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)
- [Fast Graph Neural Tangent Kernel via Kronecker Sketching](https://mlsanity.com/paper/2112.02446/) (2021)
- [Log-concave Sampling from a Convex Body with a Barrier: a Robust and Unified Dikin Walk](https://mlsanity.com/paper/2410.05700/) (2024)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [Efficient Tensor Contraction via Fast Count Sketch](https://mlsanity.com/paper/2106.13062/) (2021)
- [Online Adaptive Mahalanobis Distance Estimation](https://mlsanity.com/paper/2309.01030/) (2023)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)
- [Fast Tensor Completion via Approximate Richardson Iteration](https://mlsanity.com/paper/2502.09534/) (2025)

## 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.