Difference between revisions of "IsPSD"
Jump to navigation
Jump to search
(Created page with "{{Function |name=IsPSD |desc=Determines whether or not a matrix is positive semidefinite |req=opt_args |upd=November 20, 2012 |v=1.00}} <tt>'''IsPSD'''</tt> is a [[Lis...") |
(removed red links) |
||
| (10 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{Function | {{Function | ||
|name=IsPSD | |name=IsPSD | ||
| − | |desc=Determines whether or not a matrix is [[ | + | |desc=Determines whether or not a matrix is positive semidefinite |
| − | | | + | |rel=[[IsCP]]<br />[[IsPPT]]<br />[[IsTotallyPositive]] |
| − | |upd= | + | |cat=[[List of functions#Basic_operations|Basic operation]] |
| − | + | |upd=September 21, 2014}} | |
| − | <tt>'''IsPSD'''</tt> is a [[List of functions|function]] that determines whether or not a given matrix is | + | <tt>'''IsPSD'''</tt> is a [[List of functions|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== | ==Syntax== | ||
| Line 15: | Line 15: | ||
===Input arguments=== | ===Input arguments=== | ||
* <tt>X</tt>: A square matrix. | * <tt>X</tt>: A square matrix. | ||
| − | * <tt>TOL</tt> (optional, default <tt> | + | * <tt>TOL</tt> (optional, default <tt>eps^(3/4)</tt>): 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 <tt>-TOL</tt>. |
===Output arguments=== | ===Output arguments=== | ||
| Line 24: | Line 24: | ||
===Simple example with low tolerance=== | ===Simple example with low tolerance=== | ||
When <tt>X</tt> is very simple, positive semidefiniteness can be be determined exactly. The following example has the <tt>TOL = 0</tt> (not recommended in general!) to highlight the fact that the script really is checking for positive ''semi''definiteness, not positive definiteness. | When <tt>X</tt> is very simple, positive semidefiniteness can be be determined exactly. The following example has the <tt>TOL = 0</tt> (not recommended in general!) to highlight the fact that the script really is checking for positive ''semi''definiteness, not positive definiteness. | ||
| − | < | + | <syntaxhighlight> |
>> X = diag([1 0]) | >> X = diag([1 0]) | ||
| Line 37: | Line 37: | ||
1 | 1 | ||
| − | </ | + | </syntaxhighlight> |
Furthermore, if we make one of the eigenvalues even slightly negative in this case, it is detected as not positive semidefinite: | Furthermore, if we make one of the eigenvalues even slightly negative in this case, it is detected as not positive semidefinite: | ||
| − | < | + | <syntaxhighlight> |
>> IsPSD(X-eps*eye(2),0) | >> IsPSD(X-eps*eye(2),0) | ||
| Line 46: | Line 46: | ||
0 | 0 | ||
| − | </ | + | </syntaxhighlight> |
Note that in general you can not expect this kind of accuracy. | Note that in general you can not expect this kind of accuracy. | ||
| Line 52: | Line 52: | ||
==Notes== | ==Notes== | ||
Do not request the <tt>WIT</tt> output argument unless you need it. If <tt>WIT</tt> is not requested, positive semidefiniteness is determined by attempting a [http://en.wikipedia.org/wiki/Cholesky_decomposition Cholesky decomposition] of <tt>X</tt>, which is both faster and more accurate than computing its minimum eigenvalue/eigenvector pair. | Do not request the <tt>WIT</tt> output argument unless you need it. If <tt>WIT</tt> is not requested, positive semidefiniteness is determined by attempting a [http://en.wikipedia.org/wiki/Cholesky_decomposition Cholesky decomposition] of <tt>X</tt>, which is both faster and more accurate than computing its minimum eigenvalue/eigenvector pair. | ||
| + | |||
| + | {{SourceCode|name=IsPSD}} | ||
Revision as of 18:25, 16 December 2014
| IsPSD | |
| Determines whether or not a matrix is positive semidefinite | |
| Other toolboxes required | none |
|---|---|
| Related functions | IsCP IsPPT IsTotallyPositive |
| Function category | Basic operation |
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 =
1Furthermore, 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 =
0Note 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.