2010 | OriginalPaper | Chapter
Updating and Downdating Matrix Decompositions
Authors : Lars Eldén, Misha E. Kilmer, Dianne P. O’Leary
Published in: G.W. Stewart
Publisher: Birkhäuser Boston
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The Sherman–Morrison–Woodbury formula ([GWS-B7], p. 328) is a recipe for constructing the inverse of a matrix after it has been modified by a low-rank correction. For a matrix of size
n
×
n
that has been so modified, it enables the inverse of this matrix to be updated in time proportional to
kn
, where
k
is the rank of the correction, rather than the
n
3
time usually necessary to compute the inverse directly. This important fact has enabled a variety of algorithms, from early implementations of the simplex method for linear optimization [29] to algorithms for solving least squares problems when new data arrive.