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.

Improve this question
$\endgroup$

1 Answer 1

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

Improve this answer
$\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$
    – Federico Poloni
    Commented 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
    Commented 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$
    – Brian Borchers
    Commented May 1, 2011 at 16:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .