Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to create a program, that will decompose a matrix using the Cholesky decomposition.

The decomposition itself isn't a difficult algorithm, but a matrix, to be eligible for Cholesky decomposition, must be symmetric and positive-definite. Checking whether a matrix is symmetric is easy, but the positive part proves to be more complex.

I've read about the Sylvester's criterion, but that leads to determinants, and based on what I found on the web, those are quite extensive and hard on computers.

In a nutshell - is there something I might be missing? Due to the fact the the matrix is square or something like that, is there possibly a simpler way to determine whether it's positive?

Regards, Paul

share|improve this question
    
I guess your matrix needn't be symmetric? If it is, you can diagonalize it and look at the signs of the eigenvalues. –  Pete L. Clark Dec 6 '10 at 19:34
    
Well, it actually has to be symmetric for Cholesky decomposition, I wrote square, was thinking about symmetric, updated question. Could You simplify your comment (I'm not an English native). –  PawelMysior Dec 6 '10 at 20:04
1  
Good grief, eigendecomposition is the most expensive way of verifying positive definiteness... :o –  J. M. Dec 6 '10 at 23:24
    
I have exactly the same problem - trying to do a Cholesky decomposition in Matlab, but need some sort of test at the beginning to show if the matrix is positive. Did you manage to get a fast way of working it out in the end? Thanks :) –  Lucy Marshall Jan 9 '11 at 2:34
    
Well, I basically went with the idea of using the Cholesky decomposition to check whether the matrix is positive. Just make sure that there is no zero in the denominator and that the number to be squared isn't negative. –  PawelMysior Jan 9 '11 at 8:17
add comment

4 Answers 4

up vote 18 down vote accepted

Mathcast had it; in fact, in practical work, one uses the Cholesky decomposition $\mathbf G\mathbf G^T$ for efficiently testing if a symmetric matrix is positive definite. The only change you need to make to turn your decomposition program into a check for positive definiteness is to insert a check before taking the required square roots that the quantity to be rooted is positive. If it is zero, you have a positive semidefinite matrix; if not, then your symmetric matrix isn't positive (semi)definite. (Programming-wise, it should be easy to throw an exception within a loop! If your language has no way to break a loop, however, you have my pity.)

Alternatively, one uses the $\mathbf L\mathbf D\mathbf L^T$ decomposition here (an equivalent approach in the sense that $\mathbf G=\mathbf L\sqrt{\mathbf D}$); if any nonpositive entries show up in $\mathbf D$, then your matrix is not positive definite. Note that one could set things up that the loop for computing the decomposition is broken once a negative element of $\mathbf D$ is encountered, before the decomposition is finished!

In any event, I don't understand why people are shying away from using Cholesky here; the statement is "a matrix is positive definite if and only if it possesses a Cholesky decomposition". It's a biconditional; exploit it! It's exceedingly cheaper than successively checking minors or eigendecomposing, FWIW.

share|improve this answer
    
Hmm, that I guess is the best (only reasonable) way to do that. Thanks ;] –  PawelMysior Dec 7 '10 at 13:21
    
@J.M, just stumbled upon this. Does the matrix need to be real for this method to work? I have my own subroutine to check for positive numbers when taking roots but one of my matrices turned out to be complex and the algorithm went south. –  Inquest Jan 10 '13 at 19:06
    
@Inquest, the Cholesky decomposition is intended for Hermitian positive definite matrices, so if your language supports complex arithmetic, you shouldn't have any trouble... –  J. M. Jan 16 '13 at 16:55
add comment

I don't think there is a simpler way than computing a decomposition or determinant unless your matrix has a special form. For example if it is a sample covariance matrix then it is positive semidefinite by construction.

share|improve this answer
    
Sample covariance matrices $\mathbf A^T\mathbf A$ are positive definite if $\mathbf A$ has full column rank, and positive semidefinite if $\mathbf A$ is rank deficient. The fact that he wants to Cholesky decompose a matrix already presupposes the matrix is symmetric to begin with, since Cholesky is only defined for those. Isn't being symmetric "special" enough for you? –  J. M. Dec 7 '10 at 2:55
add comment

Other possibilities include using the conjugate gradient algorithm to check positive-definiteness. In theory, this method terminates after at most n iterations (n being the dimension of your matrix). In practice, it may have to run a bit longer. It is trivial to implement. You can also use a variant of the Lanczos method to estimate the smallest eigenvalue of your matrix (which is much easier than computing all eigenvalues!) Pick up a book on numerical linear algebra (check the SIAM collection.)

At any rate recall that such methods (and the Cholesky decomposition) check numerical positive-definiteness. It is possible for the smallest eigenvalue of your matrix to be, say, 1.0e-16 and for cancellation errors due to finite-precision arithmetic to cause your Cholesky (or conjugate gradient) to break down.

share|improve this answer
1  
Yes, and for very reliable cheap checking of positive-definiteness, one usually uses a pivoted version of Cholesky. See this and this LAPACK routine. –  J. M. Dec 28 '10 at 0:56
add comment

Perhaps someone has an iterative approach or some other approximate approach, but it looks like to be sure, one has to calculate determinants and apply Sylvester's criterion (as you pointed out).

Sylvester's states that iff, for all $k<n$, the $\det(A_k) > 0$, where $A_k$ is the $k$'th principal minor, then the matrix is positive definite. The only deterministic, efficient, algorithm to calculate determinants that I know of is the Bareiss algorithm, for which you can see Bareiss's original paper or Chee Yap's excellent reference here.

The Bareiss algorithm, in its intermediate steps, ends up calculating the determinant of the $k$ minors of the matrix for all $k<n$, so you get a simple test for positive definiteness should you end up implementing the Bareiss algorithm yourself.

I'd be interested to know if there are any iterative methods that would give you some confidence of a matrix's positive-definiteness.

share|improve this answer
    
Bareiss is alright for exact integer entries; in inexact arithmetic, LU decomposition remains the best way to get the determinant of a dense unstructured matrix. Still, it is an inefficient way to verify positive definiteness, but certainly not as flagrantly expensive as eigendecomposition. –  J. M. Dec 7 '10 at 2:57
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.