Faster p-Norm Regression Using Sparsity

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).