low-rank updates to a factorization

Many algorithms solve a sequence of systems where the matrix barely changes between steps: add one data point to a least-squares fit, swap a constraint in an active-set method, take a quasi-Newton step. Refactoring from scratch each time, at cost n^3, is wasteful when the change has tiny rank. Factorization updating recomputes the factors of the new matrix cheaply from the old ones.

The cleanest case is a rank-1 change, A_new = A + u v^T, adding an outer product to A. For the inverse there is an exact closed form, the Sherman-Morrison formula. For a QR or Cholesky factorization there are stable algorithms that walk the existing factors back to triangular form using a sequence of Givens rotations or Householder steps, at cost order n^2 rather than n^3.

Adding information (a new row, a positive term) is called updating; removing information (deleting a row, a negative-rank change) is called downdating. Downdating is the delicate direction: subtracting can destroy positive definiteness or cancel away the leading digits, so a numerically careful downdate (for example via hyperbolic rotations) is needed to keep the result trustworthy.

The payoff is an order-of-magnitude speedup in the inner loop. Recursive least squares, Kalman filtering, sequential quadratic programming, and online learning all live or die on cheap updates: each new observation modifies the system by low rank, and an n^2 update keeps the whole stream affordable where repeated n^3 refactoring would not.