1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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"? $\endgroup$ – Omnomnomnom Jan 7 at 2:03
  • $\begingroup$ @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) $\endgroup$ – Mr.Guo Jan 7 at 2:10
  • $\begingroup$ If $B$ (or $B^TB$) has low rank you can update the cholesky decomposition $C^TC$ $\endgroup$ – LinAlg Jan 7 at 2:12
  • $\begingroup$ @LinAlg yes B'B is not full rank , could you give me some more information about "update the cholesky decomposition" ? $\endgroup$ – Mr.Guo Jan 7 at 2:15
  • $\begingroup$ @LinAlg thank you for your hint, I think cholesky decomposition update should be work $\endgroup$ – Mr.Guo Jan 7 at 2:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mr.Guo Jan 7 at 3:50
  • $\begingroup$ @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"? $\endgroup$ – LinAlg Jan 7 at 4:42
  • $\begingroup$ I mean Eigen have no good interface for up-triangulate matrix rank-one update :) $\endgroup$ – Mr.Guo Jan 7 at 9:32
  • $\begingroup$ @Mr.Guo I think $C$ is of the LLT type with the UpLo flag set to upper, and that you can use this procedure. $\endgroup$ – LinAlg Jan 7 at 13:11
1
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.