chol() gives error for a (barely) positive definite matrix.
40 次查看(过去 30 天)
显示 更早的评论
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 个评论
回答(3 个)
Christine Tobler
2018-8-10
编辑:Christine Tobler
2018-8-10
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 个评论
Junho Kweon
2023-2-22
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.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!