Faster Least Squares Approximation

Comparison of the method of averages with the method of least squares

G. Dahlquist, B. Sjöberg, and P. Svensson · 1968

Earlier work this paper cites.

A generalization of the fast LUP matrix decomposition algorithm and applications

O.H. Ibarra, S. Moran, and R. Hui · 1982

Earlier work this paper cites.

The History of Statistics: The Measurement of Uncertainty before 1900

Original

S.M. Stigler · 1986

Earlier work this paper cites.

Matrix multiplication via arithmetic progressions

D. Coppersmith and S. Winograd · 1990

Earlier work this paper cites.

Matrix Perturbation Theory

G.W. Stewart and J.G. Sun · 1990

Earlier work this paper cites.

Randomized Algorithms

R. Motwani and P. Raghavan · 1995

Earlier work this paper cites.

Matrix Computations

G.H. Golub and C.F. Van Loan · 1996

Earlier work this paper cites.

Matrix Analysis

R. Bhatia · 1997

Earlier work this paper cites.

Generalized Inverses: Theory and Applications

A. Ben-Israel and T.N.E. Greville · 2003

Earlier work this paper cites.

Spectral techniques applied to sparse random graphs

U. Feige and E. Ofek · 2005

Cited alongside, same era.

Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

N. Ailon and B. Chazelle · 2006

Cited alongside, same era.

A fast random sampling algorithm for sparsifying matrices

S. Arora, E. Hazan, and S. Kale · 2006

Cited alongside, same era.

Fast Monte Carlo algorithms for matrices I: Approximating matrix multiplication

P. Drineas, R. Kannan, and M.W. Mahoney · 2006

Cited alongside, same era.

Sampling algorithms for ℓ 2 \ell_{2} regression and applications

P. Drineas, M.W. Mahoney, and S. Muthukrishnan · 2006

Cited alongside, same era.

Improved approximation algorithms for large matrices via random projections

T. Sarlós · 2006

Cited alongside, same era.

Relative-error CUR matrix decompositions

P. Drineas, M.W. Mahoney, and S. Muthukrishnan · 2008

Closest in time.

On variants of the Johnson–Lindenstrauss lemma

J. Matoušek · 2008

Closest in time.

A fast randomized algorithm for overdetermined linear least-squares regression

V. Rokhlin and M. Tygert · 2008

Closest in time.

Blendenpik: Supercharging LAPACK’s least-squares solver

H. Avron, P. Maymounkov, and S. Toledo · 2009

Closest in time.

Numerical linear algebra in the streaming model

K.L. Clarkson and D.P. Woodruff · 2009

Closest in time.

A fast and efficient algorithm for low-rank approximation of a matrix

N.H. Nguyen, T.T. Do, and T.D. Tran · 2009

Closest in time.