# How to use orthogonalization methods to identify linearly dependent vectors numerically and efficiently?

I have a set of column vectors $[v_1,v_2,v_3,...,v_k]$ and I want to get the orthonormal basis $P$ for the range of those vectors. I use modified Gram-Schmidt to do orthogonalization. If $v_3$ is a linear combination of $v_1$ and $v_2$, when we orthogonalize $v_3$, it will return a $0$-vector. My problem is when a vector should be regarded as numerically zero?

I tried to calculate the norm of the residual after subtracting the projections onto previous basis and compare it with the norm of $v_3$, if this ratio is less than some number (like 1%), then I can regard it as a $0$-vector. But this method doesn't work well. Is there anybody can help me with this? I prefer not to use SVD because it's too expensive and I need good accuracy as well as efficiency in this case. Thanks a lot!

• The best methods are termed "rank-revealing" because of their attention to this issue. Do the columns $v_i$ have any special properties or relationships? – hardmath Jul 3 '13 at 15:20
• Those columns are the solution of maxwell wave equations and the purpose of orthogonalization is to extract physically important modes from them, but I don't think there are special properties numerically. – Jin Yan Jul 4 '13 at 4:23
• Is the order of the columns significant, as far as extracting the nodes? – hardmath Jul 4 '13 at 13:59

What you are trying to do is define a (relative) threshold $\epsilon$ to determine when a vector is zero: $$\| v_3^\perp \| \le \epsilon \|v_3\|.$$ You've chosen $\epsilon=0.01$ but this is of course as arbitrary as any other number you may have chosen. The problem is that there is no such universal constant that can be used. Among the factors you should take into account are

• The precision $\tau$ with which you do computations (e.g., float vs. double)
• The sizes of the vectors
• Whether the entries of the vectors are exact or subject to measurement noise
• etc

For example, if the elements are exact but you do computations in double precision $\tau\approx 10^{-16}$, then a vector for which $$\| v_3^\perp \| \le \tau\sqrt{N} \|v_3\|$$ must certainly be considered to be zero.

In practice, you will probably want to choose $\epsilon$ significantly larger than $\tau\sqrt{N}$, but 0.01 seems rather large unless the entries of your vectors are only inexactly known.

• I agree with you on that there is no universal threshold in this case. Your demonstration here seems to be convincing, but the detailed problem is a little bit complex, so except for this threshold, I may need to consider more. 'hardmath' gave a good point about 'rank-revealing', I may try that too. Thank you. – Jin Yan Jul 4 '13 at 4:30