{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:12:19Z","timestamp":1787382739447,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>We propose and analyze a new tool to help solve sparse linear least-squares problems $\\min_{x}\\|Ax-b\\|_{2}$. Our method is based on a sparse $QR$ factorization of a low-rank perturbation $\\hat{A}$ of A. More precisely, we show that the R factor of $\\hat{A}$ is an effective preconditioner for the least-squares problem $\\min_{x}\\|Ax-b\\|_{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 $\\hat{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 $\\hat{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.<\/jats:p>","DOI":"10.1137\/070698725","type":"journal-article","created":{"date-parts":[[2009,6,17]],"date-time":"2009-06-17T18:04:42Z","timestamp":1245261882000},"page":"674-693","source":"Crossref","is-referenced-by-count":17,"title":["Using Perturbed $QR$ Factorizations to Solve Linear Least-Squares Problems"],"prefix":"10.1137","volume":"31","author":[{"given":"Haim","family":"Avron","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Esmond","family":"Ng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sivan","family":"Toledo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2009,6,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"H. Avron, E. Ng, and S. Toledo,\n                      A Generalized Courant-Fischer Minimax Theorem\n                      , Tech. report, Tel-Aviv University, Tel-Aviv, Israel, 2008.","DOI":"10.2172\/1165117"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/0613078"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"C. Bischof and P. Tang,\n                      LAPACK Working Note\n                      33:\n                      Robust Incremental Condition Estimation\n                      , Tech. report, University of Tennessee, Knoxville, TN, 1991.","DOI":"10.2172\/10133022"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0611021"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/0912073"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1137\/0611047"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0905029"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"\u00c5 Bj\u00f6rck,\n                      Numerical Methods for Least Squares Problems\n                      , SIAM, Philadelphia, 1996.","DOI":"10.1137\/1.9781611971484"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"I. Brainman and S. Toledo,\n                      Nested-dissection orderings for sparse LU with partial pivoting\n                      , in Proceedings of the 10th SIAM Conference on Parallel Processing for Scientific Computing, Norfolk, VA, 2001, CD-ROM, SIAM, Philadelphia, 2001.","DOI":"10.1007\/3-540-45262-1_16"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(87)90103-0"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0913043"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479891223781"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"P. Concus, G. H. Golub, and D. P. O'Leary,\n                      A generalized conjugate gradient method for the numerical solution of elliptic partial differential equations\n                      , in Sparse Matrix Computations, J. R. Bunch and D. J. Rose, eds., Academic Press, New York, 1976, pp. 309\u2013332.","DOI":"10.1016\/B978-0-12-141050-6.50023-4"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"T. A. Davis,\n                      Direct Methods for Sparse Linear Systems\n                      , Fundamentals of Algorithms 2, SIAM, Philadelphia, 2006.","DOI":"10.1137\/1.9780898718881"},{"key":"R15","unstructured":"T. A. Davis, J. R. Gilbert, S. I. Larimore, and E. G. Ng,\n                      A Column Approximate Minimum Degree Ordering Algorithm\n                      , Tech. report TR-00-005, Department of Computer and Information Science and Engineering, University of Florida, Gainesville, FL, 2000."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021946924741"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/0911030"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(80)90159-7"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592025"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01436075"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/0702016"},{"key":"R22","unstructured":"G. H. Golub and C. F. Van Loan,\n                      Matrix Computations\n                      , 3rd ed., The Johns Hopkins University Press, Baltimore, MD, 1996."},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1137\/0903014"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.6028\/jres.049.044"},{"key":"R25","unstructured":"N. J. Higham,\n                      Accuracy and Stability of Numerical Algorithms\n                      , SIAM, Philadelphia, 1996."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893259509"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1137\/0912062"},{"key":"R28","unstructured":"M. K. Ng,\n                      Iterative Methods for Toeplitz Systems (Numerical Mathematics and Scientific Computation)\n                      , Oxford University Press, New York, 2004."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1145\/355984.355989"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479893244353"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01933494"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070698725","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:45:25Z","timestamp":1787334325000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070698725"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1137\/070698725"],"URL":"https:\/\/doi.org\/10.1137\/070698725","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]}}}