Franklin's Notes

Gram-Schmidt process

The Gram-Schmidt process is an algorithm for constructing an orthonormal basis for a finite-dimensional subspace $S\subset X$. It can also be used to compute QR factorizations . If $S$ has basis ${a_1,\cdots,a_n}$, then the elements of the orthogonal basis can be defined recursively as

where the $P_i$ are projectors onto the orthogonal complement of the subspace spanned by the previous $q_i$, defined as

where $\hat Q_j = [q_1|q_2|\cdots | q_j]$.

This is the classical Gram-Schmidt algorithm, and it is numerically unstable. To improve stability, we can use the modified Gram-Schmidt algorithm, which is equivalent in exact arithmetic but much more stable in finite-precision arithmetic. In this algorithm, the unnormalized basis vectors $v_i$ are calculated as

where the $P_{\perp q_j}$ are orthogonal projectors given by projecting onto the orthogonal complement of each normalized basis vector $q_j$, which can be calculated as $v_j/\lVert v_j\rVert$ once $v_j$ is known. Note that, when implementing this algorithm in practice, we need not actually compute and store the matrices $P_{\perp q_j}$, as this would be inefficient, since we can actually compute the product which can be calculated in only $\mathcal{O}(n)$ operations by converting the matrix-vector product $(q_jq_j^\ast)v_j$ into a vector-vector inner product multiplied by a vector $(q_j^\ast v_j)q_j$.

Another interesting distinction between CGS and MGS: when used to compute the entries of $R$ in the QR Factorization , the classical algorithm computes the entries of $R$ column-wise, whereas the modified algorithm computes the entries of $R$ row-wise.




back to home page