2012/07/19 by Kenneth L. Clarkson, Clarkson, Kenneth L., Petros Drineas +9 · 1 citation
Engineering · Mathematics · Computer Science · #Sparse and Compressive Sensing Techniques #Mathematical Approximation and Integration #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1207.4684
We provide fast algorithms for overconstrained ℓp regression and related problems: for an n× d input matrix A and vector b∈ℝn, in O(ndlog n) time we reduce the problem minx∈ℝd ‖Ax-b‖p to the same problem with input matrix A of dimension s × d and corresponding b of dimension s× 1. Here, A and b are a coreset for the problem, consisting of sampled and rescaled rows of A and b; and s is independent of n and polynomial in d. Our results improve on the best previous algorithms when n≫ d, for all p∈[1,∞) except p=2. We also provide a suite of improved results for finding well-conditioned bases via ellipsoidal rounding, illustrating tradeoffs between running time and conditioning quality, including a one-pass conditioning algorithm for general ℓp problems. We also provide an empirical evaluation of implementations of our algorithms for p=1, comparing them with related algorithms. Our empirical results show that, in the asymptotic regime, the theory is a very good guide to the practical performance of these algorithms. Our algorithms use our faster constructions of well-conditioned bases for ℓp spaces and, for p=1, a fast subspace embedding of independent interest that we call the Fast Cauchy Transform: a distribution over matrices Π:ℝn↦ ℝO(dlog d), found obliviously to A, that approximately preserves the ℓ1 norms: that is, with large probability, simultaneously for all x, ‖Ax‖1 ≈ ‖ΠAx‖1, with distortion O(d2+η), for an arbitrarily small constant η>0; and, moreover, ΠA can be computed in O(ndlog d) time. The techniques underlying our Fast Cauchy Transform include fast Johnson-Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.