18
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I guess your matrix needn't be symmetric? If it is, you can diagonalize it and look at the signs of the eigenvalues. $\endgroup$ – Pete L. Clark Dec 6 '10 at 19:34
  • $\begingroup$ 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). $\endgroup$ – pawelmysior Dec 6 '10 at 20:04
  • 1
    $\begingroup$ Good grief, eigendecomposition is the most expensive way of verifying positive definiteness... :o $\endgroup$ – J. M. is a poor mathematician Dec 6 '10 at 23:24
  • $\begingroup$ 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 :) $\endgroup$ – Lucy Marshall Jan 9 '11 at 2:34
  • $\begingroup$ 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. $\endgroup$ – pawelmysior Jan 9 '11 at 8:17
21
$\begingroup$

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 neither zero nor positive, 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.

$\endgroup$
  • $\begingroup$ Hmm, that I guess is the best (only reasonable) way to do that. Thanks ;] $\endgroup$ – pawelmysior Dec 7 '10 at 13:21
  • $\begingroup$ @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. $\endgroup$ – Inquest Jan 10 '13 at 19:06
  • $\begingroup$ @Inquest, the Cholesky decomposition is intended for Hermitian positive definite matrices, so if your language supports complex arithmetic, you shouldn't have any trouble... $\endgroup$ – J. M. is a poor mathematician Jan 16 '13 at 16:55
  • $\begingroup$ In practice you'll need some sort of zero tolerance- due to round off errors, a pivot that should be 0 will typically not be 0 and if it happens to be negative you could incorrectly conclude that the matrix isn't PSD. There are versions of Cholesky factorization with pivoting that are more reliable. $\endgroup$ – Brian Borchers Nov 1 '16 at 16:36
  • $\begingroup$ @Brian, right, variants with symmetric pivoting would be very useful if you're looking to construct a Cholesky-based test. (I also mentioned this in a comment to Dominique's answer.) $\endgroup$ – J. M. is a poor mathematician Jan 31 '17 at 15:21
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – J. M. is a poor mathematician Dec 7 '10 at 2:55
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – J. M. is a poor mathematician Dec 7 '10 at 2:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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