Accession Number:

ADA482134

Title:

A Fast Randomized Algorithm for Overdetermined Linear Least-Squares Regression

Descriptive Note:

Technical rept.

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2008-04-28

Pagination or Media Count:

15.0

Abstract:

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.

Subject Categories:

  • Statistics and Probability

Distribution Statement:

APPROVED FOR PUBLIC RELEASE