bugGNU Octave - Bugs: bug #51270, isdefinite should return 0 for...

 
 

bug #51270: isdefinite should return 0 for zero matrices

Submitter:  Travis Arnold <teerav42>
Submitted:  Mon 19 Jun 2017 07:05:32 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  None
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * 4.0.3 Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Fri 14 Dec 2018 01:05:27 AM UTC, comment #7: 

This is a very old report, but I pushed a changeset that works along the lines proposed.  isdefinite() now only returns true or false, and the documentation outlines how to use the tolerance field to check for semi-definite matrices.

Rik <rik5>
Group administrator
Thu 22 Jun 2017 07:29:33 AM UTC, comment #6: 

There is no way to determine positive-definiteness cheaper than Choleski, as far as I know. Then, for any default tolerance tol


[1, 0; 0, -tol / 2]


will be detected as positive semi-definite. I am in favour of isdefinite returning either true (positive definite) or false. In the documentation it would possible to write that if isdefinite(A) is false but isdefinite(A+tol) is true for tol sufficiently small, than A is quite surely semi-definite. And, if one wants to be sure (up to machine precision), the eigenvalues have to be computed.

Marco Caliari <caliari>
Group Member
Tue 20 Jun 2017 05:02:42 PM UTC, comment #5: 

Why not just clamp the tolerance at eps, or at the default, or at some other small value? If the user passes in a tol of zero, just force it to be a small value and let it work the way it does now.

Either that or explicitly document that if the user passes in a tol of zero, the function can only determine whether a matrix is positive definite or not, it is unable to determine semi-definiteness.

Mike Miller <mtmiller>
Group Member
Tue 20 Jun 2017 04:54:15 PM UTC, comment #4: 

One solution would be to make this function more like other isXXX functions and return a boolean rather than -1, 0, +1.  In that case, isdefinite would only mean "positive definite" or "not positive definite".

Otherwise, we need someone with more linear algebra expertise than I have to provide an algorithm that can cheaply determine whether a matrix is positive definite.

Rik <rik5>
Group administrator
Tue 20 Jun 2017 04:49:44 PM UTC, comment #3: 

Marco is correct. A zero matrix is positive semidefinite, so


isdefinite(zeros(n))


should return 0 for any integer n. My patch fixes this.

Marco is also correct that


[1, 0; 0, 0]


is positive semidefinite, and so perhaps it would be desirable for


isdefinite ([1, 0; 0, 0], 0)


to return 0.

The way the code works is by attempting a series of Cholesky decompositions (https://en.wikipedia.org/wiki/Cholesky_decomposition). Note that theoretically, a Cholesky decomposition exists for any positive semidefinite matrix, but it is only unique for strictly positive definite matrices. In practice however,


[r, p] = chol(A)


calculates the Cholesky decomposition successfully only if A is strictly positive definite. If this returns a nonzero p, this indicates that the decomposition was unsuccessful and so A is not strictly positive definite.

We want the code to tell us whether a matrix A is

  • strictly positive definite
  • positive semidefinite
  • neither


What it actually checks for is this:

  • Are all of the eigenvalues of A at least tol bigger than 0? If so then tell the user that A is strictly positive definite.
  • If not, then are all of the eigenvalues of A + tol bigger than 0? If so then tell the user that the A is positive semidefinite.
  • If not, then tell the user that A is neither strictly positive definite nor positive semidefinite.


The problem comes from specifying a tolerance of 0. Regarding


isdefinite ([1, 0; 0, 0], 0)


the eigenvalues are not at least tol bigger than 0, so the code does not return strictly positive definite. Also, the eigenvalues + tol are not bigger than zero, so the code does not return positive semidefinite. So the code returns the third option: neither.

Calling the function with a tolerance of 0 is probably bad practice in general, so I'm not sure you want to account for that use case. Clarifying the documentation or throwing a warning if the user tries to use a tolerance of 0 might be a good idea.

Travis Arnold <teerav42>
Tue 20 Jun 2017 07:23:43 AM UTC, comment #2: 

According to the documentation, isdefinite should return 0 for semi-definite matrices (any zeros (n), for instance). Travis' patch addresses this issue. On the other hand, I think


isdefinite ([1, 0; 0, 0], 0)


should also return 0. I don't know how to get it without computing the eigenvalues.

Marco Caliari <caliari>
Group Member
Tue 20 Jun 2017 04:33:28 AM UTC, comment #1: 

It's not clear to me that the answer should be zero.  One resource for definitional issues is the Wikipedia entry on Positive Definite matrices (https://en.wikipedia.org/wiki/Positive_definite_matrix).  According to the text, the eigenvalues of a positive definite matrix are all positive.  However, the eigenvalues of a matrix of zeros are all 0.  The number 0 is not positive and therefore the matrix is not positive definite so Octave returns -1.  The definition for positive semi-definite matrices would include 0.

Rik <rik5>
Group administrator
Mon 19 Jun 2017 07:05:32 PM UTC, original submission:  

isdefinite currently returns -1 for any zero matrix that is passed to it. Clearly it should return 0. I attach a patch that fixes this behavior.

Travis Arnold <teerav42>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #40939:  isdefinite.patch added by teerav42 (2KiB - text/x-patch)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by caliari (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by teerav42 (Submitted the item)
  • -email is unavailable- added by teerav42
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-12-14 mtmiller Carbon-CopyRemoved 80942 -
    2018-12-14 rik5 StatusNeed Info Fixed
        Open/ClosedOpen Closed
    2017-06-20 rik5 StatusNone Need Info
    2017-06-19 teerav42 Attached File- Added isdefinite.patch, #40939
        Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code