I'm working on a problem where I need to solve a large set of systems of equations, where each has a structure that looks like:
$\left( M^\top_{n\times p}\Sigma_{p\times p} M_{p\times n} + \Lambda_{n\times n}\right) x_{n\times 1} = b_{n\times 1}$,
where
Here $p \sim 30$ and $n \sim O(1e5)$
$\Sigma$ is a positive definite symmetric $p\times p$ matrix
$\Lambda$ is a positive definite diagonal $n\times n$ matrix
$M$ is a general $p\times n$ matrix.
Could anyone point me to techniques / algorithms for fast solutions of this problem. I'm open to non-iterative ( eg Cholesky type decompositions of the LHS matrix ), iterative and even approximate techniques.
Thanks.
Look for Sherman, Morrison and Woodbury. This one: https://en.wikipedia.org/wiki/Woodbury_matrix_identity (in generalization of https://en.wikipedia.org/wiki/Sherman%E2%80%93Morrison_formula) $$ \left(A+UCV \right)^{-1} = A^{-1} - A^{-1}U \left(C^{-1}+VA^{-1}U \right)^{-1} VA^{-1}. $$