Timeline for Efficiently compute the trace of a sparse matrix times the inverse of a sparse matrix?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2015 at 18:37 | comment | added | Jeff | @user35593 $A$ and $B$ are both positive semidefinite---I've added that to the description now. (They are precision matrices of multivariate normal distributions.) They aren't necessarily that close: $A$ is the inverse covariance of a prior distribution and $B$ is the inverse covariance of an approximation to the posterior distribution. | |
| Dec 15, 2015 at 18:33 | history | edited | Jeff | CC BY-SA 3.0 |
added PSD
|
| Dec 15, 2015 at 18:29 | answer | added | Suvrit | timeline score: 3 | |
| Dec 15, 2015 at 18:15 | comment | added | user35593 | Do you have any additional information on $A$ and $B$? Are they positive definite? Are $A$ and $B$ close in some sense? I think the general case is rather difficult. | |
| Dec 15, 2015 at 17:47 | comment | added | Pushpendre | one "slightly" better than brute force approach to compute $AB^{-1}$ would be to compute only those cofactors of $B$ that would get multiplied with rows of $A$. There is work on determinants of sparse matrices that can get us started . but the worst case complexity of this method is still at least $n^2$ | |
| Dec 15, 2015 at 17:12 | comment | added | Jeff | @CarloBeenakker -- I removed the parenthetical about B approximating A, and quantity of interest being a measure of the quality of the approximation. It's better to think of the quantity of interest as a term in an objective function that I'm trying to minimize. | |
| Dec 15, 2015 at 17:07 | history | edited | Jeff | CC BY-SA 3.0 |
removed parenthetical comment about B approximating A
|
| Dec 15, 2015 at 7:36 | comment | added | Federico Poloni | @CarloBeenakker Good point. I have some issues with a measure under which $A=I$ and $A=\begin{bmatrix}1 & 10^6\\ 10^6 & 1\end{bmatrix}$ both approximate equally well $B=I$. (One can play around and find examples with the same nonzero pattern, too.) | |
| Dec 15, 2015 at 7:09 | comment | added | Carlo Beenakker | if you just want to measure how well $B$ approximates $A$, why not use the Frobenius norm ${\rm tr}\,[(A-B)(A-B)^t]$ ? | |
| Dec 15, 2015 at 6:59 | history | asked | Jeff | CC BY-SA 3.0 |