LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems

DOI10.1137/120866580zbMath1298.65053arXiv1109.5981OpenAlexW2007500622WikidataQ42129485 ScholiaQ42129485MaRDI QIDQ2875015

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)

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

zbMATH Keywords

preconditioning iterative method parallel computing sparse matrix randomized algorithm ridge regression random matrix Tikhonov regularization random sampling random projection linear least squares Chebyshev semi-iterative method minimum-length solution overdetermined system, underdetermined system, rank-deficient

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical solutions to overdetermined systems, pseudoinverses (65F20) 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) Parallel numerical computation (65Y05) Random matrices (algebraic aspects) (15B52) Preconditioners for iterative methods (65F08)

Related Items (32)

Randomized numerical linear algebra: Foundations and algorithms ⋮ Optimal Low-rank Approximations of Bayesian Linear Inverse Problems ⋮ Unnamed Item ⋮ Semi-Infinite Linear Regression and Its Applications ⋮ Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization ⋮ Some Comments on Preconditioning for Normal Equations and Least Squares ⋮ Faster Kernel Ridge Regression Using Sketching and Preconditioning ⋮ Model order reduction with oblique projections for large scale wave propagation ⋮ M-IHS: an accelerated randomized preconditioning method avoiding costly matrix decompositions ⋮ Preconditioners for Krylov subspace methods: An overview ⋮ Fast randomized numerical rank estimation for numerically low-rank matrices ⋮ On randomized sketching algorithms and the Tracy-Widom law ⋮ Stochastic Reformulations of Linear Systems: Algorithms and Convergence Theory ⋮ Randomized Nyström Preconditioning ⋮ Goal-Oriented Optimal Approximations of Bayesian Linear Inverse Problems ⋮ Sketching for Principal Component Regression ⋮ Fast model-fitting of Bayesian variable selection regression using the iterative complex factorization algorithm ⋮ Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems ⋮ Unnamed Item ⋮ Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition ⋮ Unnamed Item ⋮ Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views ⋮ Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten \(p\)-norms ⋮ Incremental Regularized Least Squares for Dimensionality Reduction of Large-Scale Data ⋮ Tikhonov Regularization and Randomized GSVD ⋮ Compressed and Penalized Linear Regression ⋮ Randomized core reduction for discrete ill-posed problem ⋮ Preconditioning of Linear Least Squares by Robust Incomplete Factorization for Implicitly Held Normal Equations ⋮ Kaczmarz-Type Inner-Iteration Preconditioned Flexible GMRES Methods for Consistent Linear Systems ⋮ Sampled limited memory methods for massive linear inverse problems ⋮ Estimating Leverage Scores via Rank Revealing Methods and Randomization ⋮ Subdata selection algorithm for linear model discrimination

Uses Software

This page was built for publication: LSRN: A Parallel Iterative Solver for Strongly Over- or Underdetermined Systems