LSRN: A parallel iterative solver for strongly over- or underdetermined systems

DOI10.1137/120866580zbMATH Open1298.65053DBLPjournals/siamsc/MengSM14arXiv1109.5981OpenAlexW2007500622WikidataQ42129485 ScholiaQ42129485MaRDI QIDQ2875015FDOQ2875015

Michael W. Mahoney, Michael A. Saunders, Xiangrui Meng

Publication date: 13 August 2014

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: We describe a parallel iterative least squares solver named exttt{LSRN} that is based on random normal projection. exttt{LSRN} computes the min-length solution to $mi{n}_{xinmathbb{R}^n}|Ax-b{|}_2$, where $Ainmathbb{R}^{mimesn}$ with $mggn$ or $mlln$, 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 exttt{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 $lceilgammamin(m,n)ceilimesmin(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, exttt{LSRN} outperforms LAPACK's DGELSD on large dense problems, and MATLAB's backslash (SuiteSparseQR) on sparse problems. Further experiments demonstrate that exttt{LSRN} scales well on an Amazon Elastic Compute Cloud cluster.

Full work available at URL: https://arxiv.org/abs/1109.5981

zbMATH Keywords

ridge regressionrandom matrixrandomized algorithmsparse matrixTikhonov regularizationpreconditioningparallel computingrandom samplingiterative methodrandom projectionlinear least squaresChebyshev semi-iterative methodminimum-length solutionoverdetermined system, underdetermined system, rank-deficient

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05) Random matrices (algebraic aspects) (15B52) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Preconditioners for iterative methods (65F08) Ill-posedness and regularization problems in numerical linear algebra (65F22) Iterative numerical methods for linear systems (65F10) Numerical computation of matrix norms, conditioning, scaling (65F35)

Cited In (35)

• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• Some Comments on Preconditioning for Normal Equations and Least Squares
• Sketching for Principal Component Regression
• Subdata selection algorithm for linear model discrimination
• Randomized core reduction for discrete ill-posed problem
• Fast model-fitting of Bayesian variable selection regression using the iterative complex factorization algorithm
• Sampled limited memory methods for massive linear inverse problems
• Randomized numerical linear algebra: Foundations and algorithms
• Fast randomized numerical rank estimation for numerically low-rank matrices
• Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition
• Goal-Oriented Optimal Approximations of Bayesian Linear Inverse Problems
• Incremental regularized least squares for dimensionality reduction of large-scale data
• \texttt{pylspack}: parallel algorithms and data structures for sketching, column subset selection, regression, and leverage scores
• Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten \(p\)-norms
• Faster Kernel Ridge Regression Using Sketching and Preconditioning
• Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems
• Model order reduction with oblique projections for large scale wave propagation
• On randomized sketching algorithms and the Tracy-Widom law
• Preconditioners for Krylov subspace methods: An overview
• Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization
• Tikhonov regularization and randomized GSVD
• Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views
• Randomized Nyström Preconditioning
• Compressed and Penalized Linear Regression
• Title not available (Why is that?)
• Semi-Infinite Linear Regression and Its Applications
• SketchySGD: reliable stochastic optimization via randomized curvature estimates
• Title not available (Why is that?)
• A review on design inspired subsampling for big data
• Title not available (Why is that?)
• Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory
• Optimal Low-rank Approximations of Bayesian Linear Inverse Problems
• Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems

Uses Software

• LAPACK
• Blendenpik
• LSRN
• Ziggurat

This page was built for publication: LSRN: A parallel iterative solver for strongly over- or underdetermined systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875015)