Minimum-residual methods for sparse least-squares using Golub-Kahan bidiagonalization
Abstract/Contents
- Abstract
- For 30 years, LSQR and its theoretical equivalent CGLS have been the standard iterative solvers for large rectangular systems of linear equations and least-squares problems. They are analytically equivalent to symmetric CG on the corresponding normal equation, and they reduce the residual norm monotonically. The techniques pioneered in the development of LSQR allow better algorithms to be developed for a wider range of problems. We derive LSMR, an algorithm that is similar to LSQR but exhibits better convergence properties. LSMR is equivalent to applying MINRES to the normal equation, so that the error, the residual, and the residual of the normal equation all decrease monotonically. In practice we observe that the Stewart backward error is usually monotonic and very close to optimal. LSMR has essentially the same computational cost per iteration as LSQR, but the Stewart backward error is always smaller. Thus if iterations need to be terminated early, it is safer to use LSMR. LSQR and LSMR are based on Golub-Kahan bidiagonalization. Following the analysis of LSMR, we leverage the techniques used there to construct algorithm AMRES for negatively-damped least-squares systems, again using Golub-Kahan bidiagonalization. Such problems arise in total least-squares, Rayleigh quotient iteration (RQI), and Curtis-Reid scaling for rectangular sparse matrices. Our solver AMRES provides a stable method for these problems. AMRES allows caching and reuse of the Golub-Kahan vectors across RQIs, and can be used to compute any of the singular vectors of A, given a reasonable estimate of the singular vector or an accurate estimate of the singular value.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2011 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Fong, Chin Lung |
|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
| Primary advisor | Saunders, Michael |
| Thesis advisor | Saunders, Michael |
| Thesis advisor | Gerritsen, Margot (Margot G.) |
| Thesis advisor | Murray, Walter |
| Advisor | Gerritsen, Margot (Margot G.) |
| Advisor | Murray, Walter |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | David Chin Lung Fong. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis (Ph. D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Chin Lung Fong
Also listed in
Loading usage metrics...