FAST REGRESSION FOR STRUCTURED INPUTS

We study the ℓ_p regression problem, which requires finding x ∈ ℝ^d that minimizes ǁAx − bǁ_p for a matrix A ∈ ℝⁿ×^d and response vector b ∈ ℝⁿ. 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, d^O(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(n log³ n + (dp²)^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 `<sub>∞</sub> regression, via approximation of ℓ<sub>∞</sub> by ℓ<sub>O</sub>(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.