Faster Least Squares Approximation

Tamas Sarlos
Yahoo! Research

Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. Methods dating back to Gauss and Legendre find a solution in $O(nd^2)$ time, where $n$ is the number of constraints and $d$ is the number of variables. We present two randomized algorithms that provide very accurate relative-error approximations to the solution of a least squares approximation problem more rapidly than existing exact algorithms. Both of our algorithms preprocess the data with a randomized Hadamard transform. One then uniformly randomly samples constraints and solves the smaller problem on those constraints, and the other performs a sparse random projection and solves the smaller problem on those projected coordinates. In both cases, the solution to the smaller problem provides a relative-error approximation to the exact solution and can be computed in $o(nd^2)$ time. Extensions to regularized least squares approximation and singular value decomposition are also discussed.

Joint work with Petros Drineas, Michael W. Mahoney, and Muthu Muthukrishnan.

Presentation (PowerPoint File)

Back to Workshops II: Numerical Tools and Fast Algorithms for Massive Data Mining, Search Engines and Applications