1
$\begingroup$

I'm (reasonably) familiar with factoring a positive definite matrix $\mathbf{P} = \mathbf{L} \mathbf{L}^T = \mathbf{R}^T \mathbf{R}$, and is supported by MATLAB and Eigen.

However, I have also seen a factorization of the (same) $\mathbf{P} = \mathbf{U} \mathbf{U}^T = \mathbf{L'}^T \mathbf{L'}$

The following illustrates:

>> A = rand(3, 4)

A =

    0.2785    0.9649    0.9572    0.1419
    0.5469    0.1576    0.4854    0.4218
    0.9575    0.9706    0.8003    0.9157

>> P = A * A.'

P =

    1.9449    0.8288    2.0991
    0.8288    0.7374    1.4513
    2.0991    1.4513    3.3379

>> R = chol(P)

R =

    1.3946    0.5943    1.5052
         0    0.6198    0.8982
         0         0    0.5153

% This function computes such that U * U.' = A * A.'
% Part of: http://www.iau.dtu.dk/research/control/kalmtool2.html 
>> U = triag(A)

U =

   -0.7475    0.2571   -1.1489
         0   -0.3262   -0.7944
         0         0   -1.8270

>> P2 = R.' * R

P2 =

    1.9449    0.8288    2.0991
    0.8288    0.7374    1.4513
    2.0991    1.4513    3.3379

>> P3 = U * U.'

P3 =

    1.9449    0.8288    2.0991
    0.8288    0.7374    1.4513
    2.0991    1.4513    3.3379

I haven't seen this particular factorization $\mathbf{P} = \mathbf{U} \mathbf{U}^T$ before. I have a couple of questions:

  • Is it still, by definition, Cholesky factoriation? If not, what is it called?
  • Is the simple means to compute this particular variant (e.g. a MATLAB command)
  • Is there a specific relationship between $\mathbf{U}$ and $\mathbf{R}$?
$\endgroup$

1 Answer 1

3
$\begingroup$

You other item is not called Cholesky.

The Cholesky decomposition is unique: given a Hermitian, positive-definite matrix A, there is only one lower triangular matrix L with strictly positive diagonal entries such that A = LL*.

The quote is from http://en.wikipedia.org/wiki/Cholesky_decomposition

Cholesky is an example in the LU pattern, lower triangular on the left and upper triangular on the right, http://en.wikipedia.org/wiki/LU_decomposition

Wherever you found you code, it has switched the order. All you really know about your $U$ are things along the lines of $U^{-1} R'$ is an orthogonal matrix, but as it is not upper or lower triangular you must work at it to find anything interesting. Also, of course, the absolute values of the determinants of $U$ and $R$ are equal.

I have not worked up a complete proof yet, but it appears that your $-U$ is likely to be unique as well, factor in reverse order of Cholesky and demand strictly positive entries on the diagonal, all assuming we are factoring a positive definite symmetric.

$\endgroup$
8
  • $\begingroup$ I'm guessing that what OP might have seen is the Cholesky iteration for finding the eigenvalues of a Hermitian positive definite matrix, where the matrix is factored into its Cholesky triangle and its transpose, and then the two factors are multiplied in the reverse order: $\mathbf A_0=\mathbf A,\quad \mathbf A_k=\mathbf L\mathbf L^\top,\quad \mathbf A_{k+1}=\mathbf L^\top\mathbf L$. The iteration eventually converges to a diagonal matrix whose entries are the eigenvalues of $\mathbf A$. $\endgroup$ Commented Feb 18, 2012 at 5:47
  • $\begingroup$ @J.M., I don't really know. With more code than prose, I'm reading minds. I did not know about Cholesky iteration, seems cute. $\endgroup$
    – Will Jagy
    Commented Feb 18, 2012 at 6:12
  • 1
    $\begingroup$ Going by the note here that a symmetric matrix can be factored as $\mathbf A=\mathbf U\mathbf D\mathbf U^\top$ with $\mathbf U$ unit upper triangular and $\mathbf D$ diagonal, I think it follows that the "backwards Cholesky" done in the OP ought to be unique as well, if the entries of $\mathbf D$ are positive. $\endgroup$ Commented Feb 18, 2012 at 6:25
  • $\begingroup$ @J.M., thanks, looks good. It does appear to follow from induction on dimension. $\endgroup$
    – Will Jagy
    Commented Feb 18, 2012 at 7:08
  • 1
    $\begingroup$ If $A = L L^T$ then $A^{-1} = L^{-T} L^{-1} = U U^T$. There is an update formula for $U$ when one updates $A + a a^T$ with a rank-one update $a$ (see the reference to Kalman filters by @Damien). This would have been also possible with the Cholesky decomposition of $A^{-1}$ but I suppose the $U U^T$ decomposition of the inverse was chosen as it closer relates to the Cholesky decomposition of the original matrix. $\endgroup$
    – imix
    Commented Dec 21, 2019 at 18:26

You must log in to answer this question.

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