Orthogonalization method

The basic authors of the description: Инжелевская Дарья Валерьевна(text), А.В.Фролов(editing)

The Gram--Schmidt orthogonalization is a method that constructs a set of orthogonal vectors ${\displaystyle \mathbf {b}_{1},\;\ldots ,\;\mathbf {b} _{N}}$ or a set of orthonormal vectors ${\displaystyle \mathbf {e} _{1},\;\ldots ,\;\mathbf {e}_{N}}$ from a given set of linearly independent vectors ${\displaystyle \mathbf {a} _{1},\;\ldots ,\;\mathbf {a} _{N}}$. This is done in such a way that each vector ${\displaystyle \mathbf {b} _{j}}$ or ${\displaystyle \mathbf {e} _{j}}$ is a linear combination of the vectors ${\displaystyle \mathbf {a} _{1},\;\ldots ,\; \mathbf {a} _{j}}$. The process may be used for obtaining the QR decomposition, where the system of original vectors is the columns of a given matrix, while the columns of Q are the result of orthogonalization. Thus, unlike the Givens (rotation) and Householder (reflection) methods, which are based on the left unitary/orthogonal reduction to triangular form, the orthogonalization method reduces the original matrix by right non-orthogonal (triangular) transformations to a unitary/orthogonal matrix.

Mathematical foundations of the method

The classical orthogonalization method for the QR decomposition of a square matrix (real version) is fairly simple. However, due to its instability, which manifests itself in the non-orthogonality of resulting systems, the method is very rarely used in practice.

Let $\mathbf{a}_1,\;\ldots,\;\mathbf{a}_N$ be linearly independent vectors. Define the projection of a vector $\mathbf{a}$ on (the direction of) a vector $\mathbf{b}$ by the formula $\mathbf{proj}_{\mathbf{b}}\,\mathbf{a} = {\langle \mathbf{a}, \mathbf{b} \rangle \over \langle \mathbf{b}, \mathbf{b}\rangle} \mathbf{b} ,$

where $\langle \mathbf{a}, \mathbf{b} \rangle$ is the scalar product of the vectors $\mathbf{a}$ and $\mathbf{b}$.

In the k-dimensional real space, the scalar product of the vectors $\mathbf{ a= [a_1, a_2, ...,a_k]}$ and $\mathbf{ b= [b_1, b_2, ..., b_k]}$ is defined as

$\langle \mathbf{a}, \mathbf{b} \rangle=\sum_{i=1}^k a_ib_i=a_1b_1+a_2b_2+\cdots+ a_kb_k$.

The above operator projects the vector $\mathbf{a}$ on the direction of the vector $\mathbf{b}$.

The orthogonality of the first two vectors in the orthogonalization process below is attained at Step (2).

The classical Gram--Schmidt process is performed as follows:

${\begin{array}{lclr} {\mathbf {b}}_{1}&=&{\mathbf {a}}_{1}&(1)\\ {\mathbf {b}}_{2}&=&{\mathbf {a}}_{2}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{2}&(2)\\ {\mathbf {b}}_{3}&=&{\mathbf {a}}_{3}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{3}-{\mathbf {proj}}_{{{\mathbf {b}}_{2}}}\,{\mathbf {a}}_{3}&(3)\\ {\mathbf {b}}_{4}&=&{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{1}}}\,{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{2}}}\,{\mathbf {a}}_{4}-{\mathbf {proj}}_{{{\mathbf {b}}_{3}}}\,{\mathbf {a}}_{4}&(4)\\ &\vdots &&\\{\mathbf {b}}_{N}&=&{\mathbf {a}}_{N}-\displaystyle \sum _{{j=1}}^{{N-1}}{\mathbf {proj}}_{{{\mathbf {b}}_{j}}}\,{\mathbf {a}}_{N}&(N) \end{array}}$

From each vector $\mathbf{b}_j \;(j = 1 \ldots N)$, one can obtain a normalized vector: $\mathbf{e}_j = {\mathbf{b}_j\over \| \mathbf{b}_j \|}$ (the normalized vector has the same direction as the original one, while its norm is 1 ). Here, the norm is consistent with the scalar product: $\| x \| = \sqrt{\langle x, x \rangle}$

The output of the Gram--Schmidt process:

The system $\mathbf{b}_1,\;\ldots,\;\mathbf{b}_N$ of orthogonal vectors or the system $\mathbf{e}_1,\;\ldots,\;\mathbf{e}_N$ of orthonormal vectors.

In practice, the most often used form of the method is the orthogonalization method with re-orthogonalization.