Skip to main content
2 of 2
added 116 characters in body

Cholesky Rank-1 downdate extension

If we have a matrix $K$ we can take do a rank-1 downdate of its Cholesky $L = chol(K)$ to find $L_\star = chol(K - v v^\top)$ in $O(N^2)$ time as opposed to $O(N^3)$ time for doing the Cholesky from scratch. It is even implemented in the MATLAB command cholupdate(L',v,'-').

Now, I need to find a similar, but trickier quantity. If I have another matrix $D$, we define $S = L^{-1} D L^{-\top}$. How can I compute $S_{\star}$ where $S_\star = L_\star^{-1} D L_\star^{-\top}$, given I have already computed $L$, $L_\star$, and $S$ and $K$, $v$, and $D$ are given in $O(N^2)$ time? Computation from scratch would be $O(N^3)$ since it involves solving 2 matrix-matrix systems.

Clarifications: $K$ is pos. def., $L$ and $L_\star$ are lower triangular, $D$, $S$ and $S_\star$ are symmetric.