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

 
 

bug #51270: isdefinite should return 0 for zero matrices

Submitted by:  Travis Arnold <teerav42>
Submitted on:  Mon 19 Jun 2017 07:05:32 PM UTC  
 
Category: Octave FunctionSeverity: 3 - Normal
Priority: 5 - NormalItem Group: None
Status: Need InfoAssigned to: None
Originator Name: Open/Closed: Open
Release: 4.0.3Operating System: GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission Jump to the original submission)

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

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>
Project 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>
Project Administrator
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>
Project Administrator
Tue 20 Jun 2017 04:49:44 PM UTC, comment #3:

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

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

Marco is also correct that

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

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,

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

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

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

Marco Caliari <caliari>
Project 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>
Project 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 File(s):
   
   
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
  • -unavailable- added by mtmiller (Posted a comment)
  • -unavailable- added by caliari (Posted a comment)
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by teerav42 (Submitted the item)
  • -unavailable- added by teerav42
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 3 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Tue 20 Jun 2017 04:33:28 AM UTCrik5StatusNone=>Need Info
    Mon 19 Jun 2017 07:05:32 PM UTCteerav42Attached File-=>Added isdefinite.patch, #40939
      Carbon-Copy-=>Added -unavailable-

    Back to the top


    Powered by Savane 3.1-cleanup1