Simple SVD

SVD computation using QR decomposition

Description

A very short and simple program that computes the singular value decomposition of a matrix using the QR decomposition.

• MATLAB release: MATLAB 6.5 (R13)

[Scott Miller]

What are the advantages and disadvantages of using this routine over the function svd included in MATLAB?

Scott

[John D'Errico]

This would appear to have NO advantages over svd. It will be immensely slower than svd. One exception - in theory, svdsim will work on sparse matrices. However, svdsim is so slow that even here you are far better off converting your matrix to a full one, then calling svd. For example:

>> X = sprand(50,50,.01);
>> tic,[u,s,v]= svdsim(X);toc
Elapsed time is 4.720246 seconds.
>> tic,[u,s,v]= svd(full(X));toc
Elapsed time is 0.002718 seconds.

Note, this gets far worse if X is less sparse.

>> X = sprand(50,50,.1);
>> tic,[u,s,v]= svdsim(X);toc
Elapsed time is 41.527362 seconds.
>> tic,[u,s,v]= svd(full(X));toc
Elapsed time is 0.012801 seconds.

Another problem with this code is the lack of a convergence tolerance. It merely loops an arbitrary number of times, then quits.

So don't use this code to compute the svd. Just use svd.

This leaves only one purpose - an expository one. It does that reasonably well, but even there the lack of any convergence criterion suggests a low rating. Good expository code might also suggest why there is no sort at the end on the singular values, and provide a reference for the student to read further on methods to compute the SVD.

I'll raise my rating with improvements in the exposition and code.

[Carlos López]

Aside for dealing with sparse matrix, there might be another application for this code: improving an already available approximation of the real solution. Apparently svd does not take advantage of any first guess.
I suggest something like
[U,V,S]=svdsim(A,U0,V0,S0);
To test this, you can use something like
[U0,V0,S0]=svd(single(A));
to have an initial value, and later invoke the svdsim routine. A comparison might be made with the standard svd.
I foresee an application for higher-than-double precision calculations within matlab. In such case, the output of the standard svd can be improved to the required precision with a routine similar to svdsim.
Regards
Carlos

[John D'Errico]

While future higher precision computations might allow refinement using the scheme in this code, if higher precision is available in the future, then the svd code itself would far more efficiently call a higher precision version of svd at relatively little cost in time. An expensive refinement scheme would seem to be of little value.

[Carlos López]

I consider seriously your comments, John. Thus, I will pose a different but related question to the readers: Is there a better algorithm to improve an estimate of the SVD than the one provided by this submission?
Regards
Carlos

[Paul Godfrey]

A few comments by the author...

To Scott Miller: Matlab's own SVD should always be, for many reasons, the program of first choice most SVD needs.
The purpose of this program was to demonstrate a very simple way to compute the SVD that was probably not well known.
To John D'Errico: Your first set of comments appear to be based on the assumption that this code is intended to compute with Matlab's own SVD code for all user applications. It is not.
Upon typing 'Help svdsim; the used clearly sees "A simple program that demonstrates..."
As such, I did not, originally, bother with a robust exit scheme since the program intent was algorithmic in nature and not efficiency oriented. However, I have updated the program to add a more sophiticated exit mechanism.
For your second comment and for the comments of Carlos López: The program could certainly be used to refine an existing SVD solution.
The required code would be trivial to add.
Also, QR decomposition routines (MGS) are easy to write by almost any programmer. However, an SVD routine is a more daunting task and is usually sent to a canned library routine.
This program provides an easy to implement algorithm that can be used whenever a more sophisticated math library is not available.

[Sondur Lakshmipathi]

My sincere thanks to the author. Very useful method. I compared the result with matlab inbuilt function on SVD, both match well. I had done in my application QR decomposition, I thought of reusing it for SVD computation, this helped me a lot. Good work.

[Lei]

Could anybody tell me how to evaluate the time required by the SVD. Please kindly note the svd.m called directly by the workspace is a built-in function, which is much faster than the svd.m available on the Matlab website. So which one is more suitable to evaluate the required time?

Actually, I am trying to compare a new algorithm with the SVD in computational cost or time. I suppose the built-in SVD function might be faster than the source-code SVD function. Could anybody help me? Thanks a lot for your kindly helps in advance! My email address is [e-mail].

[hendra togi]

i have a project (Robust DWT-SVD Domain Image Watermarking:
Embedding Data in All Frequencies).
i use DWT, decompose the cover image A into 4 subbands:
LL, HL, LH, and HH.
can you tell me how to apply svd to each subband image…
the program uses matlab. thx

[fgdaadasd]

Very nice SVD-Algorithm. Thank you!
But where can I find literature about this Method?