108 views (last 30 days)

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?

Christine Tobler
on 10 Aug 2018

Edited: Christine Tobler
on 10 Aug 2018

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.

Sign in to comment.

Sign in to answer this question.

Opportunities for recent engineering grads.

Apply Today
## 1 Comment

## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/225177-chol-gives-error-for-a-barely-positive-definite-matrix#comment_598269

⋮## Direct link to this comment

https://au.mathworks.com/matlabcentral/answers/225177-chol-gives-error-for-a-barely-positive-definite-matrix#comment_598269

Sign in to comment.