Alternative methods to compute the inverse of $ADA^T$ where $D$ is a diagonal matrix?

Question

Let's say I have an $m \times n$ matrix $A$ and a diagonal $n \times n$ matrix $D$. I'm running a program where $D$ gets updated on each iteration for thousands of iterations, but $A$ stays the same throughout. At each iteration, I need the inverse $(ADA^T)^{-1}$. If possible, I would like to avoid a full recalculation of the inverse at every iteration. Would there be a way to update or recalculate the inverse using the new diagonal entries in $D$ at each iteration?

Answer 1

If you change the diagonal entries one at a time, then you can iteratively apply rank-one updates to the inverse.

Let $d_1,\dots,d_n$ denote the diagonal entries of $D$. We can write $$ ADA^T = \sum_{i=1}^n d_i \, a_ia_i^T, $$ where $a_i$ denotes the $i$th column of $A$. Let $\bar D$ denote a matrix for which $d_i$ has been changed to $\bar d_i$, and no other changes have been made. The Sherman-Morrison formula tells us that $$ \begin{align} (A\bar D A^T)^{-1} &= (AD A^T + (\bar d_i - d_i)a_ia_i^T)^{-1} \\ &= (ADA^T)^{-1} - \frac{(ADA^T)^{-1}a_ia_i^T(ADA^T)^{-1}}{(\bar d_i - d_i)^{-1} + a_i^T(ADA^T)^{-1}a_i} \end{align} $$

---

Another optimization: let $R$ denote the reduced row-echelon form of $A$, and let $P$ be an invertible matrix such that $A = PR$. It follows that $$ (ADA^T)^{-1} = (PRDR^TP^T)^{-1} = P^{-T}(RDR^T)^{-1}P^{-1}. $$ Thus, it suffices to find $RDR^T$ inverse rather than computing $ADA^T$ inverse directly.

Note that some of the columns of $R$ will be sparse. For these columns, the products to be computed in the formula for the rank-1 update of $R$ will be relatively quick.

---

Here is an approach which I think helps in terms of speed but potentially require a lot of memory. I assume that all columns of $A$ are non-zero.

For each $i = 1,\dots,n$, let $P_i$ be any invertible matrix such that the $i$th column of $R_i := P_i A$ is a standard basis vector. Starting with $ADA^T$, compute $$ P_i^{-T}(ADA^T)^{-1}P_i^{-1} = (R_iDR_i^T)^{-1} $$ From there, we can (relatively) compute an update over the $i$th column. To return from $(R_iDR_i^T)^{-1}$ to $(ADA^T)^{-1}$, just compute $P_i^T(R_iDR_i^T)^{-1}P_i$.