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 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 ||A(sub x)- b|| to relative precision epsilon. The algorithm typically requires O ((log(n) + log(1/epsilon))mn+n(exp 3)) floating-point operations. This cost is less than the O(mn(exp 2)) required by the classical schemes based on QR-decompositions or bidiagonalization. We present several numerical examples illustrating the performance of the algorithm.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Apr 28, 2008
Accession Number
ADA482134

Entities

People

  • Mark Tygert
  • Vladimir Rokhlin, Jr.

Organizations

  • Yale University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Science
  • Decomposition
  • Discrete Fourier Transforms
  • Floating Point Operations
  • Guarantees
  • Iterations
  • Numbers
  • Permutations
  • Perturbation Theory
  • Precision
  • Probability
  • Random Variables
  • Real Numbers
  • Residuals
  • Simultaneous Equations

Fields of Study

  • Mathematics

Readers

  • Linear Algebra
  • Statistical inference.