Re: [eigen] RFC: BasicSVD class |

[ Thread Index | Date Index | More lists.tuxfamily.org/eigen Archives ]

*To*: eigen <eigen@xxxxxxxxxxxxxxxxxxx>*Subject*: Re: [eigen] RFC: BasicSVD class*From*: Gael Guennebaud <gael.guennebaud@xxxxxxxxx>*Date*: Fri, 7 Dec 2012 15:35:58 +0100*Dkim-signature*: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=eBsAA+IWqepsPgU0ibZJPqq1V+fgp2Am67U0tV+mPyY=; b=t5+dZOE4D1eXLJh9eYb8u7sle6dTY1mcDlX7SlDuPLF309zZ84XwETTETS6lnVvNzk NEr/JaQjne6gVrJ/4arkYKhjqqgFP6LP39leEDkYXHrPtYAKmXf5KNpa0x3qQCggi4eC p1wzgQPM4xPV2KFbaiD3WqvRjiliDzQjkeyUgwMxSBntCsmVghdXEI4WHLSWFe7DTqsi /SpqozIkQJx3ibQsUhXQDdjDO5MLLC9oKQnO7WcxSpAuDBpv5SH4rU8rL/rLKLV6Qk7c QW6X78PjV+hAz2VpSUu3YafY/YQJUz/eQiCwF0la1+hENxMy0e3nokzqH4GSh2QEzHsW eZeA==

Indeed, this simple algorithm seems pretty fast and it could even be even faster once we have fully optimized SelfAdjointEigenSolver. However I'm skeptical about its accuracy since it is squaring the entries that is typically something you want to avoid when using a SVD solver. I guess that in your case you are more interested in the singular values/vectors rather than in solving a least square problem? otherwise QR would offer a better accuracy/perf option.

gael

On Fri, Dec 7, 2012 at 2:31 PM, Mark Borgerding <mark@xxxxxxxxxxxxxx> wrote:

I compared the speed of BasicSVD to two versions of LAPACK running the [scdz]gesdd functions: the netlib version that comes with ubuntu and the MKL (Composer version).

They are pretty comparable. BasicSVD in "fast mode" beats either version for k<5. The mode based on SelfAdjointEigenSolver is slower than the MKL LAPACK.

-- Mark

On 12/05/2012 11:05 AM, Mark Borgerding wrote:

Attached is a draft of a faster SVD class.

Summary:

The BasicSVD is much faster and sufficiently accurate for many (most?) purposes.

excerpt from header:

* Singular Value Decomposition by eigenanalysis of the Gramian

*

* option 1: (default) Solves A=U*S*V' by finding the eigenvectors,values of A'A (or AA' if matrix is wide)

* This is done using the SelfAdjointEigenSolver

* option 2: "fastMode" uses power iteration to quickly strip off the dominant eigenvectors one at a time.

* This may be useful when only a few of the singular dimensions are desired (e.g. k<5)

*

* Currently limited to "Thin" or "Economy Sized" singular vectors. When decomposing a rectangular matrix,

* either the U or V matrix will be an incomplete basis (tall). Any completion of this basis is valid and

* is left as an exercise to the reader.

*

* The "fast" mode uses power iteration (plus feedback)

* This can be several times faster than the default mode, but

* with caveats:

* *) convergence is slow and accuracy suffers in the case of nearly identical strongest singular values

* *) speed is linear with K, so if K> 5ish, fastMode may actually be slower.

Output from testBasicSVD.cc (attached)

compiled with: g++ -Wall -O -g -msse4.2 -I /path/to/inc/ testBasicSVD.cc

explanation of fields:

values: K strongest singular values (in this case K=2) ( all lesser dimensions have singular values around 1)

vectorwise errors: singular vector errors left|right for each of the K strongest dimensions

subspace error: residual error of the true rank-K subspace projected onto the found subspace

begin output :

############## Type: float Problem Size: 300x200

================ JacobiSVD ================

elapsed time 0.358115s

values = 3.00011 2.00006

vectorwise errors (dB):-87.5|-92.3 -87.8|-92.2

subspace error -114 dB

================ BasicSVD ================

elapsed time 0.0242s

values = 3 2

vectorwise errors (dB):-133|-125 -112|-106

subspace error -109 dB

================ BasicSVD (fast mode) ================

elapsed time 0.0046s

values = 3 2

vectorwise errors (dB):-89.8|-86.3 -78.5|-81.8

subspace error -97.3 dB

############## Type: complex<double> Problem Size: 300x200

================ JacobiSVD ================

elapsed time 5.91s

values = 3 2

vectorwise errors (dB):-259|-265 -266|-268

subspace error -284 dB

================ BasicSVD ================

elapsed time 0.216s

values = 3 2

vectorwise errors (dB):-241|-237 -231|-231

subspace error -235 dB

================ BasicSVD (fast mode) ================

elapsed time 0.0411s

values = 3 2

vectorwise errors (dB):-305|-306 -178|-175

subspace error -178 dB

-- Mark Borgerding

**Follow-Ups**:**Re: [eigen] RFC: BasicSVD class***From:*Mark Borgerding

**Re: [eigen] RFC: BasicSVD class***From:*Jitse Niesen

**References**:**[eigen] RFC: BasicSVD class***From:*Mark Borgerding

**Re: [eigen] RFC: BasicSVD class***From:*Mark Borgerding

**Messages sorted by:**[ date | thread ]- Prev by Date:
**Re: [eigen] RFC: BasicSVD class** - Next by Date:
**[eigen] New Levenberg Marquardt stuff** - Previous by thread:
**Re: [eigen] RFC: BasicSVD class** - Next by thread:
**Re: [eigen] RFC: BasicSVD class**

Mail converted by MHonArc 2.6.19+ | http://listengine.tuxfamily.org/ |