Unit3.2.1Classical Gram-Schmidt (CGS)

Given a set of linearly independent vectors $\{ a_0, \ldots, a_{n-1} \} \subset \Cm \text{,}$ the Gram-Schmidt process computes an orthonormal basis $\{ q_0, \ldots, q_{n-1} \}$ that spans the same subspace as the original vectors, i.e.

\begin{equation*} \Span ( \{ a_0, \ldots, a_{n-1} \} ) = \Span ( \{ q_0, \ldots, q_{n-1} \} ) . \end{equation*}

The process proceeds as follows:

• Compute vector $q_0$ of unit length so that $\Span( \{ a_0 \} ) = \Span( \{ q_0 \} ) \text{:}$

• $\rho_{0,0} = \| a_0 \|_2$

Computes the length of vector $a_0 \text{.}$

• $q_0 = a_0 / \rho_{0,0}$

Sets $q_0$ to a unit vector in the direction of $a_0 \text{.}$

Notice that $a_0 = q_0 \rho_{0,0}$

• Compute vector $q_1$ of unit length so that $\Span( \{ a_0, a_1 \} ) = \Span( \{ q_0, q_1 \} ) \text{:}$

• $\rho_{0,1} = q_0^H a_1$

Computes $\rho_{0,1}$ so that $\rho_{0,1} q_0 = q_0^H a_1 q_0$ equals the component of $a_1$ in the direction of $q_0 \text{.}$

• $a_1^\perp = a_1 - \rho_{0,1} q_0$

Computes the component of $a_1$ that is orthogonal to $q_0 \text{.}$

• $\rho_{1,1} = \| a_1^\perp \|_2$

Computes the length of vector $a_1^\perp \text{.}$

• $q_1 = a_1^\perp / \rho_{1,1}$

Sets $q_1$ to a unit vector in the direction of $a_1^\perp \text{.}$

Notice that

\begin{equation*} \left( \begin{array}{c | c} a_0 \amp a_1 \end{array} \right) = \left( \begin{array}{c | c} q_0 \amp q_1 \end{array} \right) \left( \begin{array}{c | c} \rho_{0,0} \amp \rho_{0,1} \\ \hline 0 \amp \rho_{1,1} \end{array} \right) . \end{equation*}
• Compute vector $q_2$ of unit length so that $\Span( \{ a_0, a_1, a_2 \} ) = \Span( \{ q_0, q_1, q_2 \} ) \text{:}$

• $\begin{array}{l} \rho_{0,2} = q_0^H a_2 \\ \rho_{1,2} = q_1^H a_2 \end{array} \mbox{ or, equivalently, } \left( \begin{array}{c} \rho_{0,2} \\ \rho_{1,2} \end{array} \right) = \left( \begin{array}{c c} q_0 \amp q_1 \end{array} \right)^H a_2$

Computes $\rho_{0,2}$ so that $\rho_{0,2} q_0 = q_0^H a_2 q_0$ and $\rho_{1,2} q_1 = q_1^H a_2 q_1$ equal the components of $a_2$ in the directions of $q_0$ and $q_1 \text{.}$

Or, equivalently, $\left( \begin{array}{c c} q_0 \amp q_1 \end{array} \right) \left( \begin{array}{c} \rho_{0,2} \\ \rho_{1,2} \end{array} \right)$ is the component in $\Span( \{ q_0, q_1 \} ) \text{.}$

• $a_2^\perp = a_2 - \rho_{0,2} q_0 - \rho_{1,2} q_1 = a_2 - \left( \begin{array}{c c} q_0 \amp q_1 \end{array} \right) \left( \begin{array}{c} \rho_{0,2} \\ \rho_{1,2} \end{array} \right)$

Computes the component of $a_2$ that is orthogonal to $q_0$ and $q_1 \text{.}$

• $\rho_{2,2} = \| a_2^\perp \|_2$

Computes the length of vector $a_2^\perp \text{.}$

• $q_2 = a_2^\perp / \rho_{2,2}$

Sets $q_2$ to a unit vector in the direction of $a_2^\perp \text{.}$

Notice that

\begin{equation*} \left( \begin{array}{c c | c} a_0 \amp a_1 \amp a_2 \end{array} \right) = \left( \begin{array}{c c | c} q_0 \amp q_1 \amp q_2 \end{array} \right) \left( \begin{array}{c c | c} \rho_{0,0} \amp \rho_{0,1} \amp \rho_{0,2} \\ 0 \amp \rho_{1,1} \amp \rho_{1,2} \\ \hline 0 \amp 0 \amp \rho_{2,2} \end{array} \right) . \end{equation*}
• And so forth.

Yet another way of looking at this problem is as follows.

Consider the matrices

\begin{equation*} A = \left( \begin{array}{c | c | c | c | c | c | c} a_0 \amp \cdots \amp a_{k-1} \amp a_k \amp a_{k+1} \amp \cdots \amp a_{n-1} \end{array} \right) \end{equation*}

and

\begin{equation*} Q = \left( \begin{array}{c | c | c | c | c | c | c} q_0 \amp \cdots \amp q_{k-1} \amp q_k \amp q_{k+1} \amp \cdots \amp q_{n-1} \end{array} \right) \end{equation*}

We observe that

• $\Span( \{a_0\} ) = \Span( \{ q_0 \} )$

Hence $a_0 = \rho_{0,0} q_0$ for some scalar $\rho_{0,0} \text{.}$

• $\Span( \{a_0, a_1\} ) = \Span( \{ q_0, q_1 \} )$

Hence

\begin{equation*} a_1 = \rho_{0,1} q_0 + \rho_{1,1} q_1 \end{equation*}

for some scalars $\rho_{0,1}, \rho_{1,1} \text{.}$

• In general, $\Span( \{a_0, \ldots, a_{k-1}, a_{k}\} ) = \Span( \{ q_0, \ldots, q_{k-1}, q_k \} )$

Hence

\begin{equation*} a_k = \rho_{0,k} q_0 + \cdots + \rho_{k-1,k} q_{k-1} + \rho_{k,k} q_k \end{equation*}

for some scalars $\rho_{0,k}, \cdots, \rho_{k,k} \text{.}$

Let's assume that $q_0, \ldots, q_{k-1}$ have already been computed and are mutually orthonormal. Consider

\begin{equation*} a_k = \rho_{0,k} q_0 + \cdots + \rho_{k-1,k} q_{k-1} + \rho_{k,k} q_k. \end{equation*}

Notice that

\begin{equation*} \begin{array}{rcl} q_k^H a_k \amp = \amp q_k^H \left( \rho_{0,k} q_0 + \cdots + \rho_{k-1,k} q_{k-1} + \rho_{k,k} q_k \right) \\ \amp = \amp \rho_{0,k} \begin{array}[t]{c} \underbrace{ q_k^H q_0 } \\ 0 \end{array} + \cdots + \rho_{k-1,k} \begin{array}[t]{c} \underbrace{ q_k^H q_{k-1} } \\ 0 \end{array} + \rho_{k,k} \begin{array}[t]{c} \underbrace{ q_k^H q_k } \\ 1 \end{array} \end{array} \end{equation*}

so that

\begin{equation*} \rho_{i,k} = q_i^H a_k, \end{equation*}

for $i = 0, \ldots , k-1 \text{.}$ Next, we can compute

\begin{equation*} a_k^\perp = a_k - \rho_{0,k} q_0 - \cdots - \rho_{k-1,k} q_{k-1} \end{equation*}

and, since $\rho_{k,k} q_k = a_k^\perp\text{,}$ we can choose

\begin{equation*} \rho_{k,k} = \| a_k^\perp \|_2 \end{equation*}

and

\begin{equation*} q_k = a_k^\perp / \rho_{k,k} \end{equation*}
Remark3.2.1.1.

For a review of Gram-Schmidt orthogonalization and exercises orthogonalizing real-valued vectors, you may want to look at Linear Algebra: Foundations to Frontiers (LAFF) [26] Week 11.