# Fast Regression for Structured Inputs

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

## Key facts

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

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

- [Online Lewis Weight Sampling](https://mlsanity.com/paper/2207.08268/) (2022)
- [Provable Data Subset Selection For Efficient Neural Network Training](https://mlsanity.com/paper/2303.05151/) (2023)
- [DataS^3: Dataset Subset Selection for Specialization](https://mlsanity.com/paper/2504.16277/) (2025)
- [Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions](https://mlsanity.com/paper/2207.07417/) (2022)
- [Efficient Algorithms for Sparse Moment Problems without Separation](https://mlsanity.com/paper/2207.13008/) (2022)
- [Fast (1+varepsilon)-Approximation Algorithms for Binary Matrix Factorization](https://mlsanity.com/paper/2306.01869/) (2023)
- [On Socially Fair Low-Rank Approximation and Column Subset Selection](https://mlsanity.com/paper/2412.06063/) (2024)
- [Sharper Bounds for ℓp Sensitivity Sampling](https://mlsanity.com/paper/2306.00732/) (2023)
- [Computing Approximate ℓp Sensitivities](https://mlsanity.com/paper/2311.04158/) (2023)
- [Deterministic Coreset for Lp Subspace](https://mlsanity.com/paper/2601.00361/) (2026)
- [Fair Dataset Distillation via Cross-Group Barycenter Alignment](https://mlsanity.com/paper/2605.00185/) (2026)

## Abstract (arXiv)

We study the ℓp regression problem, which requires finding x∈mathbb Rd that minimizes |Ax-b|p for a matrix A∈mathbb Rn × d and response vector b∈mathbb Rn. There has been recent interest in developing subsampling methods for this problem that can outperform standard techniques when n is very large. However, all known subsampling approaches have run time that depends exponentially on p, typically, dO(p), which can be prohibitively expensive. We improve on this work by showing that for a large class of common structured matrices, such as combinations of low-rank matrices, sparse matrices, and Vandermonde matrices, there are subsampling based methods for ℓp regression that depend polynomially on p. For example, we give an algorithm for ℓp regression on Vandermonde matrices that runs in time O(nlog3 n+(dp2)0.5+ω·polylog,n), where ω is the exponent of matrix multiplication. The polynomial dependence on p crucially allows our algorithms to extend naturally to efficient algorithms for ℓ_∞ regression, via approximation of ℓ_∞ by ℓO(log n). Of practical interest, we also develop a new subsampling algorithm for ℓp regression for arbitrary matrices, which is simpler than previous approaches for p ≥ 4.