Gram-Schmidt Algorithm

Definition:

• Use the idea of Euclidean Projection on a line
• The basic idea is to first orthogonalize each vector w.r.t. previous ones; then normalize result to have norm one.

• Given a set of vectors $a_1,...,a_n$ that are Linear Independence

1. Let ${\tilde{q}}_1=a_1$
2. $q_1=$ normalized ${\tilde{q}}_1$
3. remove $q_1$ in vector $a_2,{\tilde{q}}_2=a_2-(a_2^T{q}_1)q_1$
4. $q_2=$ normalized ${\tilde{q}}_2$
5. remove $q_1,q_2$ in vector $a_3,{\tilde{a}}_3=a_3-(a_3^T{q}_1)q_1-(a_3^T{q}_2)q_2$
6. $q_3=$ normalized ${\tilde{q}}_3$
7. …

• If at step i, we find ${\tilde{q}}_i=0$, meaning that vector is linearly dependence, then we directly jump at the next step