# 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.

-

## 1 Answer

Computing $L_{*}^{-1}$ from $L_{*}$ takes only $O(n^2)$ time.

If you can afford the two matrix-matrix multiplications (which are $O(n^3)$ but parallelize and use cache very efficiently), then that might be the quickest way to proceed. Unless $n$ is very large, it might not be worth considering any other approach.

For a true $O(n^2)$ approach, you might want to look at the "product form Cholesky Factorization" approach to rank-1 updates. I believe that this would give you the updated factorization in a form that could be applied to get $S_{*}$.

-
Seconded. As usual with computations that involve inverses, you need to ask yourself "do I really need to compute this inverse element-by-element, or can I store it in some factored form that still allows to compute matvec products in $O(n^2)$ and matmat in $O(n^3)$?". In most cases, the second option holds, and the factored form is faster and stabler. – Federico Poloni May 1 '11 at 11:03
Thanks, Solving $L x = y$ is $O(n^2)$, but it seems that computing $L^{-1}$ would require solving that system for each unit vector and thus be $O(n^3)$ unless there are some tricks I am unaware of. They don't seem to be implemented in matlab if they exist. What are the best references to solving this problem using the product form Cholesky? – R Turner May 1 '11 at 11:06
My oops- I had thought there was an $O(n^2)$ way to get the inverse of a lower triangular matrix but my memory was faulty. Sorry about that. For the product form cholesky factorization, look at the 2005 paper by Goldfard and Scheinberg, "Product-form Cholesky factorization in interior point methods for second-order cone programming" and follow references back from there. See portal.acm.org/citation.cfm?id=1058105 – Brian Borchers May 1 '11 at 16:21