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

55 ビュー (過去 30 日間)
Kiran Sagar
Kiran Sagar 2015 年 6 月 24 日
コメント済み: 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 件のコメント
Abdullah Yaqot
Abdullah Yaqot 2018 年 8 月 9 日
I have the same problem. It would be great to get a reply from mathworks.

サインインしてコメントする。

回答 (3 件)

Christine Tobler
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.

Junho Kweon
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.

aisha
aisha 2023 年 10 月 13 日
error in cholesky (line 9)
L(d,d)=sqrt(A(d,d)-L(d,1-N).^2);
  1 件のコメント
Torsten
Torsten 2023 年 10 月 13 日
It would help if you supplied the code where this error appears.

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeLinear Algebra についてさらに検索

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by