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.
Copyright. All Rights Reserved.