[jira] [Created] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Created] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
------------------------------------------------------------------------------------

                 Key: MATH-601
                 URL: https://issues.apache.org/jira/browse/MATH-601
             Project: Commons Math
          Issue Type: Bug
    Affects Versions: 2.2, 3.0
         Environment: All
            Reporter: greg sterijevski


In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:

In lines 2600-264 we have:

                if (singularValues[i] > 0) {
                 a = 1 / singularValues[i];
                } else {
                 a = 0;
                }

This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...

Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Christopher Nix updated MATH-601:
---------------------------------

    Attachment: SingularValueDecompositionImpl.patch

getRank() employs a local tolerance value to determine if a singular value should be counted.  

I have attached a patch that moves this tolerance value to a static variable in the main class to be accessed by the Solver in working out the pseudo-inverse.  This tolerance value will also guard against overflow.

> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2, 3.0
>         Environment: All
>            Reporter: greg sterijevski
>              Labels: Pseudoinverse
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069628#comment-13069628 ]

greg sterijevski commented on MATH-601:
---------------------------------------

Patch looks good to me...

> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2, 3.0
>         Environment: All
>            Reporter: greg sterijevski
>              Labels: Pseudoinverse
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069937#comment-13069937 ]

Axel Kramer commented on MATH-601:
----------------------------------

For reference values try wolfram alpha:
N[SingularValueDecomposition[{{1,2},{1,2}}]]

It's still different.
See: MATH-320

> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2, 3.0
>         Environment: All
>            Reporter: greg sterijevski
>              Labels: Pseudoinverse
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069982#comment-13069982 ]

greg sterijevski commented on MATH-601:
---------------------------------------

Axel,

You are correct, while the getRank()  emthods criterion was changed to:
double tol = FastMath.max(m, n) * singularValues[0] * EPS;
there is nothing happening at line 591. The moore-penrose will still be not
consistent to the ranks calculation.

Line 591 and onwards:

                if (singularValues[i] > 0) {
                    a = 1 / singularValues[i];
                } else {
                    a = 0;
                }

So the change of the zero criterion is good, there is one more spot to fix.

I would also put a lower bound on tol:

tol = FastMath.max(m, n) * singularValues[0] * EPS;

if( FastMath.abs(tol) < FastMath.sqrt( MathUtils.SAFE_MIN) ){

}


-Greg




> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2, 3.0
>         Environment: All
>            Reporter: greg sterijevski
>              Labels: Pseudoinverse
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13069983#comment-13069983 ]

greg sterijevski commented on MATH-601:
---------------------------------------

Sorry,

Sent the previous inadvertently,

f( FastMath.abs(tol) < FastMath.sqrt( MathUtils.SAFE_MIN) ){
 tol = FastMath.sqrt( MathUtils.SAFE_MIN);
}

That should guard against the case of a small matrix with small eigenvalues.

-Greg

On Sat, Jul 23, 2011 at 10:31 AM, Greg Sterijevski



> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2, 3.0
>         Environment: All
>            Reporter: greg sterijevski
>              Labels: Pseudoinverse
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Phil Steitz updated MATH-601:
-----------------------------

    Affects Version/s:     (was: 3.0)
        Fix Version/s: 3.0

> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2
>         Environment: All
>            Reporter: greg sterijevski
>            Assignee: Phil Steitz
>              Labels: Pseudoinverse
>             Fix For: 3.0
>
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13084556#comment-13084556 ]

Phil Steitz commented on MATH-601:
----------------------------------

I just committed (r1157336) a modified version of Chris' patch.  Please review, test and confirm that it fixes the issue.

Changes to the patch:
0) Incorporated Greg's suggestion to put a floor on tol
1) Made tol final, but not static and explicitly passed it to the Solver constructor.  The value depends on instance data so should not be static.

> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2
>         Environment: All
>            Reporter: greg sterijevski
>            Assignee: Phil Steitz
>              Labels: Pseudoinverse
>             Fix For: 3.0
>
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

    [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13084559#comment-13084559 ]

Gilles commented on MATH-601:
-----------------------------

Also changed "max(m, n)" to "m" in accordance with Greg's remark on the "dev" ML for other such occurrences (revision 1157342).


> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2
>         Environment: All
>            Reporter: greg sterijevski
>            Assignee: Phil Steitz
>              Labels: Pseudoinverse
>             Fix For: 3.0
>
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Resolved] (MATH-601) SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation

Gilles (Jira)
In reply to this post by Gilles (Jira)

     [ https://issues.apache.org/jira/browse/MATH-601?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Phil Steitz resolved MATH-601.
------------------------------

    Resolution: Fixed

> SingularValueDecompositionImpl psuedoinverse is not consistent with Rank calculation
> ------------------------------------------------------------------------------------
>
>                 Key: MATH-601
>                 URL: https://issues.apache.org/jira/browse/MATH-601
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 2.2
>         Environment: All
>            Reporter: greg sterijevski
>            Assignee: Phil Steitz
>              Labels: Pseudoinverse
>             Fix For: 3.0
>
>         Attachments: SingularValueDecompositionImpl.patch
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> In the SingularValueDecompositionImpl's internal private class Solver, a pseudo inverse matrix is calculated:
> In lines 2600-264 we have:
>                 if (singularValues[i] > 0) {
>                  a = 1 / singularValues[i];
>                 } else {
>                  a = 0;
>                 }
> This is not consistent with the manner in which rank is determined (lines 225 to 233). That is to say a matrix could potentially be rank deficient, yet the psuedoinverse would still include the redundant columns...
> Also, there is the problem of very small singular values which could result in overflow.  

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira