Hi all,

I've came across a following problem.

I have a set of N vectors in N-dimensional space. Some of them are lineary-dependant, some can even be zero. I need to make this set orthonormal - i.e., get rid of all dependent vecotrs and orthogonalize the rest. I thought SVD will do the job but it fails - I receive far more "independent" vectors than I expect in the set. Is there any other method which can do the job?

Thanks in advance.

svdcmp returns a matrix a whose n columns are the basis vectors. For a m x n matrix a you will receive n vectors with m components. You should however check the values in w for zero values (i.e. <1.0e-7 for single precision) and discard the corresponding vectors from the orthonormal basis. This should give you a set of independent basis vectors.

juha,

Thank you for your reply

Yes I've implemented schem outlined here - I've even fixed bugs in svdcmp mentioned here on the forums. Unfortunately, this doesn't work. In my case, N is 924 and number of fabs(w[i])>1e-8 is 912. The rank of the matrix composed of my N vectors is 128 so I expect SVD to return only 128 non-zero w[i]. Any ideas then?

Based on my experience svdcmp works fine. Is it possible to get a copy of this matrix in an text file like this?

a11 a12 a13 ...
a21 a22 a23 ...
... ... ... ...

It's pretty ok to send the matrix - nothing secret there.
But I've just played with w[i] and learned that I obtain desired 128 vectors if I discard all w[i] less then 10^-5 (small w[i] are 2..3*10^-6). Is it ok or the error is too big?

I am not sure about the threshold. But I tend to think that the choosen 10^-5 would be fine. On the other hand you could always compare your result with the result of the orth command in octave (GPL). Octave also has a svd command.

Thank you for your reply again.

I've found the root of the problem. I'm using data from mt CAS system (Mathematica) in order to construct matrix I later feed to dsvdcmp(). during export, Mathematica rounds all numeric values to sixth digit which leads to severe roundoff errors. I've switched to binary interchange format and now w[i] are nearly zero and I get the correct number of vectors in the output.

Hope this would help someone who come across the similar problem.

Hi,

As I udestand, a problem was solved.

But just a few tips:

1) Mathematica itself can do calculation with an infinity digits after a decimal point (or at least more than 6 digits on 32 bits , up to 15-16 digits). You can found this fact if
replace a cell output on screen on Cell -> ConvertTo->InputForm cell or
do saving all input numbers as simple ASCII text file.

2) There is another simple method for orthogonalization of vectors: Gram-Schmidt procedure. However you should use a modified method and a small dimensions matrices (less than 100) to avoid round-off errors

Evgeny

Hi Evgeny,


As I udestand, a problem was solved.

Absolutely.

Thank you very much for the tips. I knew that Mathematica is able to export more than 6 digits (although I had some difficulties while specifying precision for N[] -- it doesn't honor my settings) but unfortunately that would be of little help. As I've mentioned earlier, the matrices I'm interested in are of order 1000 x 1000 and if you export a reasonable amount of digits, data file becomes really huge (for import/export purposes I mean). Binary data is, naturally, much more compact. Gram-Schmidt doesn't work for these matrices for the same reasons - they are too big.

Thank you again.