I have a matrix $F=XDX^T$, where $D$ is $m\times m$ and diagonal and $X$ is $n\times m$.

Now, I compute $F^{-1}$.

Is there an efficient method to update $F^{-1}$ if $D$ is updated by $D'=D+G$, where $G$ is a sparse diagonal matrix?

  • $\begingroup$ Note: "sparse diagonal matrix" is a very redundant expression. ;) $\endgroup$ Aug 30 '10 at 11:23
  • $\begingroup$ How else would I imply a diagonal matrix with only very few of the diagonal nonzero though? $\endgroup$ Aug 30 '10 at 23:53
  • $\begingroup$ I would probably have used "low-rank diagonal matrix". :) $\endgroup$ Aug 31 '10 at 20:38
  • $\begingroup$ Ah thanks, that makes more sense. $\endgroup$ Aug 31 '10 at 22:09

Yes, there is a very efficient way to compute the updated $F^{-1}$. Begin by writing $X$ in terms of its columns: $X = [x_1 x_2 \dots x_m]$. It follows that: $$ XGX^T = \sum_{i=1}^{m} G_{ii} x_ix_i^T = \sum_{i\in S} G_{ii} x_ix_i^T $$ where $S \subset \{1,\dots,m\}$ is the set of indices for which $G_{ii}$ is nonzero. Suppose that $S$ contains $r$ indices. Since $G$ is sparse by assumption, $r$ is much smaller than $m$. If we assemble the columns of $X$ corresponding to indices in $S$, we obtain a new matrix $Y$, such that: $$ XGX^T = YHY^T $$ where $Y$ is $m \times r$, and $H$ is a diagonal matrix whose diagonal consists of all the nonzero entries along the diagonal of $G$. Now apply the Woodbury matrix identity: $$ (F+YHY^T)^{-1} = F^{-1} - F^{-1}Y(H^{-1}+Y^TF^{-1}Y)^{-1}Y^TF^{-1} $$ Computing the left-hand side directly is costly, as it requires inverting an $m\times m$ matrix. However, since $F^{-1}$ has already been computed, we can compute the right-hand side efficiently; the only inverse required is that of an $r\times r$ matrix, and $r$ is much smaller than $m$.

  • $\begingroup$ Note, however, that though $D$, $XDX^T$, and their inverses have the same inertia (via Sylvester), the "corrected" inverse may or may not have the same inertia (this depends on the nature of G). Though, it should hopefully be cheap to permute the entries of G (and the corresponding columns of X) such that all zero entries of G are in the trailing portion of the matrix, making SMW applicable. $\endgroup$ Aug 30 '10 at 11:35

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.