# Faster p-Norm Regression Using Sparsity

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

## Key facts

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

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

- [Query Complexity of Active Learning for Function Family With Nearly Orthogonal Basis](https://mlsanity.com/paper/2306.03356/) (2023)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)

## Abstract (arXiv)

For a matrix A∈ ℝn× d with n≥ d, we consider the dual problems of min |Ax-b|pp, , b∈ ℝn and minA^top x=b |x|pp,, b∈ ℝd. We improve the runtimes for solving these problems to high accuracy for every p>1 for sufficiently sparse matrices. We show that recent progress on fast sparse linear solvers can be leveraged to obtain faster than matrix-multiplication algorithms for any p > 1, i.e., in time tildeO(pnθ) for some θ < ω, the matrix multiplication constant. We give the first high-accuracy input sparsity p-norm regression algorithm for solving min |Ax-b|pp with 1 < p ≤ 2, via a new row sampling theorem for the smoothed p-norm function. This algorithm runs in time tildeO(nnz(A) + d4) for any 1<p≤ 2, and in time tildeO(nnz(A) + dθ) for p close to 2, improving on the previous best bound where the exponent of d grows with maxp, p/(p-1).