IsPSD

	IsPSD
	Determines whether or not a matrix is positive semidefinite
Other toolboxes required	opt_args
Related functions	IsCP; IsPPT; IsTotallyPositive

IsPSD is a function that determines whether or not a given matrix is positive semidefinite. The input matrix can be either full or sparse and, if requested, a vector that proves that the given matrix is not positive semidefinite can be provided as output.

Syntax

PSD = IsPSD(X)
PSD = IsPSD(X,TOL)
[PSD,WIT] = IsPSD(X,TOL)

Argument descriptions

Input arguments

X: A square matrix.
TOL (optional, default eps^(3/4)): The numerical tolerance used when determining positive semidefiniteness. The matrix will be determined to be positive semidefinite if its minimal eigenvalue is computed to be at least -TOL.

Output arguments

PSD: A flag (either 1 or 0) indicating that X is or is not positive semidefinite.
WIT (optional): An eigenvector corresponding to the minimal eigenvalue of X. When PSD = 0, this serves as a witness that verifies that X is not positive semidefinite, since WIT'*X*WIT < 0.

Examples

Simple example with low tolerance

When X is very simple, positive semidefiniteness can be be determined exactly. The following example has the TOL = 0 (not recommended in general!) to highlight the fact that the script really is checking for positive semidefiniteness, not positive definiteness.

>> X = diag([1 0])

X =

     1     0
     0     0

>> IsPSD(X,0)

ans =

     1

Furthermore, if we make one of the eigenvalues even slightly negative in this case, it is detected as not positive semidefinite:

>> IsPSD(X-eps*eye(2),0)

ans =

     0

Note that in general you can not expect this kind of accuracy.

Notes

Do not request the WIT output argument unless you need it. If WIT is not requested, positive semidefiniteness is determined by attempting a Cholesky decomposition of X, which is both faster and more accurate than computing its minimum eigenvalue/eigenvector pair.

Source code

Click here to view this function's source code on github.