2
$\begingroup$

Could you please let me know if there is a quick way to recompute result of a Cholesky decomposition of a covariance matrix, if the order of variables was switched to put a different variable as #1 on the list?

As a simple example, if the covariance matrix of random variables $(v_1,v_2,v_3,v_4)$ and its Cholesky decomposition are known, how can I quickly compute Cholesky decomposition of the covariance matrix of variables $(v_2,v_1,v_3,v_4)$? Note, $v_1$ was #1 on the list, and then the order of $(v_1,v_2)$ was switched to put $v_2$ as #1 on the list without changing the order of the other variables.

Thank you for your help!

$\endgroup$
3
  • $\begingroup$ Let your covariance matrix be $\Sigma$ and let $$P=\begin{bmatrix}&1&&\\1&&&\\&&1&\\&&&1\end{bmatrix}$$ be the matrix that swaps $v_1$ and $v_2$. Then the new covariance matrix is $P^T\Sigma P$. However, it does not seem likely that you can quickly compute its Cholesky decomposition. $\endgroup$
    – user856
    Commented Jun 10, 2016 at 15:49
  • $\begingroup$ The most relaxed requirement for me is to present the new covariance matrix in the form $U^TU$ such that there would be only one non-zero element in the first column of $U$. $\endgroup$
    – S.V
    Commented Jun 13, 2016 at 20:43
  • $\begingroup$ Answering my own question: an efficient update of a Cholesky decomposition can be done using Givens rotations or Householder transforms. $\endgroup$
    – S.V
    Commented Jun 14, 2016 at 21:31

2 Answers 2

1
$\begingroup$

Let C be the covariance matrix

    v1        v2          v3          v4
v1  1.0790   -0.0013      0.0321      0.0434
v2 -0.0013    0.9949     -0.0503      0.0494
v3  0.0321   -0.0503      0.9632      0.0008
v4  0.0434    0.0494      0.0008      0.9629

Then the choleskydecomposition gives L

v1   1.0387   0.0000      0.0000      0.0000
v2  -0.0012   0.9975      0.0000      0.0000
v3   0.0309  -0.0504      0.9796      0.0000
v4   0.0418   0.0496      0.0020      0.9791

and the cholesky-decomposition of C when v1 and v2 are reordered can be done by a rotation on the first two columns only:

v1 -0.0013   -1.0387      0.0000      0.0000
v2  0.9975    0.0000      0.0000      0.0000
v3 -0.0505   -0.0308      0.9796      0.0000
v4  0.0495   -0.0418      0.0020      0.9791

For instance by the MatMate commands

C = randomn(4,1000) *' /1000
L = cholesky(C)
L1 = rot(L,"drei",2´1,1..2)   // rotate on columns 1 and 2 only, use order v2´v1
                              // this is also the cholesky of C when v1 and v2
                              // exchange their places (but not in the output
                              // of the cholesky factor
$\endgroup$
2
  • $\begingroup$ Technically, what you provided with this method is some decomposition of the new matrix in the form $LL^T$, where $L$ is not necessarily lower (or upper) diagonal: this is exactly what Rahul wrote about. Have a look at your matrix: both $L1_{12}$ and $L1_{21}$ elements are not zero. This is why one needs to apply Givens rotations or Householder transforms on top of your result (which is what I implemented today): they allow one to make all or some elements on one side of the diagonal to be equal to zero. $\endgroup$
    – S.V
    Commented Jun 17, 2016 at 2:12
  • $\begingroup$ @S.V. : "... this is why one needs apply Givens rotations..." - yes, exactly this. It is such a standard procedure in many of my exercises and analyses that I just don't think much about it. $\endgroup$ Commented Jun 17, 2016 at 4:06
0
$\begingroup$

Such permutation is equivalent to row/column deletion at position i and then row/column insertion at position 1. This can be reduced to low rank modification of Cholesky factorization and can be done efficiently without recomputing Cholesky factorization.

See Davis, Timothy A., and William W. Hager. "Row modifications of a sparse Cholesky factorization." SIAM Journal on Matrix Analysis and Applications 26.3 (2005): 621-639 for detailed description how to reduce such permutation to low rank update of Cholesky factorization. For dense problem required numerical algorithms are available in Linpack (but not in Lapack)

$\endgroup$
1
  • $\begingroup$ I have spent several hours yesterday trying to make the Linpack function SCHEX to work. Somehow, it does not do what it promises to do - my conclusion was that either there is a bug in SCHEX or there is some linking problem between the FORTRAN shared library I have made and my C++ code. Had to implement the update using the Givens rotations myself. $\endgroup$
    – S.V
    Commented Jun 16, 2016 at 16:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .