Advanced Linear Algebra: Are you ready?

Solution

• Given a set of vectors, the Gram-Schmidt process computes an orthonormal basis for the space spanned by those vectors. Given only two vectors, the two columns of the given matrix,

  \begin{equation*} A = \left( \begin{array}{c | c} a_0 \amp a_1 \end{array} \right),\text{,} \end{equation*}

  the process proceeds to compute the orthonormal basis \(\{ q_0, q_1 \} \) as follows:

  • The first basis vector \(q_0 \) equals the first column scaled to have unit length:

    • Compute the length of the first column \(\rho_{0,0} := \| a_0 \|_2 = \left\| \left(\begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \end{array}\right) \right\|_2 = \sqrt{2} \text{.}\)

    • \(q_0 := a_0 / \| a_0 \|_2 = a_0 / \rho_{0,0} = \frac{1}{\sqrt{2}} \left(\begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \end{array}\right) \text{.}\)

  • Compute the component of the second column that is orthogonal to \(q_0 \text{:}\)

    • \(\rho_{0,1} := q_0^T a_1 = \frac{1}{\sqrt{2}} \left(\begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \end{array}\right)^T \left(\begin{array}{rrr} 0 \\ 1 \\ 1 \\ 1 \end{array}\right) = \frac{1}{\sqrt{2}} \text{.}\)

    • \(\begin{array}{rcl} a_1^\perp \amp := \amp a_1 - q_0^T a_1 q_0 = a_1 - \rho_{0,1} q_0 = \left(\begin{array}{rrr} 0 \\ 1 \\ 1 \\ 1 \end{array}\right) - \frac{1}{\sqrt{2}} \frac{1}{\sqrt{2}} \left(\begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \end{array}\right) \\ \amp = \amp \left(\begin{array}{rrr} -\frac{1}{2} \\ \frac{1}{2} \\ 1 \\ 1 \end{array}\right) \end{array} \text{.}\)

  • The second basis vector \(q_1 \) equals the component of the second vector orthogonal to \(q_0 \text{,}\) scaled to have unit length:

    • Compute the length of \(a_1^T \text{:}\) \(\rho_{1,1} := \| a_1^\perp \|_2 = \left\| \left(\begin{array}{rrr} -\frac{1}{2} \\ \frac{1}{2} \\ 1 \\ 1 \end{array}\right) \right\|_2 = \frac{\sqrt{5}}{\sqrt{2}} \text{.}\)

    • \(q_1 := a_1^\perp / \| a_0^\perp \|_2 = a_1^\perp / \rho_{1,1} = \frac{\sqrt{2}}{ \sqrt{5} } \left(\begin{array}{rrr} -\frac{1}{2} \\ \frac{1}{2} \\ 1 \\ 1 \end{array}\right) \text{.}\)

    • For our example, the QR factorization of the matrix is given by

      \begin{equation*} \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c | c} a_0 \amp a_1 \end{array} \right) } \\ A \end{array} = \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c | c} q_0 \amp q_1 \end{array} \right) } \\ Q \end{array} \begin{array}[t]{c} \underbrace{ \left( \begin{array}{c | c} \rho_{0,0} \amp \rho_{0,1} \\ \hline 0 \amp \rho_{1,1} \\ \end{array} \right) } \\ R \end{array} \end{equation*}

      Thus

      \begin{equation*} \left(\begin{array}{r| rr} 1 \amp 0 \\ 1 \amp 1 \\ 0 \amp 1 \\ 0 \amp 1 \end{array}\right) = \left( \begin{array}{ c | c } \frac{1}{\sqrt{2}} \left(\begin{array}{r} 1 \\ 1 \\ 0 \\ 0 \end{array}\right) \amp \frac{\sqrt{2}}{ \sqrt{5} } \left(\begin{array}{rrr} -\frac{1}{2} \\ \frac{1}{2} \\ 1 \\ 1 \end{array}\right) \end{array} \right) \left( \begin{array}{ c | c } \sqrt{2} \amp 1 \\ \hline 0 \amp \frac{\sqrt{5}}{\sqrt{2}} \end{array} \right) . \end{equation*}

Relevance

Viewing information in an orthogonal basis simplifies visualing the solution. When we are first introduced to 2D and 3D visualization, the "xyz" axis are orthogonal (perpendicular) which allows one to easily describe the coordinate of points in the plane or space. Orthogonal bases provide the same benefits in a situation where the data does not nicely align with the various coordinate axes.

The Gram-Schmidt process provides a mathematical algorithm for computing an orthogonal basis. However, when computer arithmetic is employed, it can lead to a large accumulation of error. For this reason, in practice, modifications of this algorithm are often employed.

Viewing orthogonalization as a QR factorization has a benefit similar to why viewing Gaussian elimination as an LU factorization. It allows the algorithms to be made more systematic. It facilitates the development of alternative algorithms. It allows the theory of, for example, solving linear least squares problems to be elegantly described. It is fundamental to being able to analyze how computer arithmetic and algorithms interact.

Resources