title: A fast randomized algorithm for overdetermined linear least-squares regression.
abstract: We introduce a randomized algorithm for overdetermined linear least-squares regression. Given an arbitrary full-rank m x n matrix A with m >/= n, any m x 1 vector b, and any positive real number epsilon, the procedure computes an n x 1 vector x such that x minimizes the Euclidean norm ||Ax - b || to relative precision epsilon. The algorithm typically requires ((log(n)+log(1/epsilon))mn+n(3)) floating-point operations. This cost is less than the (mn(2)) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.
authors.affiliation: Program in Applied Mathematics, Yale University, A. K. Watson Hall, 51 Prospect Street, New Haven, CT 06511, USA.
authors.forename: Vladimir
authors.initials: V
authors.lastname: Rokhlin
authors.forename: Mark
authors.initials: M
authors.lastname: Tygert
mesh_terms: D000465:Algorithms; D016018:Least-Squares Analysis; D016014:Linear Models
references.citation: Proc Natl Acad Sci U S A. 2007 Dec 18;104(51):20167-72
references.pmid: 18056803