octave-bug-tracker
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Octave-bug-tracker] [bug #55564] GESDD: vastly different singular value


From: anonymous
Subject: [Octave-bug-tracker] [bug #55564] GESDD: vastly different singular values when vectors are also requested
Date: Thu, 24 Jan 2019 17:03:55 -0500 (EST)
User-agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.12; rv:64.0) Gecko/20100101 Firefox/64.0

URL:
  <https://savannah.gnu.org/bugs/?55564>

                 Summary: GESDD: vastly different singular values when vectors
are also requested
                 Project: GNU Octave
            Submitted by: None
            Submitted on: Thu 24 Jan 2019 10:03:53 PM UTC
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Inaccurate Result
                  Status: None
             Assigned to: None
         Originator Name: Tim Mitchell
        Originator Email: address@hidden
             Open/Closed: Open
         Discussion Lock: Any
                 Release: 5.0.1
        Operating System: BSD

    _______________________________________________________

Details:

I recently opened an issue on LAPACK's Github page about how the GESDD routine
can produce vastly different singular values if the singular vectors are also
requested <https://github.com/Reference-LAPACK/lapack/issues/316>.  At the
moment, it is still unclear if this behavior is a coding bug or just an
inherent deficiency of the "divide and conquer" approach that GESDD
implements.  You will need to follow the LAPACK issue for developments on that
and for complete details.

As Octave 4.4 is using GESDD by default (like MATLAB and others), I just
wanted to raise your attention of how bad this problem can be in practice. 
For future Octave releases, you might consider only using GESVD for all svd
calls, unless the user specifically enables GESDD (at their own risk). ;-) 

In any case, GESDD's inaccuracy in singular values can basically be
arbitrarily inaccurate.  To be fair, note that this may only happen rarely and
indeed the example I found was designed to be numerically challenging
(companion_demo(n) from EigTool, with n>=26).  Nevertheless, even though this
matrix is nearly singular (GESVD returns 2.6e-10 as the smallest singular
value), GESDD instead returns 2.3e+9 as the smallest singular value!  For this
problem, only the largest singular value is computed consistently; all others
don't even agree to a single digit between GESVD and GESDD.  

Lastly, note that using norm(U*S*V'-A)/norm(A) to verify the computation for
this example is not a sufficient test.  The reason is that the largest
singular value is 6e+25 and all the others are at least 1e+16 times smaller. 
So, to machine precision, the matrix seems to be rank one.  In other words,
one can randomly choose any value in [0,1e9] for the other n-1 singular values
and still have norm(U*S*V'-A)/norm(A) look good numerically!  A better test is
to compare the singular values to those computed by GESVD and make sure each
singular value has a high number of digits in agreement.




    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?55564>

_______________________________________________
  Message sent via Savannah
  https://savannah.gnu.org/




reply via email to

[Prev in Thread] Current Thread [Next in Thread]