Stability of Conjugate Gradient and Lanczos Methods for Linear Least Squares Problems
A thorough study of two different implementations of the conjugate gradient and the Lanczos methods is presented, in order to find numerical solutions to linear least squares problems. Although these implementations are mathematically equivalent, their computational, and most important, numerical properties are quite different. For the conjugate gradient method the implementations considered are the original ones, as given by \textit{M. R. Hestenes} and \textit{E. Stiefel} in their classic paper [(CGLS1) J. Res. Nat. Bur. Standards 49, 409-436 (1952; Zbl 0048.09901)] and a variant of it (CGLS2) obtained by recurring on the residuals of the normal equations, instead of doing so on the original residuals. For the Lanczos method, the two implementations LSQR and LSCG differ in that LSQR employs Givens rotations in the bidiagonalization process. By adapting a result obtained by \textit{A. Greenbaum} [SIAM J. Matrix Anal. App. 18, No. 3, 535-551 (1997; Zbl 0873.65027)] for linear problems with square matrices, bounds are obtained for the errors in the computed residuals for both CGLS1 and LSQR. These bounds show that both implementations are normwise backward stable. A heuristic explanation is also given for the failure of both CGLS2 and LSCG to yield accurate results. As for storage and operational count, the unstable implementations are less costly than their stable counterparts. But for the tests reported in the paper, which deal with ill-conditioned problems, the difference in accuracy is overwhelmingly in favour of the stable implementations. Another important point to bear in mind is that the unstable variants tend to converge faster (to inaccurate results) than CGLS1, whereas the situation is even when compared with LSQR, which almost always converges faster than CGLS1. On the other hand, regarding accuracy, CGLS1 beats them all, with a slightly higher a priori computational cost than CGLS2, and a significantly smaller one than both LSQR and LSCG. These are perhaps the reasons for the authors' preference for CGLS1. The paper does not report on effective computing times that would justify even more this preference, especially with respect to LSQR, although such justification is suggested by the included graphs. Another very nice graph shows for one example that the norm of the residuals of the normal equations decrease for CGLS1 to about machine precision, while for CGLS2, in spite of very poor convergence, they decrease to zero in the limit. The last conclusion to point out is that for the inconsistent case, CGLS1 and LSQR achieve even better accuracy than a normwise backward stable method.
- Accuracy of preconditioned CG-type methods for least squares problems.
- Numerical aspects of the generalized CG-method applied to least squares problems
- The Lanczos and Conjugate Gradient Algorithms
- Preconditioned Conjugate Gradient Method and Generalized Successive Overrelaxation Method for the Least Squares Problems
- Accuracy of preconditioned CG-type methods for least squares problems.
- Accurate conjugate gradient methods for families of shifted systems
- The triangle method for finding the corner of the L-curve
- Extension of Tikhonov regularization method using linear fractional programming
- A new consistent splitting scheme for incompressible Navier-Stokes flows: a least-squares spectral element implementation
- LSQR algorithm with structured preconditioner for the least squares problem in quaternionic quantum theory
- A class of incomplete orthogonal factorization methods. II: Implemetation and results
- On the robustness of numerical algorithms for linear systems and signal processing in finite precision arithmetic
- Stability of the MGS-like elimination method for equality constrained least squares problems
- scientific article; zbMATH DE number 671777 (Why is no real title available?)
- The adaptive s-step conjugate gradient method
- Solving mixed sparse-dense linear least-squares problems by preconditioned iterative methods
- Total variation superiorized conjugate gradient method for image reconstruction
- Inexact half-quadratic optimization for linear inverse problems
- Composite Step Product Methods for Solving Nonsymmetric Linear Systems
- Linear regression models, least-squares problems, normal equations, and stopping criteria for the conjugate gradient method
- scientific article; zbMATH DE number 852354 (Why is no real title available?)
- Conditional stability of Larkin methods with non-uniform grids
- Block conjugate gradient algorithms for least squares problems
- A new Lanczos-type algorithm for systems of linear equations
- scientific article; zbMATH DE number 7280152 (Why is no real title available?)
- On iterative solution of the extended normal equations
- Sharp 2-norm error bounds for LSQR and the conjugate gradient method
- The Conjugate Residual Method in Linesearch and Trust-Region Methods
- LNLQ: an iterative method for least-norm problems with an error minimization property
- scientific article; zbMATH DE number 6604147 (Why is no real title available?)
- Landweber-type method with uniformly convex constraints under conditional stability assumptions
- Some properties of LSQR for large sparse linear least squares problems
- Efficient solution of parameter identification problems with H¹ regularization
- Estimating error norms in CG-like algorithms for least-squares and least-norm problems
- Cholesky-like preconditioner for Hodge Laplacians via heavy collapsible subcomplex
- Computing projections with LSQR
- Divergence-free and curl-free moving least squares approximations
- Partial least-squares vs. Lanczos bidiagonalization. I: Analysis of a projection method for multiple regression
This page was built for publication: Stability of Conjugate Gradient and Lanczos Methods for Linear Least Squares Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4389103)
