# Up-/downdating methods for a series of normal equations

In an application I have to solve a series of positive definite linear systems of the form $A^TA x = A^Tb$ (i.e. normal equations). The next system is obtained from the previous one by adding and/or removing a small number of columns to $A$ (usually one or two). The vector $b$ stays the same throughout. It seems clear that some kind of up-/downdating strategy should be applied, however, my questions are:

What kind of up-/downdating shall I choose (QR, Cholesky, Matrix-Inversion-Lemma,others?,...)?

On what conditions and requirements shall I make my choice (high precision needed, ill-conditioned matrices, well-conditioned ones, speed,...)?

P.S.: You may assume that $A$ and $A^T$ can be applied fast.

• So you have $\mathbf A$ itself available and not just $\mathbf A^\top \mathbf A$? Updating a QR decomposition seems to be a good choice if the condition number of $\mathbf A$ is reasonable (there are also updating algorithms for SVD, but I've found them a bit unwieldy). As a matter of fact, the Cholesky and QR updating methods are essentially equivalent... – J. M. Jan 13 '12 at 10:40
• I should make the reminder, however, that downdating can be an unstable process. You'd want to check the condition of your newly-derived system after performing the downdate. – J. M. Jan 13 '12 at 10:41