A Fast Randomized Algorithm for Overdetermined Linear Least-Squares Regression
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
We introduce a randomized algorithm for overdetermined linear least-squares regression. Given an arbitrary full-rank m x n matrix A with m greater than or equal to n, any m x 1 vector b, and any positive real number epsilon, the procedure computes an n x 1 vector x which minimizes the spectral norm Asub x- b to relative precision epsilon. The algorithm typically requires O logn log1epsilonmnnexp 3 floating-point operations. This cost is less than the Omnexp 2 required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.
- Statistics and Probability