5
$\begingroup$

I have the Cholesky decomposition of a matrix $M$. However, I need the Cholesky decomposition of the inverse of the matrix, $M^{-1}$. Is there a fast way to do this, without first computing $M^{-1}$? In other words, is there a relationship between the Cholesky decompositions of a matrix and of its inverse?

My matrix is a covariance matrix and, hence, positive-definite.

$\endgroup$
2
$\begingroup$

If $L^T L = R$ is the available Cholesky decomposition, then inverting both sides of the equation you get,

$$L^{-1}(L^{T})^{-1} = R^{-1} $$

And since transposition and inverse are interchangeable:

$$L^{-1}(L^{-1})^{T} = R^{-1} $$

So if you define $P = (L^{-1})^T$ this is your desired answer. In other words,

$$P^{T}P=R^{-1}$$

$\endgroup$
  • 4
    $\begingroup$ The decomposition obtained here for $R^{-1}$ is not the Cholesky decomposition as the first factor ,$P^T$, is upper triangular (should be lower triangular). $\endgroup$ – Juho Kokkala Jan 29 '17 at 12:58
  • $\begingroup$ @JuhoKokkala Why does that matter? It is still triangular. $\endgroup$ – Rodrigo de Azevedo Jul 11 '18 at 17:33
  • $\begingroup$ Whether it matters in practice would depend on what you use the Cholesky factor for (not specified in the question). The question asks how to get the Cholesky decomposition of $M^{-1}$, and this answer gives some decomposition that (in the general case) is not the Cholesky decomposition. $\endgroup$ – Juho Kokkala Jul 11 '18 at 18:30
1
$\begingroup$

I do not believe there is any way to do it without some $O(n^3)$ operation. Different choices can have different constants. In particular, assuming $M=LL^T$ and you already have the Cholesky factor $L$, computing $L^{-1}$ costs ~$n^3/3$ flops, and given that, you can form $M^{-1}$ = $L^{-T}L^{-1}$ in ~$n^3/3$ flops and take its Cholesky in another ~$n^3/3$ flops, which is ~$n^3/3$ flops cheaper than pretending you don't have $L$, forming $M^{-1}$ directly and taking its Cholesky. But it's still $O(n^3)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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