Section04 Orthonormal Bases and Gram-Schmidt

• Why orthogonality?
  1. The dot product of two orthogonal vectors is zero. $\boldsymbol{a}^{\text{T}}\boldsymbol{b} = 0$
  2. When the columns of $\boldsymbol{A}$ are orthonal to each other. The result of $\boldsymbol{A}^{\text{T}}\boldsymbol{A}$ is a diagonal matrix.
  3. It's easier to compute the solution to $\boldsymbol{A}^{\text{T}}\boldsymbol{A \hat{x}} = \boldsymbol{A}^{\text{T}}\boldsymbol{b}$
• Orthonormal
  1. orthonal unit vectors.
  2. The vector $\boldsymbol{q}_{1}, \cdots, \boldsymbol{q}_{n}$ are orthonormal if $$\boldsymbol{q}_{i}^{\text{T}}\boldsymbol{q}_{j} = \left\{ \begin{array}{lll} 0 & \text{when } i \ne j & \text{(orthonal vectors)} \\ 1 & \text{when } i = j & \text{(unit vectors: } \Vert \boldsymbol{q}_{i} \Vert = 1 \text{)} \end{array} \right.$$
  3. A matrix with orthonormal columns is denoted as $\boldsymbol{Q}$.
     • $\boldsymbol{Q}^{\text{T}}\boldsymbol{Q} = \boldsymbol{I}$
     • When $\boldsymbol{Q}$ is square, $\boldsymbol{Q}^{\text{T}}\boldsymbol{Q} = \boldsymbol{I}$ means that $\boldsymbol{Q}^{\text{T}} = \boldsymbol{Q}^{-1}$: transpose = inverse.
     • Multiplication by any orthonormal matrix $\boldsymbol{Q}$, lengths and angles don't change. ($\Vert \boldsymbol{Qx} \Vert = \Vert \boldsymbol{x} \Vert$)
• Three types orthonormal matrix
  1. Rotation matrix $$\boldsymbol{Q} = \left[ \begin{matrix} cos \theta & -sin \theta \\ sin \theta & cos \theta \end{matrix} \right]$$
  2. Permutation Matrix $$\boldsymbol{Q} = \left[ \begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix} \right]$$
     • Every permutation matrix is an orthogonal matrix.
  3. Reflection $$\begin{array}{c} \text{Suppose } \boldsymbol{u} \text{ is any unit vector. }\\ \boldsymbol{Q} = \boldsymbol{I} - 2 \boldsymbol{uu}^{\text{T}} \end{array}$$

Projections Using Orthonormal Bases: $\boldsymbol{Q}$ Replaces $\boldsymbol{A}$

Why

• When the orthonormal matrix $\boldsymbol{Q}$ replaces $\boldsymbol{A}$:

• When $\boldsymbol{Q}$ is square:
  • $\boldsymbol{p} = \boldsymbol{b}; \boldsymbol{P} = \boldsymbol{I}$
  • Application: Transform: $\boldsymbol{b} = \sum_{i=1}^{n}\boldsymbol{q}_{i}(\boldsymbol{q}_{i}^{\text{T}}\boldsymbol{b})$ (Break vector $\boldsymbol{b}$ or functions $f(x)$ into perpendicular pieces.) Fourier series.

The Gram-Schmidt Process

• Goal: three independent vectors $\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{c}$ to three orthogonal vectors $\boldsymbol{A}, \boldsymbol{B}, \boldsymbol{C}$

Steps

1. Choosing $\boldsymbol{A} = \boldsymbol{a}$
2. Choose $\boldsymbol{B}$ whose direcion is perpendicular to $\boldsymbol{A}$. $\boldsymbol{B} = \boldsymbol{b} - \frac{\boldsymbol{A}^{\text{T}}\boldsymbol{b}}{\boldsymbol{A}^{\text{T}}\boldsymbol{A}}\boldsymbol{A}$ ($\boldsymbol{b}$ subtract its projection along $\boldsymbol{A}$)
3. Choose $\boldsymbol{C}$ whose direction is perpendicular to $\boldsymbol{A}$ and $\boldsymbol{B}$. $\boldsymbol{C} = c - \frac{\boldsymbol{A}^{\text{T}}\boldsymbol{c}}{\boldsymbol{A}^{\text{T}}\boldsymbol{A}}\boldsymbol{A} - \frac{\boldsymbol{B}^{\text{T}}\boldsymbol{c}}{\boldsymbol{B}^{\text{T}}\boldsymbol{B}}\boldsymbol{B}$ ($\boldsymbol{c}$ subtract its peojection along $\boldsymbol{A}$ and $\boldsymbol{C}$)
4. ......

Idea

• Subtract from every new vector its projection in the directions already set.

The Factorization $\boldsymbol{A} = \boldsymbol{QR}$

$$\begin{array}{c} \left[ \begin{matrix} \boldsymbol{a} & \boldsymbol{b} & \boldsymbol{c} \end{matrix} \right] = \left[ \begin{matrix} \boldsymbol{q}_{1} & \boldsymbol{q}_{2} & \boldsymbol{q}_{3} \end{matrix} \right] \left[ \begin{matrix} \boldsymbol{q}_{1}^{\text{T}} \boldsymbol{a} & \boldsymbol{q}_{1}^{\text{T}} \boldsymbol{b} & \boldsymbol{q}_{1}^{\text{T}} \boldsymbol{c}\\ & \boldsymbol{q}_{2}^{\text{T}} \boldsymbol{b} & \boldsymbol{q}_{2}^{\text{T}} \boldsymbol{c} \\ & & \boldsymbol{q}_{3}^{\text{T}} \boldsymbol{c} \end{matrix} \right]\\ \Downarrow \\ \boldsymbol{A} = \boldsymbol{QR} \\ \Downarrow \\ \boldsymbol{R} = \boldsymbol{Q}^{\text{T}}\boldsymbol{A} \end{array}$$

• $\boldsymbol{R}$ is upper triangular matrix, because $\boldsymbol{q}_{i}$ is orthogonal to the first $i-1$ columns of $\boldsymbol{A}$

Application in LSQ

$$\begin{array}{ll} \because & \boldsymbol{A} = \boldsymbol{QR} \text{ and we want to solve } \boldsymbol{A}^{\text{T}}\boldsymbol{A \hat{x}} = \boldsymbol{A}^{\text{T}}\boldsymbol{b} \\ \therefore & (\boldsymbol{QR})^{\text{T}}(\boldsymbol{QR}) \boldsymbol{\hat{x}} = (\boldsymbol{QR})^{\text{T}}\boldsymbol{b} \\ & \boldsymbol{R}^{\text{T}}\boldsymbol{R}\boldsymbol{\hat{x}} = \boldsymbol{R}^{\text{T}}\boldsymbol{Q}^{\text{T}} \boldsymbol{b} \\ & \color{#D0104C}{\boldsymbol{R}\boldsymbol{\hat{x}} = \boldsymbol{Q}^{\text{T}}\boldsymbol{b}} \\ \therefore & \color{#D0104C}{\boldsymbol{\hat{x}} = \boldsymbol{R}^{-1}\boldsymbol{Q}^{\text{T}}\boldsymbol{b}} \\ \end{array}$$

Properties from Exerciese

1. If $\boldsymbol{Q}_{1}$ and $\boldsymbol{Q}_{2}$ are orthonormal matrices. Their product $\boldsymbol{Q}_{1}\boldsymbol{Q}_{2}$ is also an orthonormal matrix.
   • proof $$\begin{array}{ll} \because & \boldsymbol{Q}_{1} \text{ and } \boldsymbol{Q}_{2} \text{ are orthonormal matrices.} \\ \therefore & \boldsymbol{Q}_{1}^{\text{T}}\boldsymbol{Q}_{1} = \boldsymbol{I} \text{ and } \boldsymbol{Q}_{2}^{\text{T}}\boldsymbol{Q}_{2} = \boldsymbol{I} \\ \therefore & (\boldsymbol{Q}_{1}\boldsymbol{Q}_{2})^{\text{T}}\boldsymbol{Q}_{1}\boldsymbol{Q}_{2} = \boldsymbol{Q}_{2}^{\text{T}}\boldsymbol{Q}_{1}^{\text{T}}\boldsymbol{Q}_{1}\boldsymbol{Q}_{2} = \boldsymbol{Q}_{2}^{\text{T}}\boldsymbol{I}\boldsymbol{Q}_{2} = \boldsymbol{I} \\ \therefore & \boldsymbol{Q}_{1}\boldsymbol{Q}_{2} \text{ is also a orthonormal matrix.} \\ \end{array}$$
2. The Pivots for $\boldsymbol{A}^{\text{T}}\boldsymbol{A}$ must be the squares of diagonal entries of $\boldsymbol{R}$. $$\begin{array}{c} \boldsymbol{A} = \boldsymbol{QR} \\ \Downarrow \\ \boldsymbol{A}^{\text{T}}\boldsymbol{A} = \boldsymbol{R}^{\text{T}}\boldsymbol{R} = \boldsymbol{LDU} \end{array}$$
3. $\boldsymbol{Q}^{-1}$ is an orthogonal matrix when $\boldsymbol{Q}$ is an orthogonal matrix.
4. Reflection matrix $\boldsymbol{Q} = \boldsymbol{I} - 2\boldsymbol{uu}^{\text{T}} \text{ and } \boldsymbol{u}^{\text{T}}\boldsymbol{u} = \boldsymbol{I}$
   • $\boldsymbol{Qu} = (\boldsymbol{I} - 2 \boldsymbol{uu}^{\text{T}})\boldsymbol{u} = \boldsymbol{u} - 2 \boldsymbol{uu}^{\text{T}}\boldsymbol{u} = - \boldsymbol{u}$
   • Suppose $\boldsymbol{u}^{\text{T}}\boldsymbol{v} = 0$ ($\boldsymbol{u}$ and $\boldsymbol{v}$ are orthogonal.) $\boldsymbol{Qv} = (\boldsymbol{I} - \boldsymbol{uu}^{\text{T}})\boldsymbol{v} = \boldsymbol{v} - 0 = \boldsymbol{v}$
   • Reflection matrix reflect a vector across the hyperplane which is orthogonal to $\boldsymbol{u}$
5. If $\boldsymbol{A}$ is $m$ by $n$ with rank $r = n$, it could be factorized as $\boldsymbol{A} = \left[ \begin{matrix} \boldsymbol{Q}_{1} & \boldsymbol{Q}_{2} \end{matrix} \right] \left[ \begin{matrix} \boldsymbol{R} \\ \boldsymbol{0} \end{matrix} \right]$
   • The first $n$ columns of $\boldsymbol{Q}$ ($\boldsymbol{Q}_{1}$) are an orthonormal basis for column space.
   • The last $m-n$ columns of $\boldsymbol{Q}$ ($\boldsymbol{Q}_{2}$) are an orthonormal basis for left nullspace.