Faster $p$-Norm Regression Using Sparsity

Abstract

For a matrix $A\in {\mathbb{R}}^{n\times d}$ with $n\ge d$, we consider the dual problems of $\min \Vert Ax-b{\Vert }_p^p,b\in {\mathbb{R}}^n$ and ${\min }_{A^{\top }x=b}\Vert x{\Vert }_p^p,b\in {\mathbb{R}}^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 $\tilde{O}(p{n}^{\theta })$ for some $\theta <\omega$, the matrix multiplication constant. We give the first high-accuracy input sparsity $p$-norm regression algorithm for solving $\min \Vert Ax-b{\Vert }_p^p$ with $1<p\le 2$, via a new row sampling theorem for the smoothed $p$-norm function. This algorithm runs in time $\tilde{O}(\text{nnz}(A)+d^4)$ for any $1<p\le 2$, and in time $\tilde{O}(\text{nnz}(A)+d^{\theta })$ for $p$ close to $2$, improving on the previous best bound where the exponent of $d$ grows with $\max \{p,p/(p-1)\}$.

Includes new results. The first input sparsity algorithm for p-norm via efficient row-sampling

References in corpus (1)

• On Low Rank Matrix Approximations with Applications to Synthesis Problem in Compressed Sensing