You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Phil Steitz <ph...@gmail.com> on 2013/10/19 01:21:54 UTC
[math] documentation for what pseudo-inverse means in decomp solvers
The decomposition solvers can "invert" non-square matrices. There
is no documentation describing what exactly is being returned in
these cases. It is not obvious to me exactly what conditions the
returned value satisfies in each case when the actual parameter is
not square. Do all of them return pseudo-inverses X satisfying AXA
= A where A is the input matrix? Do they satisfy other conditions
as well? Under what conditions will exceptions be thrown? We
should either throw NonSquareMatrixException (as MatrixUtils now
does) on non-square arguments or define precisely what is being
computed by each of the solvers for non-square arguments and what
the preconditions are.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] documentation for what pseudo-inverse means in decomp
solvers
Posted by Phil Steitz <ph...@gmail.com>.
On 10/21/13 9:19 AM, Sean Owen wrote:
> On Sat, Oct 19, 2013 at 5:51 PM, Phil Steitz <ph...@gmail.com> wrote:
>> Investigation / tests / documentation much appreciated.
>>
>> Thanks for looking into this!
> OK Phil I'll have another go. I would like to propose three patches
> (three JIRAs?)
>
> 1. The javadoc updates discussed on this thread, which I really
> wouldn't mind someone else reviewing for correctness. Plus a few
> additional tests to cover the gaps between what's tested now and
> what's being asserted in the javadoc.
+1 many thanks and I will review
>
> 2. A small issue in EigenDecomposition.isNonSingular() that I found
> while making a test for it (so won't be part of patch #1). Basically
> it needs to use the "epsilon" threshold for testing for 0 eigenvalues
> to get this right reliably.
+1
>
> 3. If it turns out to be a real issue, a patch for
> QRDecompositionSolver to handle tall/skinny matrices correctly. Still
> need to look into this to be sure.
+1
Thanks!
Phil
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] documentation for what pseudo-inverse means in decomp solvers
Posted by Sean Owen <sr...@gmail.com>.
On Sat, Oct 19, 2013 at 5:51 PM, Phil Steitz <ph...@gmail.com> wrote:
> Investigation / tests / documentation much appreciated.
>
> Thanks for looking into this!
OK Phil I'll have another go. I would like to propose three patches
(three JIRAs?)
1. The javadoc updates discussed on this thread, which I really
wouldn't mind someone else reviewing for correctness. Plus a few
additional tests to cover the gaps between what's tested now and
what's being asserted in the javadoc.
2. A small issue in EigenDecomposition.isNonSingular() that I found
while making a test for it (so won't be part of patch #1). Basically
it needs to use the "epsilon" threshold for testing for 0 eigenvalues
to get this right reliably.
3. If it turns out to be a real issue, a patch for
QRDecompositionSolver to handle tall/skinny matrices correctly. Still
need to look into this to be sure.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] documentation for what pseudo-inverse means in decomp
solvers
Posted by Phil Steitz <ph...@gmail.com>.
On 10/19/13 5:14 AM, Sean Owen wrote:
> On Sat, Oct 19, 2013 at 12:21 AM, Phil Steitz <ph...@gmail.com> wrote:
>> The decomposition solvers can "invert" non-square matrices. There
>> is no documentation describing what exactly is being returned in
>> these cases. It is not obvious to me exactly what conditions the
>> returned value satisfies in each case when the actual parameter is
>> not square. Do all of them return pseudo-inverses X satisfying AXA
>> = A where A is the input matrix? Do they satisfy other conditions
>> as well? Under what conditions will exceptions be thrown? We
>> should either throw NonSquareMatrixException (as MatrixUtils now
>> does) on non-square arguments or define precisely what is being
>> computed by each of the solvers for non-square arguments and what
>> the preconditions are.
> Lots of the decompositions are not even defined for non-square
> matrices -- for example LU. I think this covers that pretty well:
> http://commons.apache.org/proper/commons-math/userguide/linear.html
> (end of 3.4)
>
> Looks like these decompositions do check and reject non-square
> matrices, and javadoc that. So set those aside. I think we're talking
> about QR and SVD here.
Right. Sorry, I had randomly chosen QR to look at when I did not
see clear doco in DecompositionSolver.
>
> For non-square matrices, the inverse can't exist, so the result is
> intended to be a pseudo-inverse. Yes it will always satisfy AXA = A.
> We can point people to the definition of pseudo-inverse but I think
> the salient fact is that in Ax = b, the "best" answer for x is
> pinv(A)*b in the sense that:
>
> - if there are no exact solutions, x gives the closest solution
> (minimizes L2 norm of Ax-b)
> - if there are many solutions, x is the smallest solution (smallest L2
> norm of x)
>
> You can make more specific and useful statements too, like, pinv(A)
> will be a left- or right-inverse of A if it's not singular. And of
> course if A is square and non-singular you get the real inverse out of
> this, which also satisfies the generalized conditions above.
>
>
> 1. The javadoc does say it's a pseudo-inverse which is correct but
> maybe it bears explaining that slightly?
Yes. Patches most welcome on this. As long as we get good javadoc
in the Decomp classes themselves, that is OK, IMO.
>
> 2. The DecompositionSolver javadoc says that SingularMatrixException
> is thrown if A is singular, but, at the least the SVD impl does not.
> And indeed it does the meaningful thing in this case. This comment can
> be moved down to, say, the QR decomposition, which does reject a
> singular matrix (and it's beyond me whether it can be modified to not
> do so)
Right. The DecompositionSolver javadoc should refer users to the
specific impl for preconditions / exceptions.
>
> 3. While playing with it I was not able to get the QR decomposition to
> (pseudo-)invert a tall/skinny (non-singular) matrix. I think it is a
> small bug in that it solves for an identity matrix of the wrong size
> here, but again, some chance I'm missing something.)
Investigation / tests / documentation much appreciated.
Thanks for looking into this!
Phil
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
> For additional commands, e-mail: dev-help@commons.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] documentation for what pseudo-inverse means in decomp solvers
Posted by Sean Owen <sr...@gmail.com>.
On Sat, Oct 19, 2013 at 12:21 AM, Phil Steitz <ph...@gmail.com> wrote:
> The decomposition solvers can "invert" non-square matrices. There
> is no documentation describing what exactly is being returned in
> these cases. It is not obvious to me exactly what conditions the
> returned value satisfies in each case when the actual parameter is
> not square. Do all of them return pseudo-inverses X satisfying AXA
> = A where A is the input matrix? Do they satisfy other conditions
> as well? Under what conditions will exceptions be thrown? We
> should either throw NonSquareMatrixException (as MatrixUtils now
> does) on non-square arguments or define precisely what is being
> computed by each of the solvers for non-square arguments and what
> the preconditions are.
Lots of the decompositions are not even defined for non-square
matrices -- for example LU. I think this covers that pretty well:
http://commons.apache.org/proper/commons-math/userguide/linear.html
(end of 3.4)
Looks like these decompositions do check and reject non-square
matrices, and javadoc that. So set those aside. I think we're talking
about QR and SVD here.
For non-square matrices, the inverse can't exist, so the result is
intended to be a pseudo-inverse. Yes it will always satisfy AXA = A.
We can point people to the definition of pseudo-inverse but I think
the salient fact is that in Ax = b, the "best" answer for x is
pinv(A)*b in the sense that:
- if there are no exact solutions, x gives the closest solution
(minimizes L2 norm of Ax-b)
- if there are many solutions, x is the smallest solution (smallest L2
norm of x)
You can make more specific and useful statements too, like, pinv(A)
will be a left- or right-inverse of A if it's not singular. And of
course if A is square and non-singular you get the real inverse out of
this, which also satisfies the generalized conditions above.
1. The javadoc does say it's a pseudo-inverse which is correct but
maybe it bears explaining that slightly?
2. The DecompositionSolver javadoc says that SingularMatrixException
is thrown if A is singular, but, at the least the SVD impl does not.
And indeed it does the meaningful thing in this case. This comment can
be moved down to, say, the QR decomposition, which does reject a
singular matrix (and it's beyond me whether it can be modified to not
do so)
3. While playing with it I was not able to get the QR decomposition to
(pseudo-)invert a tall/skinny (non-singular) matrix. I think it is a
small bug in that it solves for an identity matrix of the wrong size
here, but again, some chance I'm missing something.)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: [math] documentation for what pseudo-inverse means in decomp
solvers
Posted by Thomas Neidhart <th...@gmail.com>.
On 10/19/2013 01:21 AM, Phil Steitz wrote:
> The decomposition solvers can "invert" non-square matrices. There
> is no documentation describing what exactly is being returned in
> these cases. It is not obvious to me exactly what conditions the
> returned value satisfies in each case when the actual parameter is
> not square. Do all of them return pseudo-inverses X satisfying AXA
> = A where A is the input matrix? Do they satisfy other conditions
> as well? Under what conditions will exceptions be thrown? We
> should either throw NonSquareMatrixException (as MatrixUtils now
> does) on non-square arguments or define precisely what is being
> computed by each of the solvers for non-square arguments and what
> the preconditions are.
LU and Cholesky decomposition already check if the matrix is square and
throw a NonSquareMatrixException in this case.
QR decomposition seems to compute the right-inverse of the matrix if the
number of rows is equal to its rank.
Thomas
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org