9
$\begingroup$

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.

  • 1
    Would this be useful? It shows a way of updating the inverse when small changes are made to the matrix: http://www.alglib.net/matrixops/general/invupdate.php2012-10-06
  • 0
    Assuming your matrix is real matrix (all elements are real), you are guaranteed by spectral theorem that your matrix $A = QDQ^{T}$ where $D$ is diagonal and $Q$ is orthogonal. Getting this $Q$ is algorithmically Gram-Schimdt process (so rather simple).2012-10-06
  • 0
    @s.b yes, I'm aware; if that helps me invert the submatricies of $\Sigma$ (your $A$) then please tell me how, but as I said in my question I've already tried to figure out how to use the eigen decomposition to do it.2012-10-06
  • 0
    > I can tell you that there is a rank one update formula for finding > the inverse of a submatrix of one less dimension, which is to say the > matrix attained after deletion of any desired row and any desired > column. If you think it would be useful I could recite it for you > after I look it up exactly. I'm also interested in inverting this kind of matrices. If you could post the answer i would be glad. Thanks in advance, P2013-03-13
  • 0
    @user66612: I would be very happy to see it.2013-03-20

3 Answers 3