Gram-Schmidt Process
The Gram-Schmidt process converts a linearly independent set of vectors into an orthogonal (or orthonormal) set spanning the same subspace.
Purpose
To construct orthogonal bases, used in QR decomposition, least squares, and the LLL algorithm.
Mechanism
Iterate: u_1=v_1, u_k=v_k - ∑(v_k·u_i)/(u_i·u_i) * u_i (i<k). Each step subtracts the projections onto the previous vectors. Orthonormalization additionally divides by ||u_i||.
Use cases
- QR decomposition
- Least squares
- Orthogonal basis construction