Timeline for Efficiently calculate the trace of the product of two large but symmetric matrices, one of which is an inverse
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 11, 2016 at 0:30 | comment | added | Pushpendre | 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". | |
| Mar 10, 2016 at 22:31 | comment | added | Igor Rivin | Is there any more information on $D$ vis-a-vis $M?$ Like, is $D+M$ diagonally dominant? Or the opposite? Is anything positive definite? | |
| Mar 10, 2016 at 19:42 | comment | added | Richard Zhang | If $M$ is low-rank, then this can be efficiently done using the Woodbury identity. | |
| Mar 10, 2016 at 19:36 | comment | added | Carlo Beenakker | 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. | |
| Mar 10, 2016 at 19:35 | comment | added | Suvrit | This is close to: mathoverflow.net/questions/226132/… | |
| Mar 10, 2016 at 19:32 | history | edited | Suvrit | CC BY-SA 3.0 |
fixed notation; added tag
|
| Mar 10, 2016 at 19:18 | review | First posts | |||
| Mar 10, 2016 at 19:33 | |||||
| Mar 10, 2016 at 19:14 | history | asked | aenima | CC BY-SA 3.0 |