DOE OSTI · 938513
Using Perturbed QR Factorizations To Solve Linear Least-Squares Problems
Abstract
We propose and analyze a new tool to help solve sparse linear least-squares problems min{sub x} {parallel}Ax-b{parallel}{sub 2}. Our method is based on a sparse QR factorization of a low-rank perturbation {cflx A} of A. More precisely, we show that the R factor of {cflx A} is an effective preconditioner for the least-squares problem min{sub x} {parallel}Ax-b{parallel}{sub 2}, when solved using LSQR. We propose applications for the new technique. When A is rank deficient we can add rows to ensure that the preconditioner is well-conditioned without column pivoting. When A is sparse except for a few dense rows we can drop these dense rows from A to obtain {cflx A}. Another application is solving an updated or downdated problem. If R is a good preconditioner for the original problem A, it is a good preconditioner for the updated/downdated problem {cflx A}. We can also solve what-if scenarios, where we want to find the solution if a column of the original matrix is changed/removed. We present a spectral theory that analyzes the generalized spectrum of the pencil (A*A,R*R) and analyze the applications.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Avron, Haim, Ng, Esmond G, Toledo, Sivan. 2008-03-21. Using Perturbed QR Factorizations To Solve Linear Least-Squares Problems. https://searchnasa.com/record/osti%3A938513/using-perturbed-qr-factorizations-to-solve-linear-least-squares-problems
Citations retain the original authors and DOI and include this site’s record URL. If this discovery service contributed to your research, you can also cite Search NASA by Indiciae: BibTeX · RIS.