Are there any decompositions of a symmetric matrix that allow for the inversion of any submatrix?

Question

I am given a $J \times J$ symmetric matrix $\Sigma$. For a subset of $\{1, ..., J\}$, $v$, let $\Sigma_{v}$ denote the associated square submatrix. I am in need of an efficient scheme for inverting $\Sigma_v$ for potentially any subset $v$. Essentially, I will have to invert many different submatricies $\Sigma_v$, but I won't know which ones I need to invert in advance of running some program; I would rather invest in a good matrix decomposition at the outset, if one exists (or otherwise get whatever information necessary, if not a decomposition).

I've messed around with the eigen decomposition a little bit, but wasn't able to coerce the inverse of a submatrix out of it.

UPDATE: Apparently the term for the type of submatricies I want to invert is "principal submatrix". I'm wondering if I can't make some progress on this via the Cholesky decomposition. Suppose I'm content to calculate $\Sigma_{jj} ^ {-1}$ for any $j \in \{1, 2, ..., J\}$, where $\Sigma_{jj}$ denotes the submatrix obtained by deleting rows/columns greater than $j$. Write $\Sigma = LL^T$ and let $Q = L^{-1}$. Write $$ L = \begin{pmatrix}L_1 & \mathbf 0 \\ B & L_2\end{pmatrix}, Q = \begin{pmatrix}Q_1 & \mathbf 0 \\ C & Q_2\end{pmatrix} $$ where $L_1$ and $Q_1$ and $j \times j$. It follows that $\Sigma_{jj} = L_1 L_1^T$ and $Q_1 = L_1 ^{-1}$ so that $\Sigma_{jj} ^{-1} = Q_1^T Q_1$. So, once I have the Cholesky decomposition I have the inverses of the leading principal submatricies. This doesn't solve the problem as stated since I may need to deal with other principal submatricies, but it should be a useful partial solution.

Answer 1

I imagine the best you can do is only one rank at a time building up or down to attain the desired sub-matrix portion. The simple formula is

$$\mathbf{A}^{-1} = E - \frac{\mathbf{f}\mathbf{g}^T}{h}$$

Where $$\pmatrix{\mathbf A & \mathbf b\\ \mathbf c^T & d}^{-1} = \pmatrix{\mathbf E & \mathbf f\\ \mathbf g^T & h}$$

To derive it we will use Bitwise's helpful comment; the formula $$(A + uv^T)^{-1}=A^{-1}-\frac{(A^{-1}u)(v^TA^{-1})}{1 + v^TA^{-1}u}$$ which shows the rank one aspect of the update relative to the already known inverse. If you use this with sub-matrices in mind, care would have to be given for how to reduce the dimension of $A$, this formula is not directly applicable for that; it does not show how to update a row and a column at once since that is not a rank one update. But it becomes necessary in the derivation.

You have as your knowns the conformably partitioned matrix and its inverse: $$\pmatrix{\mathbf A & \mathbf b\\ \mathbf c^T & d} \pmatrix{\mathbf E & \mathbf f\\ \mathbf g^T & h} = \pmatrix{ \mathbf I & \mathbf 0 \\ \mathbf 0^T & 1}$$ And you want to find the quantity $A^{-1}$. First see that $ AE + \mathbf {bg}^T = \mathbf I$ Is the top left element of their multiple. Then:

\begin{align} AE + \mathbf {bg}^T &= \mathbf I \\ AE &= \mathbf I - \mathbf {bg}^T \\ AE\left(\mathbf I - \mathbf {bg}^T\right)^{-1} &= \mathbf{I} \\ \Rightarrow A^{-1} &= E\left(\mathbf I - \mathbf {bg}^T\right)^{-1} \end{align}

The inverse for $\mathbf{A}$ then is the matrix $E(\mathbf I-\mathbf {bg}^T)^{-1}$. The rank one formula may now be used to find the necessary elements. \begin{align} \mathbf{A}^{-1} & = E\left(\mathbf I - \mathbf {bg}^T\right)^{-1} \\ & =E\left(\mathbf I + \mathbf {(-b)g}^T\right)^{-1} \\ & =E\left(\mathbf I - \frac{\mathbf {(-b)g}^T}{1 + \mathbf{g}^T(-\mathbf{b})}\right) \\ & =E\left(\mathbf I + \frac{\mathbf {bg}^T}{1 - \mathbf{g}^T\mathbf{b}}\right) \\ & =E + \frac{(E\mathbf {b})\mathbf{g}^T}{1 - \mathbf{g}^T\mathbf{b}} \\ \end{align}

How about some further reducing: $$ \pmatrix{\mathbf E & \mathbf f\\ \mathbf g^T & h}\pmatrix{\mathbf A & \mathbf b\\ \mathbf c^T & d} = \pmatrix{ \mathbf I & \mathbf 0 \\ \mathbf 0^T & 1} $$ \begin{align} E\mathbf{b} + \mathbf{f}d & = 0 \\ E\mathbf{b} &= -\mathbf{f}d \\ \text{and}\quad \mathbf{g}^Tb + hd &= 1 \\ \mathbf{g}^T\mathbf{b} &= 1 - hd \\ 1 - \mathbf{g}^T\mathbf{b} &= hd \\ \Rightarrow \mathbf{A}^{-1} &= E + \frac{-\mathbf{f}d\mathbf{g}^T}{hd} \\ &= E - \frac{\mathbf{f}\mathbf{g}^T}{h} \\ \end{align}

And you have your rank one update of the sub-matrix portion, repeated here for convenience:

$$\mathbf{A}^{-1} = E - \frac{\mathbf{f}\mathbf{g}^T}{h}$$

To go the other direction (adding a row and column) you can use what is called the bordering method as described in this answer