the inverse of a sum of two symmetric for schur completion?

Question

I have a up-triangulate Jacobi matrix J which can be blocked like :

$J = \begin{bmatrix}A & B\\ 0 & C\end{bmatrix} $

both A and C are up-triangulate, we can get Hessian matrix H by:

$H = J'J =\begin{bmatrix}A' & 0\\B'&C'\end{bmatrix} \begin{bmatrix}A & B\\ 0 & C\end{bmatrix} = \begin{bmatrix}A'A & A'B\\B'A & B'B+C'C\end{bmatrix} $

by schur completion, I want to margin $B'B+C'C$, the equation is:

$ A'A - A'B(B'B+C'C)^{-1}B'A $

I know $C^{-1}$ is easy computed because it's a up-triangulate matrix, but unfortunately the add ruin this equation.

I have found that $ X(X^{-1}+Y^{-1})Y = (X^{-1}+Y^{-1})^{-1} $ only when both X and Y are invertible, which B'B dose not meet

so any one have some brilliant idea to compute this equation easily?

Answer 1

To compute $X:=(B^TB+C^TC)^{-1}B^TA$, you never actually compute $(B^TB+C^TC)^{-1}$, but instead you solve $(B^TB+C^TC)X=B^TA$. Since $C$ is upper triangular, you can see $C^T$ as the Cholesky factor of $C^TC$. You can update the Cholesky factor $C^T$ to account for the low rank update $B^TB$ (via repeated rank-1 updates). That will give you a new Cholesky factor $L$ such that $LL^T = B^TB+C^TC$. Then all you need to do is solve $LL^TX = B^TA$, which is relatively easy.

Answer 2

hi @Omnomnomnom you have given me a better hint to solve this problem , I'd like to list it here I have checked your equation it's correct except one little mistaken, it should be:

$ (C'C+B'B)^{-1} = (C'C)^{-1} - (C'C)^{-1}B'(I+B(C'C)^{-1}B')^{-1}B(C'C)^{-1} $

I think it's a good solution because B is (small rows * big cols) matrix, we can get

$D = (C'C)^{-1}$

$E = BDB'$

$F = (I+E)^{-1}$

D,E,F are all easy computed, so the result is :

$ (C'C+B'B)^{-1} = D - DB'FBD $

and finally,

$ result = A'A-A'B(B'B+C'C)^{-1}B'A = A'(I-B(B'B+C'C)^{-1}B')A = A'(I-BDB' + BDB'FBDB')A = A'(I-E+EFE)A$