Systems Optimization Laboratory

LSRN: Strongly Over- and Under-Determined 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 minimum-length solution to highly rectangular systems \(Ax \approx b\): \begin{align*} \\ \text{minimize } \|x\| \text{ such that } \|Ax-b\| = \min, \end{align*} where the matrix \(A\ \in R^{m \times n}\) is highly over-determined (\(m \gg n\)) or highly under-determined (\(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 well-conditioned, 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 semi-iterative 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 shared-memory 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) C95-C118.
  Permalink: http://dx.doi.org/10.1137/120866580

• RELEASE:
  19 Feb 2012: Python implementation v0.1.
  02 May 2012: C++/Matlab implementation v0.1.

• Python files: lsrn_py-0.1.tar.gz (requires numpy, scipy, mpi4py, and ziggurat).
• C++ with Matlab interface: lsrn_cpp-0.1.tar.gz.