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

Question

Kiran Sagar 2015-6-24

1
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/225177-chol-gives-error-for-a-barely-positive-definite-matrix

评论： Torsten 2023-10-13

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?

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Abdullah Yaqot 2018-8-9

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Christine Tobler 2018-8-10

7
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/225177-chol-gives-error-for-a-barely-positive-definite-matrix#answer_332354

编辑：Christine Tobler 2018-8-10

在 MATLAB Online 中打开

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.

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

Answer 2

Junho Kweon 2023-2-22

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/225177-chol-gives-error-for-a-barely-positive-definite-matrix#answer_1177460

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.