Gram-Schmidt orthogonalization

The Gram-Schmidt process is used to find a set of orthogonal vectors from a general set of vectors.

Suppose we have a set of nonorthogonal vectors v₀...v_n-1 and from them we want to create the orthogonal set w₀...w_n-1. (n is the dimension.) We can simply use the first vector from the nonorthogonal set as the starting vector for the new set: w₀.

The next vector can be obtained by projecting v₁ on w₀, and then subtracting the projection from v₁: w₁ = v₁ - proj_w0v₁ = v₁ - ( v₁ . w₀ / ||w₀||² ) (w₀).

The rough idea should be clear by now. For w₂, w₂ = v₂ - proj_w0v₂ - proj_w1v₂. The same process is repeated for the remaining vectors: w_i = v_i - sigma^i-1_j=0(proj_wjv_i). Thus, we are able to obtain the set of orthogonal vectors from the general set of vectors.

To get an orthonormal set instead, either perform the normalization at the end, or normalize each w as we go along.