Dear all,
I have been using NR for a long time.
Recently, I wanted to write a program for decomposing a matrix
with SVD.
I copied the source code from NR and could compile it.
First time without svdbksb(...) and later added the same.

I also decomposed the matrix with SVD() function in MATLAB...

The decomposed matrices are not at all same,even with in reasonable limits of differences.....

Why is it so ??
AFAIK,
I tried to learn the fortran code from LAPACK of SVD which is used in Matlab.. I felt it uses QR decomposition....and NR_SVD, it doesnt use I think...please do correct me if I am wrong...

Because of these difference , I am speculative of which one is robust, which one is more preferred and why ???
I would like to have some reference to whether there has been any comparison and theory of making these two SVDs coincide...

I would be grateful to any type of suggestion or explanations in this regard. I would be glad if some body spares some time on this topic...

Thankyou for your input in advance.
Prasad.
Research Scholar.

Prasad,

The results of SVD are not completely unique.
See for example, the last FAQ on the page
http://webnz.com/robert/nmfaq.htm
(This doesn't relate to NR, but it is the same issue as seen by the author of another package.)

For convenience I'll reproduce the relevant Q and A here (hope the owner of the above-cited web page doesn't mind!):

Q. Your SVD routine gives a different answer from the SVD routine in Matlab.

A. The SVD decomposition is not completely unique. Columns in the U matrix can be swapped, if those in the V matrix and the elements in the diagonal matrix, D, are swapped in the same way. The signs of the elements in a column of U may be reversed if the signs in the corresponding column in V are reversed. If a number of the singular values are identical one can apply an orthogonal transformation to the corresponding columns of U and the corresponding columns of V. Note that older versions of my SVD do not sort the singular values.

Cheers,
Bill P.

Dear Bill Press,
thankyou for the input. Coming to quote you have given: I have gone through the site of newmat. Thankyou.
I would like further my doubts:

SVD is a Technique. If you take an application which uses SVD as a technique, with the present quote i.e non-uniqueness, it will give different
results and hence different physical consequences ??????

Doesnt this ambiguate the usage of SVD itself.
For example:
I am trying to use SVD for fitting a best plane. The smallest singular value and its corresponding RH(V) vector corresponds to the direction cosines of that data set (best fit plane).

In such a case, is it meaning ful to think
of different d.c.s for same data set ?????

It can be given an allowance of error but
not totally different dcs.

What I personally feel, there could be a way of assessing the quality of the Decomposed Matrices....?????

Could you please comment on this ???

Thankyou for any further input.
I am also trying to get hold of the best way of
assessing the quality of decomposition....

sincerely,
Prasad.

the diagonal Matrix should be the same always
but the left and right Projectors can differ in such way, that one is a lef and the other a right rotation i think.
i hope i am not to much wrong :O)
but the solution should be correct.

I too notice that sometimes the Numerical Recipes SVD routine delivers inaccurate results. I understand that the result is equivalent when it only differs by permutations and sign inversions, but I mean that sometimes the decomposition does not produce accurate results for small numbers.

Over the years I have seen this same posting many times on various newsgroups (search google groups with the search term: 'svd matlab "numerical recipes"'). I haven't seen many modifications of the NR routines along with these postings, so I figured I'm missing something. Are there any patches or corrections posted somewhere to SVD? Can anyone explain why this is happening?

Appreciate the help,
Geoff

example)

A matrix is as follows:
0.000000036401 0.000000191508 -0.001130863094
-0.000000111413 -0.000000010724 -0.002234603231
0.001027620086 0.002135421691 0.452740081559

Matlab produces:

U
0.002497710874 -0.464669394236 -0.885480725652
0.004935520881 -0.885466974436 0.464676099898
-0.999984700920 -0.005530935158 0.000081745007

D
0.452753210490 0.000000000000 0.000000000000
0.000000000000 0.000013144110 0.000000000000
0.000000000000 0.000000000000 0.000000000000

V
-0.002269679815 -0.426195617444 0.904628180097
-0.004716451582 -0.904615885978 -0.426201658750
-0.999986301725 0.005233976313 -0.000043057423

Numerical Recipes produces:
U
0.002497710874, 0.938995259456, 0.343921014420
0.004935520881, -0.343929473838, 0.938982511903
-0.999984700920, 0.000647877482, 0.005493467097

D
0.452753210491
0.000000000000
0.000013029467

V
-0.002269679815, -0.904628180097, 0.426195617444
-0.004716451582, 0.426201658750, 0.904615885978
-0.999986301725, 0.000043057423, -0.005233976313

Nevermind. I just saw the bug report section, and this cured the problem for me.

Sorry about that.

Dear gagnal,
can you please give the address where you have
seen the bug report listing and how you could over come the problem...

thankyou for the help in advance..

Sincerely,
Prasad.

Sure- it was on this nr.com/forum under 'Official Bug Reports'

I'm not sure if all the links work this way, but this is what I'm looking at:
http://www.nr.com/forum/forumdisplay.php?forumid=9

Good luck,
Geoff

Well, i have learned a lot from reading the posts here, but I do have NR Version 2.11 and I'm still in a quandry about the MATLAB versus NRC SVD solutions. I am trying to get a C program to EXACTLY match MATLAB output because otherwise the two programs' least squares process immediately diverge. Is there any method out there for getting the exact same results for the U and V matrices each time, or is some of this proprietary MATLAB software?

We are coming down to a deadline very soon and any help would be appreciated, even pointing to a non-NRC solution.

We are working on an Arcturus Cold Fire embedded uClinux system for a NASA experiment, so there is no MATLAB for this platform.

I am using dsvdcmp.c. Thanks!

If this is for an embedded system, then I would really recommend using an optimized version of the LAPACK libraries for your SVD.

Kevin Dolan

Hi, Kevin

I am assuming that you mean the CLAPACK, which is the F77 version converted to C, and then use a wrapper libary optimized for my platform.

I noticed that on my Arturus ColdFile platform running uClinux, we also use an altered version of the gcc compiler. However, the Arcturus ColdFire does not have a floating point processor so not only does the NRS SVD routine come to a different result than the MATLAB version (on a PC), but it is about 40x slower.

Another problem with the Arcturus is that it does not support dynamic memory allocation very well (i.e., malloc()). For the NRC SVD routine, this was easy modifiy as I set up fixed arrays and made my own pointers and pointers-to-pointers. I then simply tossed out 99% of the software source code for the various other functions I would not be using.

LAPACK looks pretty comprehensive though I will also have to do a "lobotomy" to keep only the parts I will need and replace malloc in all the code that will actually get used (Apparently not too much).

Do you know if its SVD algorithm is substantially faster than the NRC version?

Thanks for the tip!

Lapack should definitely be faster than NRC, but on an embedded system with no floating point processor, just about any generic solution will probably be terribly slow.

Kevin Dolan

Kevin

I came across a linear algebra package called Oracle, but turns out many of its routines are also built from LAPACK.

I then found and downloaded the whole CLAPACK package - what a monster! The SVD routine source file alone has 4,083 lines and then you still have to include a whole bunch of library functions.

Have you ever heard of any nice scaled-down SVD routine? Of course, the NRC program is short (a few hundred lines) but aaprently is not adequate.

I used the Oracle example of an SVD operation from their demo page, copied the inputs from the Oracle demo text into my MATAB window on my PC and got the same results for an output, so the underlying CLAPACK sure seems consistent with MATLAB.

Matlab also uses Lapack internally for its linear algebra operations. Most math packages do.

I doubt you will find what you are looking for. SVD is a complex operation to perform. I honestly doubt that you will find an algorithm for it that is suitable for an embedded system. It is a complicated enough task that it would probably need to be optimized for the particular hardware it is going to be running on. So even if you find an algorithm for SVD which was designed for that purpose, if it was not for the system you are using, it won't be very useful.

Kevin Dolan