Let $\{u_1,u_2,\ldots,u_n\}$ be the orthogonal (i.e., before the normalization) basis obtained from linearly independent vectors $\{v_1,v_2,\ldots,v_n\}$ by the Gram-Schmidt process, starting from $u_1=v_1$ and $$u_j=v_j-\sum_{k=1}^{j-1}\langle v_j,u_k/\| u_k\|\rangle u_k/\| u_k\|, \quad\text{ for }2\leq j\leq n.$$

From the linear independence, the resulting vectors will be non-zero. But intuitively, if $\{v_1,v_2,\ldots,v_n\}$ are close to linear dependent, some $u_j$ should be near $0$.

I wonder if we can assess how close $\|u_j\|$ are to $0$ (lower bound of $\|u_j\|$) in terms of how linear independent ${v_1,\dots,v_n}$ are. I thought of getting a lower bound of $\|u_j\|$ in terms of the smallest eigenvalue of the Gram matrix of $(v_1|\cdots|v_n)$, but no luck.

  • $\begingroup$ It's an interesting question. But In the first place you formula would should get simplified in simply normalization, because they're already orthogonal. Therefore in an actual (numerical implementation) you would use the full formula, but just the normalization. Once you do that you can use the properties of the floating division algorithm to find an answer. $\endgroup$ – user8469759 Apr 26 at 7:56
  • $\begingroup$ Bear in mind anyway that the theoretical formula you provided won't give you any answer, because that assumes real arithmetic. When you move from real to floating point arithmetic there're few implementation factors to take into account. As a guess though I'd say you can use relative error, page 371 of ftp.demec.ufpr.br/CFD/bibliografia/… gives an analysis of the error, probably your case is a special case of that one (I just had a quick look, I'll read through it later because I got curious now). $\endgroup$ – user8469759 Apr 26 at 8:03
  • 4
    $\begingroup$ The magnitudes of $u_i$ are equal to the corresponding diagonal entries of $R$ in the QR decomposition $[v_1, \dots, v_n] = Q R$. Maybe that helps. $\endgroup$ – Rahul Apr 26 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.