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

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?

• I understand most of your question, but I don't understand this: "by schur completion, I want to margin $B'B+C'C$". What are you trying to say here? What do you mean by "margin"? – Omnomnomnom Jan 7 '19 at 2:03
• @Omnomnomnom thank you for your attention , basically margin means remove some target variable in optimization problem , you can refer it from g2o paper cct.lsu.edu/~kzhang/papers/g2o.pdf , equ(25) – Mr.Guo Jan 7 '19 at 2:10
• If $B$ (or $B^TB$) has low rank you can update the cholesky decomposition $C^TC$ – LinAlg Jan 7 '19 at 2:12
• @LinAlg yes B'B is not full rank , could you give me some more information about "update the cholesky decomposition" ? – Mr.Guo Jan 7 '19 at 2:15
• @LinAlg thank you for your hint, I think cholesky decomposition update should be work – Mr.Guo Jan 7 '19 at 2:24

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.

• cholesky factor update is a good idea, I'm using eigen , but I didn't find the rank one update for C, it only have interface for C'C which need mutiply first, so I think @Omnomnomnom 's idea is more fitting for me :) , I have listed the detail below – Mr.Guo Jan 7 '19 at 3:50
• @Mr.Guo what do you mean by "I didn't find the rank one update for C, it only have interface for C'C which need mutiply first"? – LinAlg Jan 7 '19 at 4:42
• I mean Eigen have no good interface for up-triangulate matrix rank-one update :) – Mr.Guo Jan 7 '19 at 9:32
• @Mr.Guo I think $C$ is of the LLT type with the UpLo flag set to upper, and that you can use this procedure. – LinAlg Jan 7 '19 at 13:11

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