Systems Optimization Laboratory
Stanford, CA 943054121 USA

LSRN: Strongly Over and UnderDetermined Systems
 AUTHORS:
Xiangrui Meng,
Michael Saunders,
Michael Mahoney.
 CONTENTS: LSRN is a parallel iterative least squares solver that is
based on random normal projection. It computes the minimumlength
solution to highly rectangular systems \(Ax \approx b\):
\begin{align*}
\\ \text{minimize } \x\ \text{ such that } \Axb\ = \min,
\end{align*}
where the matrix \(A\ \in R^{m \times n}\) is highly
overdetermined (\(m \gg n\)) or highly underdetermined (\(m \ll n\)) and may have any rank.
It may be dense or sparse or a linear operator defined by a routine for computing \(Av\) and \(A^T u\)
for given vectors \(v\) and \(u\).
We expect \(\min(m,n) = O(1000)\), but the other dimension may be millions.
The preconditioning phase consists of a random normal projection
(which is embarrassingly parallel) and a singular value decomposition of size
\( \lceil \gamma \min(m,n) \rceil \times \min(m,n) \),
where \(\gamma\) is moderately larger than 1, e.g. \(\gamma=2\).
We prove that the preconditioned system is
wellconditioned, with a strong concentration result
on the extreme singular values, and hence that the
number of iterations is fully predictable when we
apply LSQR or the Chebyshev semiiterative method. As
we demonstrate, the Chebyshev method is particularly
efficient for solving large problems on clusters with
high communication cost. Numerical results demonstrate
that on a sharedmemory machine, LSRN outperforms
LAPACK's DGELSD on large dense problems, and MATLAB's
backslash (SuiteSparseQR) on sparse problems. Further
experiments demonstrate that LSRN scales well on an
Amazon Elastic Compute Cloud cluster.
 REFERENCE:
Xiangrui Meng, Michael A. Saunders, and Michael W. Mahoney.
LSRN: a parallel iterative solver for strongly
over or underdetermined systems,
SIAM J. Sci. Comput. 36:2 (2014) C95C118.
Permalink:
http://dx.doi.org/10.1137/120866580
 RELEASE:
19 Feb 2012: Python implementation v0.1.
02 May 2012: C++/Matlab implementation v0.1.
DOWNLOADS:
