Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$B_{(n+1)(n+1)}$ = $ \begin{bmatrix} A & u \\ u^T & 1 \\ \end{bmatrix}$ = $\begin{bmatrix} L_{11} & 0 \\ L_{21} & l_{22} \\ \end{bmatrix} $ $\begin{bmatrix} L_{11}^T & L_{21}^T \\ 0 & l_{22} \\ \end{bmatrix} $

Here A is nxn matrix, $l_{22}$ is scalar, $L_{11}$ is also a nxn matrix. So Cholasky factorization of this B matrix will give us the following: $L_{11}*L_{11}^T=A, L_{11}*L_{21}^T=u, L_{21}*L_{11}^T=u^T$, and $L_{21}*L_{21}^T=1-l_{11}^2$

  1. What to do after this?

  2. Is the factorization done?

  3. If this is done, how can I compute B's complexity(flops) if A is given - lets say it is N?

Thanks.

share|improve this question
    
That's basically the outer product formulation of Cholesky decomposition. Watkins's book has a discussion on this. –  J. M. Oct 28 '12 at 4:55
add comment

1 Answer

up vote 1 down vote accepted

Well, regarding 1, $L_1$ is computed as per the standard cholesky factorisation for $A$. Then from your working, you get $L_{21}^T=L_{11}^{-1}u$ and $l_{22}=\sqrt{1-L_{21}L_{21}^T}$.

For 2, now the factorisation is complete as you have determined what they factors should be.

For 3, the complexity for the determination of $L_{11}$ is known for the Cholesky decomposition. Then you just have to increment it for the additional computations which you incur.

share|improve this answer
    
so then $L_{11}$ should be such a matrix that its transpose is equal to itself.... does this tell you anything? I guess symmetric But then how can i decompose if matrix A is not given –  ASROMA Oct 27 '12 at 23:08
    
If $A$ is not given, then you can't do anymore than I said, where $L_{11}$ is the cholesky factor of $A$. Once you know it, then you can extend the factorisation to an additional dimension, as I describe above. –  Daryl Oct 28 '12 at 1:59
    
OH, it says that Cholesky decomposition of A is given $A=L*L^T$, but then what does it mean $L_{11}L_{11}=L*L^T$ ? –  ASROMA Oct 28 '12 at 2:23
    
You have a mistake. In the second matrix, the $(1,1)$ block should be $L_{11}^T$. Also, above, if $L_{11}L_{11}^T=LL^T$, then, $L_{11}=$? –  Daryl Oct 28 '12 at 3:34
    
ok thanks, how did i missed that ??? –  ASROMA Oct 28 '12 at 4:53
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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