4
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ May 1, 2011 at 11:03
  • 1
    $\begingroup$ 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? $\endgroup$
    – R Turner
    May 1, 2011 at 11:06
  • $\begingroup$ 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 $\endgroup$ May 1, 2011 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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