Understand
We describe a parallel iterative least squares solver named \texttt{LSRN} that is based on random normal projection.
- \texttt{LSRN} computes the min-length solution to $\min_{x \in \mathbb{R}^n} \|A x - b\|_2$, where $A \in \mathbb{R}^{m \times n}$ with $m \gg n$ or $m \ll n$, and where $A$ may be rank-deficient.
- Tikhonov regularization may also be included.
- Since $A$ is only involved in matrix-matrix and matrix-vector multiplications, it can be a dense or sparse matrix or a linear operator, and \texttt{LSRN} automatically speeds up when $A$ is sparse or a fast linear operator.
Built on
M. R. Hestenes and E. Stiefel
1952
Earlier work this paper cites.
G. H. Golub and R. S. Varga
1961
Earlier work this paper cites.
A. Torralba, R. Fergus, and W. T. Freeman
1970
Earlier work this paper cites.
D. G. Luenberger
1973
Earlier work this paper cites.
C. C. Paige and M. A. Saunders
1975
Earlier work this paper cites.
G. T. Herman, A. Lent, and H. Hurwitz
1980
Earlier work this paper cites.
G. H. Golub and C. F. Van Loan
1996
Earlier work this paper cites.
Similar
G. Marsaglia and W. W. Tsang
2000
Cited alongside, same era.
K. R. Davidson and S. J. Szarek
2001
Cited alongside, same era.
M. H. Gutknecht and S. Rollin
2002
Cited alongside, same era.
T. A. Davis
2006
Cited alongside, same era.
P. Drineas, M. W. Mahoney, and S. Muthukrishnan
2006
Cited alongside, same era.
T. Sarlós
2006
Cited alongside, same era.
V. Rokhlin and M. Tygert
2008
Cited alongside, same era.
Then
H. Avron, P. Maymounkov, and S. Toledo
2010
Later among the works it cites.
E. S. Coakley, V. Rokhlin, and M. Tygert
2011
Closest in time.
T. A. Davis and Y. Hu
2011
Closest in time.
P. Drineas, M. W. Mahoney, S. Muthukrishnan, and T. Sarlós
2011
Closest in time.
D. C.-L. Fong and M. Saunders
2011
Closest in time.
N. Halko, P. G. Martinsson, and J. A. Tropp
2011
Closest in time.
Also available at arXiv:1104.5557v2
M. W. Mahoney · 2011
Closest in time.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…