6
$\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$
  • $\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 '14 at 10:39
  • 1
    $\begingroup$ "that how a positive semi-definite be done for Cholesky decomposition"??? What do you mean? $\endgroup$ – Dima Pasechnik Jan 20 '14 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 '14 at 11:46
  • $\begingroup$ Do you mean to ask why R has a Cholesky decomposition if and only if R is positive semidefinite? $\endgroup$ – Dima Pasechnik Jan 21 '14 at 15:55
  • 3
    $\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$ – Dima Pasechnik Jan 22 '14 at 20:08
6
$\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).

| cite | improve this answer | |
$\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".

| cite | improve this answer | |
$\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.