CODEWITHSUNDEEP
matlablinear-algebra
arbitUser1401
arbitUser1401

Reputation: 575

Checking whether a matrix is SPD

What will be the quickest (run time) way to check whether a matrix is symmetric positive definite in Matlab? I have run this test for a large number of sparse matrices whose size (dimension) varies from 10000 to 100000?

Edit:

Cholesky is exorbitantly costly for my purpose. I need a dirty check first if it gives an indication that matrix might be spd then I might check only those matrix more reliably using CHOL

Upvotes: 4

Views: 8803

Answers (5)

Emmet
Emmet

Reputation: 6411

You might be able to thin the field a bit by eliminating some matrices from consideration using Gershgorin's Theorem, used for estimating eigenvalues.

The upshot is that if you sum the absolute values of the elements on each row (other than the one on the diagonal), k, you get a radius, rk. The corresponding eigenvalue must lie within that radius of the value on the diagonal, akk. So, if akk > rk for all k, your matrix is PD. If akk <= rk for some k, your matrix might still be PD because all this means is that one or more of the Gershgorin disks straddles the imaginary axis (or zero) and the actual eigenvalue could be on either side.

Assuming issymmetric(A) succeeds, something like:

r = sum(abs(A),2)-diag(A);
if length(find(r>diag(A))) == 0,
    % No circles cross the origin: A is PD
else
    % A might still be PD: do some other test
end

A quick'n'dirty test of this with matrices M=sprandsym(n,n,d)+c*speye(n,n), some of which are PD and some of which are not (twiddling n, d, and c), seems to indicate that it identifies many, but not all, SPD matrices (as expected), but is very cheap compared to eig() (and its underlying Cholesky) for "large" n. For your particular matrices, it might work or it might not. YMMV, I guess.

I haven't worked out all the details, obviously, but I'm sure you get the idea.

Upvotes: 0

Dana Massie
Dana Massie

Reputation: 1

Regarding the trace test mentioned above: Assume matrix A is:

A =
    1.0000    1.6000
    1.6000    1.0000

Then the 

trace(A) is 2

But the eigenvalues of A are eig(A)

ans =
   -0.6000
    2.6000

Thus the eigenvalues are not all positive. Therefore this matrix is not SPD yet its trace > 0. I suspect, based on this counter example, that the trace test is not conclusive.

Upvotes: 0

Stochastically
Stochastically

Reputation: 7846

I think this is a non-trivial problem to do it efficiently. The Cholesky algorithm will fail if the matrix is not positive definite, so it may be best to implement oneself, which would also have the advantage that one would have control over what to do when the algorithms fails because the input isn't positive definite. I use C# rather than Matlab for my mathematical programming, and my Cholesky implementation is only a handful of lines, so it's not difficult. If you use someone else's algorithm then depending on how it's implemented, if you feed in a non-symmetric matrix you may get misleading results, because some implementations assume that the matrix is symmetric. The only quick pre-test that I can think of would be to check the matrix trace, which will be positive if the matrix is SPD.

Upvotes: 2

fpe
fpe

Reputation: 2750

I think you may have a look at the eigenvalues of your matrix, and check whether they are all distinct and real valued.

You may, therefore, think to call eig function as follows:

[V,D] = eig(A)

I hope this helps

Upvotes: 1

Mikhail
Mikhail

Reputation: 21749

As stated here, you can use chol function to check whether a matrix is PD.

The CHOL function provides an optional second output argument "p" which is zero if the matrix is found to be positive definite. The CHOL function will return an error if it is only provided with a single output argument, and is also given a matrix that is not positive definite. NOTE: CHOL expects its input matrix to be symmetric and only looks at the upper triangular portion of the matrix.

As for symmetry, you can use the following function:

issym = @(m) isequal(tril(x), triu(x)');

Upvotes: 3

Related Questions