1
$\begingroup$

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

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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