12
$\begingroup$

We know that a positive definite matrix has a Cholesky decomposition,but I want to know how a Cholesky decomposition can be done for positive semi-definite matrices?The following sentences come from a paper. "There are two assumptions on the specified correlation matrix R. The first is a general assumption that R is a possible correlation matrix, i.e. that it is a symmetric positive semidefinite matrix with 1’s on the main diagonal. While implementing the algorithm there is no need to check positive semi-definiteness directly, as we do a Cholesky decomposition of the matrix R at the very start. If R is not positive semi-definite, the Cholesky decomposition will fail." Thank you for your answer.

$\endgroup$
8
  • $\begingroup$ THANK YOU .but here I want to know if a positive semi-definite can be done for Cholesky decomposition? and how? $\endgroup$
    – Purple
    Jan 20, 2014 at 10:39
  • 1
    $\begingroup$ "that how a positive semi-definite be done for Cholesky decomposition"??? What do you mean? $\endgroup$ Jan 20, 2014 at 11:28
  • $\begingroup$ excuse for my bad english."There are two assumptions on the specified correlation matrix R. The first is a general assumption that R is a possible correlation matrix, i.e. that it is a symmetric positive semidefinite matrix with 1’s on the main diagonal. While implementing the algorithm there is no need to check positive semi-definiteness directly, as we do a Cholesky decomposition of the matrix R at the very start. If R is not positive semi-definite, the Cholesky decomposition will fail." $\endgroup$
    – Purple
    Jan 20, 2014 at 11:46
  • 4
    $\begingroup$ en.m.wikipedia.org/wiki/Cholesky_decomposition has a proof that yes, indeed, it is correct, a p.s.d. R will have a Cholesky decomposition. $\endgroup$ Jan 22, 2014 at 20:08
  • 1
    $\begingroup$ Thank you for your answer.In Matlab Programming, the "chol" command can be used to simply apply this to only a positive definite matrix.When it comes to a positive semi-definite matrix,“chol” fails.I want to ask if there any command in Matlab Programming that can be used to a positive semi-definite matrix? $\endgroup$
    – Purple
    Jan 23, 2014 at 7:11

2 Answers 2

8
$\begingroup$

You can either:

  • use a LDL^T decomposition (see e.g. here)

  • deflate the kernel yourself before: that is, compute a basis $Q_2$ for the kernel, complete it to a square orthonormal matrix $Q=[Q_1 \, Q_2]$, and assemble $$ Q^TRQ=\begin{bmatrix}R_{11} & 0\\ 0 & 0\end{bmatrix}, $$ where $R_{11}$ is going to be nonsingular (and hence can be Cholesky-factored).

$\endgroup$
3
$\begingroup$

If you don't mind including some permutations, you can get a variant of Cholesky that still has the rank-revealing property:

$$P^T R P = R_1^T R, \quad R_1 = \begin{bmatrix} R_{11} & R_{22} \\ 0 & 0 \end{bmatrix}.$$

This is a matter of simple greedy pivoting. For the algorithm and more details, see Higham's "Cholesky Factorization".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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