title: LSRN: A PARALLEL ITERATIVE SOLVER FOR STRONGLY OVER- OR UNDERDETERMINED SYSTEMS.
abstract: We describe a parallel iterative least squares solver named LSRN that is based on random normal projection. LSRN computes the min-length solution to minx∈ℝn‖Ax-b‖2, whereA∈ ℝm×nwithm≫norm≪n, and whereAmay be rank-deficient. Tikhonov regularization may also be included. SinceAis involved only in matrix-matrix and matrix-vector multiplications, it can be a dense or sparse matrix or a linear operator, and LSRN automatically speeds up whenAis sparse or a fast linear operator. The preconditioning phase consists of a random normal projection, which is embarrassingly parallel, and a singular value decomposition of size ⌈γ min(m, n)⌉ × min(m, n), where γ is moderately larger than 1, e.g., γ = 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 show that on a shared-memory machine, LSRN is very competitive with LAPACK's DGELSD and a fast randomized least squares solver called Blendenpik on large dense problems, and it outperforms the least squares solver from SuiteSparseQR on sparse problems without sparsity patterns that can be exploited to reduce fill-in. Further experiments show that LSRN scales well on an Amazon Elastic Compute Cloud cluster.
authors.affiliation: ICME, Stanford University, Stanford, CA 94305 ( mengxr@stanford.edu ).
authors.forename: Xiangrui
authors.initials: X
authors.lastname: Meng
authors.affiliation: Systems Optimization Laboratory, Department of Management Science and Engineering, Stanford University, Stanford, CA 94305 ( saunders@stanford.edu ).
authors.forename: Michael A
authors.initials: MA
authors.lastname: Saunders
authors.affiliation: Department of Mathematics, Stanford University, Stanford, CA 94305 ( mmahoney@cs.stanford.edu ).
authors.forename: Michael W
authors.initials: MW
authors.lastname: Mahoney
keywords: Chebyshev semi-iterative method; LAPACK; LSQR; Tikhonov regularization; iterative method; linear least squares; minimum-length solution; over determined system; parallel computing; preconditioning; random matrix; random projection; random sampling; randomized algorithm; rank-deficient; ridge regression; sparse matrix; underdetermined system