Sorry about the long title. I need to calculate the trace of $M(M+D)^{-1}$, where $M$ is a dense symmetric matrix, and $D$ is a diagonal matrix. The main issue is the dimension could be large (usually in the hundreds to thousands range) so computing the inverse could be quite expensive especially because the trace needs to be computed iteratively. Is there any efficient algorithm to do this?
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ This is close to: mathoverflow.net/questions/226132/… $\endgroup$– SuvritCommented Mar 10, 2016 at 19:35
-
1$\begingroup$ if $I$ would have been sparse, there are efficient techniques described here --- for a dense matrix you'll just have to compute the inverse and sum over the diagonal elements. $\endgroup$– Carlo BeenakkerCommented Mar 10, 2016 at 19:36
-
2$\begingroup$ If $M$ is low-rank, then this can be efficiently done using the Woodbury identity. $\endgroup$– Richard ZhangCommented Mar 10, 2016 at 19:42
-
1$\begingroup$ Is there any more information on $D$ vis-a-vis $M?$ Like, is $D+M$ diagonally dominant? Or the opposite? Is anything positive definite? $\endgroup$– Igor RivinCommented Mar 10, 2016 at 22:31
-
$\begingroup$ Let $v = tr(M (M+D)^{-1})$. Let $L := M+D$, then $v = tr((L-D)L^{-1}) = tr(I - DL^{-1}) = tr(I) - tr(L^{-1}D)$. So the problem is really just to solve $tr(L^{-1}D)$. To do something better than calculating all the diagonal values of $L^{-1}$ we need more constraints. The constraints can be of any form. Since you said that the trace needs to be computed iteratively then maybe $L$ is the result of some low rank update, in which case you might want to keep around some matrix decomposition and update it? In case you want ideas then just google for "diagonal entries of matrix inverse". $\endgroup$– PushpendreCommented Mar 11, 2016 at 0:30
Add a comment
|