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