How to obtain the inverse of $MSM^T$ when $(MM^T)^{-1}$ is already known and $S$ is an invertible symmetric matrix?

Question

How to obtain the inverse of $MSM^T$ when $(MM^T)^{-1}$ is already known and $S$ is an invertible symmetric matrix? Assume that $M$ is an $n \times m$ matrix with $n \leq m$. Is it possible to obtain a matrix $N$ such that $(MSM^T)^{-1}=N(MM^T)^{-1}N$?

Answer 1

From a computational perspective, finding such an $N$ isn't known to be easier than just finding $(MSM^T)^{-1}$ from scratch. I have two arguments for why the existence of such a trick is implausible to me:

1. The computationally expensive step in interior-point algorithms for linear optimisation is solving $ADA^T d_y = r$ for $d_y$ where $A$ is a fixed matrix ("the left hand side") with more columns than rows. $D$ is a diagonal matrix that changes from iteration to iteration. IPMs solve these systems repeatedly; they'll typically do 20-100 iterations, each of which solves such a system. Competitive IPMs solve this system from scratch each time.

2. If I want to solve some positive definite linear system, say $AA^T = r$, all I need to do is pad $A$ out with some extra columns, say $B$, such that $AA^T + 2BB^T = \lambda I$. (I did not say I wanted to compute $B$.) Then $AA^T = MSM^T$ where $M = [A, B, B]$ and $S = \operatorname{Diag}(I, I, -I)$. If I can quickly find an $N$ such that $(MSM^T)^{-1} = N(MM^T)^{-1} N^T$, then I have $AA^T = (MSM^T)^{-1} = NN^T$---I can solve systems whose left-hand side is $AA^T$ rapidly without having done anything as expensive as a matrix multiplication.