Low Rank Updates for the Cholesky Decomposition

Usage of the Sherman-Morrison-Woodbury formula to update linear systems after low rank modifications of the system matrix is widespread in machine learning. However, it is well known that this formula can lead to serious instabilities in the presence of roundoff error. If the system matrix is symmetric positive definite, it is almost always possible to use a representation based on the Cholesky decomposition which renders the same results (in exact arithmetic) at the same or less operational cost, but typically is much more numerically stable. In this note, we show how the Cholesky decomposition can be updated to incorporate low rank additions or downdated for low rank subtractions. We also discuss a special case of an indefinite update of rank two. The methods discussed here are well-known in the numerical mathematics literature, and code for most of them can be found in the LINPACK suite.