# Near Optimal Sketching of Low-Rank Tensor Regression

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

## Key facts

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

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

- [Fast Sketching of Polynomial Kernels of Polynomial Degree](https://mlsanity.com/paper/2108.09420/) (2021)
- [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)
- [Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning](https://mlsanity.com/paper/2406.11151/) (2024)
- [Is Solving Graph Neural Tangent Kernel Equivalent to Training Graph Neural Network?](https://mlsanity.com/paper/2309.07452/) (2023)
- [Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications](https://mlsanity.com/paper/2311.05116/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [SliceNStitch: Continuous CP Decomposition of Sparse Tensor Streams](https://mlsanity.com/paper/2102.11517/) (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)

## Abstract (arXiv)

We study the least squares regression problem beginalign* min_Theta ∈ Sodot D,R |ATheta-b|2, endalign* where Sodot D,R is the set of Theta for which Theta = sumr=1R θ1(r) circ cdots circ θD(r) for vectors θd(r) ∈ ℝpd for all r ∈ [R] and d ∈ [D], and circ denotes the outer product of vectors. That is, Theta is a low-dimensional, low-rank tensor. This is motivated by the fact that the number of parameters in Theta is only R · sumd=1D pd, which is significantly smaller than the prodd=1D pd number of parameters in ordinary least squares regression. We consider the above CP decomposition model of tensors Theta, as well as the Tucker decomposition. For both models we show how to apply data dimensionality reduction techniques based on it sparse random projections Phi ∈ ℝm × n, with m ll n, to reduce the problem to a much smaller problem minTheta |Phi A Theta - Phi b|2, for which if Theta' is a near-optimum to the smaller problem, then it is also a near optimum to the original problem. We obtain significantly smaller dimension and sparsity in Phi than is possible for ordinary least squares regression, and we also provide a number of numerical simulations supporting our theory.