Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

1 Answer 1

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_{*}$.

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.