Fast Randomized Algorithm for Overdetermined Linear Least-Squares Regression; Technical rept

摘要

We introduce a randomized algorithm for overdetermined linear least- squares regression. Given an arbitrary full-rank m n matrix A with m > n, any m 1 vector b, and any positive real number epsilon, the procedure computes an n 1 vector x which minimizes the spectral norm.