A fast randomized algorithm for overdetermined linear least-squares regression
2008
Rokhlin, Vladimir | Tygert, Mark
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 ε, the procedure computes an n x 1 vector x such that x minimizes the Euclidean norm ||Ax - b|| to relative precision ε. The algorithm typically requires O((log(n)+log(1/ε))mn+n³) floating-point operations. This cost is less than the O(mn²) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.
Show more [+] Less [-]AGROVOC Keywords
Bibliographic information
This bibliographic record has been provided by National Agricultural Library