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