6
$\begingroup$

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?

  • 0
    Note: "sparse diagonal matrix" is a very redundant expression. ;)2010-08-30
  • 0
    How else would I imply a diagonal matrix with only very few of the diagonal nonzero though?2010-08-30
  • 0
    I would probably have used "low-rank diagonal matrix". :)2010-08-31
  • 0
    Ah thanks, that makes more sense.2010-08-31

1 Answers 1

6

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

  • 0
    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.2010-08-30