Sampling Algorithms and Coresets for ₚ Regression

The ₚ regression problem takes as input a matrix An× d, a vector bⁿ, and a number p∈[1,∞), and it returns as output a number Z and a vector x_ optᵈ such that Z=minxᵈ\|Ax-b\|ₚ=\|Ax_ opt-b\|ₚ. In this paper, we construct coresets and obtain an efficient two-stage sampling-based approximation algorithm for the very overconstrained (n d) version of this classical problem, for all p∈[1, ∞). The first stage of our algorithm nonuniformly samples r̂₁=O(36ᵖ d^max/2+1,p\+1) rows of A and the corresponding elements of b, and then it solves the ₚ regression problem on the sample; we prove this is an 8-approximation. The second stage of our algorithm uses the output of the first stage to resample r̂₁/ε² constraints, and then it solves the ₚ regression problem on the new sample; we prove this is a (1+ε)-approximation. Our algorithm unifies, improves upon, and extends the existing algorithms for special cases of ₚ regression, namely, $p = 1,2$ [K. L. Clarkson, in Proceedings of the 16th Annual ACM–SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2005, pp. 257–266; P. Drineas, M. W. Mahoney, and S. Muthukrishnan, in Proceedings of the 17th Annual ACM–SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2006, pp. 1127–1136]. In the course of proving our result, we develop two concepts—well-conditioned bases and subspace-preserving sampling—that are of independent interest.