chol() gives error for a (barely) positive definite matrix.

I have a matrix whose smallest eigenvalue is positive but very close to zero (~ 1e-17). Theoretically, it should be a positive semi-definite matrix. But on using chol() function, it shows error that matrix is not positive definite.

As far as I know, cholesky decomposition is possible for positive semidefinite matrices. Is chol function capable of factorizing such matrices?

[Abdullah Yaqot]

I have the same problem. It would be great to get a reply from mathworks.

Answer 1

[Christine Tobler]

Short answer first: CHOL requires the input matrix to be positive definite, it does not support positive semi-definite. I'll explain below why this is more practical for numerical computations.

Other things you can do instead of Cholesky decomposition:

 % 1) Compute the LDL decomposition: A lower-triangular matrix L, 
 %    a block-diagonal matrix D (1-by-1 and 2-by-2 blocks),
 %    and a permutation matrix P, such that A is P*L*D*L'*P'
 [L, D, P] = ldl(A)

 % 2) Compute the eigenvalue decomposition, set its negative eigenvalues to zero,
 % and use QR to get two triangular factors for this modified matrix:
 [U, d] = eig(A, 'vector'); % A == U*diag(d)*U'
 d(d < 0) = 0; % Set negative eigenvalues of A to zero
 [~, R] = qr(diag(sqrt(d))*U'); % Q*R == sqrt(D)*U', so A == U*diag(d)*U'
                                %                         == R'*Q'*Q*R == R'*R
 % In this case, check that d(d<0) are all nearly zero.

 % 3) Ugly but quick: Just add a small number to A's diagonal before calling Cholesky
 R = chol(A + 1e-13*eye(size(A)));
 % Whether this is a bad thing to do depends on how you continue to use R.

I hope one of these will do what you need.

Why CHOL doesn't (and shouldn't) work for semi-definite matrices

The problem is round-off error. When we numerically compute the eigenvalue decomposition, the eigenvalues and eigenvectors are those of a matrix that is very close to A, but not exactly the same: let's call it A_eig. The same happens when we compute the Cholesky decomposition, whose factors will be close to another matrix close that is close to A, let's call it A_chol. In your case, A_eig is just about positive definite, but A_chol is indefinite (positive and negative eigenvalues) - but for another matrix, it could be the other way around.

The errors A - A_chol and A - A_eig are guaranteed to be small, but they have a big impact for a matrix that is just barely positive definite. So for these matrices, some work-around is needed to reliably treat them as if they were positive semi-definite.

Answer 2

[Junho Kweon]

There is quite well-developed code nearestSPD, which can solve the minor round-off error as @Christine Tobler mentioned. The code finds the nearest positive definite matrix. I had same issue, and this code solved the problem very well.

I hope this help for you too.

[Junho Kweon]

Check this @Abdullah Yaqot :)

Answer 3

[aisha]

error in cholesky (line 9)

L(d,d)=sqrt(A(d,d)-L(d,1-N).^2);

[Torsten]

It would help if you supplied the code where this error appears.