LSRN swMATH ID: 9555 Software Authors: Meng, Xiangrui; Saunders, Michael A.; Mahoney, Michael W. Description: LSRN: A parallel iterative solver for strongly over- or underdetermined systems. We describe a parallel iterative least squares solver named LSRN that is based on random normal projection. LSRN computes the min-length solution to min x∈ℝ n ∥Ax-b∥ 2 , where A∈ℝ m×n with m≫n or m≪n, and where A may be rank-deficient. Tikhonov regularization may also be included. Since A is 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 when A is 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. Homepage: http://web.stanford.edu/group/SOL/papers/lsrn-sisc-2014.pdf Related Software: Blendenpik; LSQR; CRAIG; Regularization tools; UTV; JDQR; JDQZ; LSMR; PDCO; SparseMatrix; Algorithm 971; kappa_SQ; Algorithm 844; HOGWILD; IR Tools; AIR tools; EIGIFP; LAPACK; ASKIT; batchtools Cited in: 29 Documents all top 5 Cited by 59 Authors 6 Mahoney, Michael W. 3 Avron, Haim 3 Tenorio, Luis 2 Cui, Tiangang 2 Du, Yishu 2 Hayami, Ken 2 Marzouk, Youssef M. 2 Meng, Xiangrui 2 Morikuni, Keiichi 2 Spantini, Alessio 2 Wei, Yimin 2 Woodruff, David P. 2 Yin, Junfeng 2 Zhang, Liping 2 Zheng, Ning 1 Bjarkason, Elvar K. 1 Cheng, Li 1 Chi, Jocelyn T. 1 Chow, Yinlam 1 Chu, Delin 1 Chung, Julianne M. 1 Chung, Matthias 1 Clarkson, Kenneth L. 1 Drineas, Petros 1 Gallopoulos, Efstratios 1 Guan, Yongtao 1 Helmstetter, Anthony W. 1 Homrighausen, Darren 1 Ipsen, Ilse C. F. 1 Jia, Zhongxiao 1 Liao, Li-Zhi 1 Ma, Ping 1 Magdon-Ismail, Malik 1 Martinsson, Per-Gunnar 1 McDonald, Daniel J. 1 Mor-Yosef, Liron 1 Ng, Michael Kwok-Po 1 Ré, Christopher M. 1 Renaut, Rosemary Anne 1 Richtárik, Peter 1 Saunders, Michael A. 1 Scott, Jennifer A. 1 Shustin, Paz Fink 1 Slagel, J. Tanner 1 Sobczyk, Aleksandros 1 Solonen, Antti 1 Takáč, Martin 1 Tan, Roger C. E. 1 Tropp, Joel A. 1 Tůma, Miroslav 1 Vatankhah, Saeed 1 Wathen, Andrew John 1 Willcox, Karen E. 1 Xie, Pengpeng 1 Yang, Jiyan 1 Yang, Yanfei 1 Yu, Bin 1 Zhang, Xiaowei 1 Zhou, Quan all top 5 Cited in 12 Serials 8 SIAM Journal on Scientific Computing 6 SIAM Journal on Matrix Analysis and Applications 3 Journal of Machine Learning Research (JMLR) 2 Inverse Problems 2 Journal of Computational and Applied Mathematics 1 BIT 1 Linear Algebra and its Applications 1 SIAM Review 1 Acta Numerica 1 Foundations and Trends in Machine Learning 1 Journal of Computational and Graphical Statistics 1 Bayesian Analysis all top 5 Cited in 11 Fields 21 Numerical analysis (65-XX) 15 Computer science (68-XX) 10 Statistics (62-XX) 8 Linear and multilinear algebra; matrix theory (15-XX) 3 Operations research, mathematical programming (90-XX) 2 Fluid mechanics (76-XX) 1 Operator theory (47-XX) 1 Probability theory and stochastic processes (60-XX) 1 Mechanics of deformable solids (74-XX) 1 Geophysics (86-XX) 1 Biology and other natural sciences (92-XX) Citations by Year