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

DOI10.1137/120866580MaRDI QIDQ2875015zbMATH OpenOpenAlexDBLPWikidataFDO

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

Publication date 13 August 2014

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

Full work available at URL https://arxiv.org/abs/1109.5981, http://europepmc.org/articles/pmc4238893

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)

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.

Recommendations

• Parallel algorithms for the iterative solution of sparse least-squares problems
• Faster least squares approximation
• Parallel solution of sparse linear least squares problems on distributed-memory multiprocessors
• A fast randomized algorithm for overdetermined linear least-squares regression
• Blendenpik: Supercharging LAPACK's Least-Squares Solver

Cited in

(37)

• Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views
• Estimating Leverage Scores via Rank Revealing Methods and Randomization
• 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
• Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition
• Weighted SGD for \(\ell_p\) regression with randomized preconditioning
• PLSS: A Projected Linear Systems Solver
• Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems
• Fast randomized numerical rank estimation for numerically low-rank matrices
• Incremental regularized least squares for dimensionality reduction of large-scale data
• More efficient estimation for logistic regression with optimal subsamples
• Stochastic reformulations of linear systems: algorithms and convergence theory
• \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
• Sketching for principal component regression
• Are sketch-and-precondition least squares solvers numerically stable?
• Some comments on preconditioning for normal equations and least squares
• 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
• Goal-oriented optimal approximations of Bayesian linear inverse problems
• Tikhonov regularization and randomized GSVD
• Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
• Optimal low-rank approximations of Bayesian linear inverse problems
• M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions
• Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems
• Randomized Nyström Preconditioning
• Compressed and Penalized Linear Regression
• scientific article; zbMATH DE number 7625175 (Why is no real title available?)
• Semi-Infinite Linear Regression and Its Applications
• SketchySGD: reliable stochastic optimization via randomized curvature estimates
• A review on design inspired subsampling for big data
• Faster kernel ridge regression using sketching and preconditioning

Describes a project that uses

Uses Software

• Ziggurat
• LSRN
• Blendenpik
• LAPACK

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)