3
$\begingroup$

Suppose that $A$ is a symmetric positive definite matrix and assume its dimension $n$ is large. Let $I$ be the $n \times n$ identity matrix and $m \neq 0$ be a scalar. I'm interested in computing as many of the following as possible:

  • det$(A + mI)$
  • $(A + mI)^{-1}$
  • $(A + mI)^{-1}B$, where $B$ is an $n \times m$ matrix
  • the Cholesky decomposition of $A + mI$,

I'd like to do this for many values of $m$. However, because $n$ is large, I'd like to know if there is some update trick based on det$(A)$, $A^{-1}$, and the Cholesky decomposition of $A$. $A$ will likely not be sparse. I've been researching this for quite a while and the results haven't been all that encouraging.

Any help, hints, suggestions, or references would be much appreciated!

$\endgroup$
  • $\begingroup$ I don't have much hope either. You can precompute the SVD of $A$ which renders the first three easy, of course. $\endgroup$ – user7530 Mar 9 '15 at 0:59
  • $\begingroup$ If you're using python, scikit-sparse cholmod can compute the Cholesky $L L' = A A' + \beta I$ with parameter $\beta$. In C, I believe the underlying SuiteSparse can do that too, not sure. $\endgroup$ – denis Aug 4 at 16:16
1
$\begingroup$

Use the fact that symetric positive definite matrix is similar to a diagonal matrix with positive elements. More specifically, $$ P^{-1}AP = \operatorname{diag}\{a_1,...a_n\} $$ where $a_i>0$ for $i \in [1, n]$, diag{$a_1,...a_n$} is diagonal matrix, and $P $ is invertible. So We have

\begin{align} \det(A+mI)&=\det(P^{-1}(A+mI)P) \\ &=\det(P^{-1}AP+P^{-1}(mI)P) \\ &=\det(P^{-1}AP+P^{-1}P(mI)) \\ &=\det(P^{-1}AP+mI) \\ &=\prod \limits_{i=1}^{n}(a_i+m) \end{align}

Since $$ P^{-1}(A+mI)P = \operatorname{diag}(a_i+m) $$ And $$ \operatorname{diag}(a_i+m)^{-1}=\operatorname{diag}(\frac{1}{a_i+m}) $$ where $a_i+m\neq0$

Thus \begin{align} (P^{-1}(A+mI)P)^{-1}&=P(A+mI)^{-1}P^{-1} \\ &=\operatorname{diag}(a_i+m)^{-1} \\ &=\operatorname{diag}(\frac{1}{a_i+m}) \end{align}

And

$$(A+mI)^{-1}=P\operatorname{diag}(\frac{1}{a_i+m})P^{-1}$$

$\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.