Updating the Cholesky factorization of when one or more columns are added to or removed from matrix can be done very efficiently obviating the re-factorization from scratch.
Assume we know the Cholesky factorisation of and we remove a column from matrix which can be written as follows
Once we delete the column at we have
from which we have that
The last equation is a rank-1 update (see Golub and Van Loan) and it comes at the
cost of .
Appending columns using permutation matrix
Having computed a Cholesky factorisation with permutation for the matrix , that is , we need to compute the Cholesky factorisation of , where .
From which we have that
and $\ell_1$ is computed from the following nice linear system
and, provided that , is positive definite and
Remark. to solve we do and we set so we then need to solve
The permuted Cholesky factor of is
and the corresponding permutation matrix is
The computational cost of this update is .
In this example we shall insert a column in , so we shall define the matrix
There is then a permutation matrix so that .
It is then easy to update the factorisation
which is the updated Cholesky factorisation of with permutation matrix .
Inserting many columns
Now we are going to insert many columns, recursively, at various positions in . Essentially, we are going to update a permuted Cholesky factorisation by inserting a column in any position in , so the updated matrix becomes
There is a permutation matrix so that
Say we have . We can then compute a permuted Cholesky factorisation for ,
which is the permuted Cholesky factorisation of with permutation matrix .
Let now be a given matrix and be a collection of column indexes of , and and we know the Cholesky factorisation of .
Let , i.e., the -th column of is added to to form the new matrix
Having augmented we can now update the factorisation of and compute an such that