Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
Note: "sparse diagonal matrix" is a very redundant expression. ;) –  J. M. Aug 30 '10 at 11:23
    
How else would I imply a diagonal matrix with only very few of the diagonal nonzero though? –  Projectile Fish Aug 30 '10 at 23:53
    
I would probably have used "low-rank diagonal matrix". :) –  J. M. Aug 31 '10 at 20:38
    
Ah thanks, that makes more sense. –  Projectile Fish Aug 31 '10 at 22:09

1 Answer 1

up vote 5 down vote accepted

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

share|improve this answer
    
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. –  J. M. Aug 30 '10 at 11:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.