# Sublinear Time Numerical Linear Algebra for Structured Matrices

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

## Key facts

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

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

- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions](https://mlsanity.com/paper/2207.07417/) (2022)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Ridge Leverage Score Sampling for ℓp Subspace Approximation](https://mlsanity.com/paper/2407.03262/) (2024)
- [Toeplitz Least Squares Problems, Fast Algorithms and Big Data](https://mlsanity.com/paper/2112.12994/) (2021)

## Abstract (arXiv)

We show how to solve a number of problems in numerical linear algebra, such as least squares regression, ℓp-regression for any p ≥ 1, low rank approximation, and kernel regression, in time T(A) poly(log(nd)), where for a given input matrix A ∈ ℝn × d, T(A) is the time needed to compute A· y for an arbitrary vector y ∈ ℝd. Since T(A) ≤ O(nnz(A)), where nnz(A) denotes the number of non-zero entries of A, the time is no worse, up to polylogarithmic factors, as all of the recent advances for such problems that run in input-sparsity time. However, for many applications, T(A) can be much smaller than nnz(A), yielding significantly sublinear time algorithms. For example, in the overconstrained (1+ε)-approximate polynomial interpolation problem, A is a Vandermonde matrix and T(A) = O(n log n); in this case our running time is n · poly(log n) + poly(d/ε) and we recover the results of citeavron2013sketching as a special case. For overconstrained autoregression, which is a common problem arising in dynamical systems, T(A) = O(n log n), and we immediately obtain n · poly(log n) + poly(d/ε) time. For kernel autoregression, we significantly improve the running time of prior algorithms for general kernels. For the important case of autoregression with the polynomial kernel and arbitrary target vector b∈ℝn, we obtain even faster algorithms. Our algorithms show that, perhaps surprisingly, most of these optimization problems do not require much more time than that of a polylogarithmic number of matrix-vector multiplications.