|Re: [eigen] accuracy of SVD|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen <eigen@xxxxxxxxxxxxxxxxxxx>
- Subject: Re: [eigen] accuracy of SVD
- From: Benoit Jacob <jacob.benoit.1@xxxxxxxxx>
- Date: Wed, 27 Sep 2017 17:32:26 -0400
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=fcbM1WvM2j6YNyv6r5kfr+AYbN7aB+sfAdEGizvo8h0=; b=Pw5PsSFDY3mkdztVN67mS/do+zyD+d0vp9bhJQgO0flCCObzs8ysKbKVVsU54QQ1Yv Ot+7Z+j6Sa9a3B/kZ9aBe/cbnsKK5XnpGeNC95QQ807H4HNWRNhpuNRroUvaGRtSJ+PH upwsXHtmScZ168bxWi55Vz3H9NseypHJppz32DnZ1TDwaFNs+nsHXXEGf6+z3g8App7f +e8zIGb48Qo2keVZSjZUVaxay990rGEBFdHcAjE4B/URwCOZ09cG9JNDtYPvvUCff3wB 1Jsi1kDKKwQOUNPd7ICC++r/LPI1dRWnaUSUzcHr2B/NzU5egef1478aEgjD1KXig2H8 aLIA==
Disclaimer: I wrote this JacobiSVD code and "proven accuracy" claim a very long time ago and have been inactive in the Eigen project for a long time since. I would not be aware if my understanding of this code is out of date.
Thanks for the very informative study.
By "proven accuracy" all I meant was that the high-level algorithm (QR preconditioning with complete pivoting, followed by 2-sided Jacobi SVD iteration) does not involve any compromise on accuracy. I did not actually prove my own implementation in any way. I was mostly looking for a way to distinguish that kind of provenness in this table  from the otherwise very good, but still compromising, accuracy of some other decompositions. For example, while 1-sided Jacobi or QR without complete pivoting are very accurate on most matrices, one can always craft a 'bad' matrix on which they will be inaccurate; as far as I understand, that is in principle not possible with complete-pivoting-QR and 2-sided Jacobi.
I can't speak for current maintainers but I would suggest that a patch, fixing this documentation to remove any inaccurate claim, would be welcome. Eigen, including its documentation, is an open source project, it only improves with contributions like it looks like you'd be able to make here!
A code contribution fixing the inaccuracy which you observed, would naturally be very welcome too. I'm surprised that Eigen's JacobiSVD is so inaccurate compated to the other implementations you compared it to. Short of a fix, I suspect that at least a stand-alone compilable testcase, demonstrating the accuracy issue, would be very useful for anyone wanting to look into this.
Regarding the poor speed of this code, this is a known issue, and as of Eigen 3.3, which also offers a much faster bidiagonalizing SVD, I believe that JacobiSVD is only considered useful as a reference, accurate-but-slow decomposition. Thus, poor speed is not a major concern; on the other hand, your finding of disappointing accuracy sounds like a nail in its coffin.