chol() gives error for a (barely) positive definite matrix.
95 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.