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.

References in zbMATH (referenced in 27 articles )

Showing results 1 to 20 of 27.
Sorted by year (citations)

1 2 next

  1. Shustin, Paz Fink; Avron, Haim: Semi-infinite linear regression and its applications (2022)
  2. Chi, Jocelyn T.; Ipsen, Ilse C. F.: Multiplicative perturbation bounds for multivariate multiple linear regression in Schatten (p)-norms (2021)
  3. Du, Yi-Shu; Hayami, Ken; Zheng, Ning; Morikuni, Keiichi; Yin, Jun-Feng: Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems (2021)
  4. Du, Yi-Shu; Hayami, Ken; Zheng, Ning; Morikuni, Keiichi; Yin, Jun-Feng: Kaczmarz-type inner-iteration preconditioned flexible GMRES methods for consistent linear systems (2021)
  5. Sobczyk, Aleksandros; Gallopoulos, Efstratios: Estimating leverage scores via rank revealing methods and randomization (2021)
  6. Chung, Julianne; Chung, Matthias; Tanner Slagel, J.; Tenorio, Luis: Sampled limited memory methods for massive linear inverse problems (2020)
  7. Homrighausen, Darren; McDonald, Daniel J.: Compressed and penalized linear regression (2020)
  8. Richtárik, Peter; Takáč, Martin: Stochastic reformulations of linear systems: algorithms and convergence theory (2020)
  9. Zhang, Liping; Wei, Yimin: Randomized core reduction for discrete ill-posed problem (2020)
  10. Bjarkason, Elvar K.: Pass-efficient randomized algorithms for low-rank matrix approximation using any number of views (2019)
  11. Mor-Yosef, Liron; Avron, Haim: Sketching for principal component regression (2019)
  12. Renaut, Rosemary A.; Helmstetter, Anthony W.; Vatankhah, Saeed: Unbiased predictive risk estimation of the Tikhonov regularization parameter: convergence with increasing rank approximations of the singular value decomposition (2019)
  13. Zhou, Quan; Guan, Yongtao: Fast model-fitting of Bayesian variable selection regression using the iterative complex factorization algorithm (2019)
  14. Jia, Zhongxiao; Yang, Yanfei: Modified truncated randomized singular value decomposition (MTRSVD) algorithms for large scale discrete ill-posed problems with general-form regularization (2018)
  15. Yang, Jiyan; Chow, Yin-Lam; Ré, Christopher; Mahoney, Michael W.: Weighted SGD for (\ell_p) regression with randomized preconditioning (2018)
  16. Avron, Haim; Clarkson, Kenneth L.; Woodruff, David P.: Faster kernel ridge regression using sketching and preconditioning (2017)
  17. Spantini, Alessio; Cui, Tiangang; Willcox, Karen; Tenorio, Luis; Marzouk, Youssef: Goal-oriented optimal approximations of Bayesian linear inverse problems (2017)
  18. Pereyra, Victor: Model order reduction with oblique projections for large scale wave propagation (2016)
  19. Scott, Jennifer; Tuma, Miroslav: Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations (2016)
  20. Wei, Yimin; Xie, Pengpeng; Zhang, Liping: Tikhonov regularization and randomized GSVD (2016)

1 2 next