The Fast Cauchy Transform and Faster Robust Linear Regression

Abstract

We provide fast algorithms for overconstrained _p regression and related problems: for an n d input matrix A and vector bR^n, in O(nd n) time we reduce the problem _xR^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 :R^n R^O(d 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(d^2+), for an arbitrarily small constant >0; and, moreover, A can be computed in O(nd d) time. The techniques underlying our Fast Cauchy Transform include fast Johnson-Lindenstrauss transforms, low-coherence matrices, and rescaling by Cauchy random variables.

Tasks

Reproductions