Subspace embeddings and l_p-regression using exponential random variables

Abstract

Oblivious low-distortion subspace embeddings are a crucial building block for numerical linear algebra problems. We show for any real p, 1 ≤ p < ∞, given a matrix M ∈ ℝn×d with n ≥ d, with constant probability we can choose a matrix π with max(1, n 1-2/p)poly(d) rows and n columns so that simultaneously for all x ∈ ℝd, ||Mx||p ≤ ||ΠMx||∞ ≤ poly(d)||Mx||p. Importantly, ΠM can be computed in the optimal O(nnz(M)) time, where nnz(M) is the number of non-zero entries of M. This generalizes all previous oblivious subspace embeddings which required p ∈ [1, 2] due to their use of p-stable random variables. Using our matrices Π, we also improve the best known distortion of oblivious subspace embeddings of l1 into l1 with Õ(d) target dimension in O(nnz(M)) time from Õ(d3) to Õ(d2), which can further be improved to Õ(d3/2)log / n if d= Ω(log n), answering aquestion of Meng and Mahoney (STOC, 2013). We apply our results to l p-regression, obtaining a (1+ε)-approximation in O(nnz(M) log n)+poly(d/ε) time, improving the best known poly(d/ε) factors for every p ∈ [1, ∞) \ {2}. If one is just interested in a poly(d) rather than a (1 + ε)-approximation to lp-regression, a corollary of our results is that for all p ∈ [1, ∞) we can solve the l p-regression problem without using general convex programming, that is, since our subspace embeds into l∞ it suffices to solve a linear programming problem. Finally, we give the first protocols for the distributed lp-regression problem for every p ≥ 1 which are nearly optimal in communication and computation. © 2013 D.P. Woodruff & Q. Zhang.