# 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.

# Descriptors:

# Subject Categories:

- Statistics and Probability