---
tags: Linear Algebra - HungYiLee
---

Linear Algebra - Lec 31~31-2: Orthogonal Basis and Gram-Schmidt Process
===

[TOC]

# [課程網站](http://speech.ee.ntu.edu.tw/~tlkagk/courses_LA18.html)

# [Lecture 31: Orthogonal Basis](https://www.youtube.com/watch?v=98-0Q1ed3sM&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=31)

## Orthogonal Set

- orthogonal 的 vector set 不一定是 independent 的
- 但若它是 non-zero 的 vector set，就是 independent 的


## Orthonormal Set

- A set of vectors is called an **orthonormal set** if it is an orthogonal set, and the norm of all the vectors is 1
- norm 是 1 的 vector 被稱為 **unit vector**
- orthonormal set **是 independent 的**

## Orthogonal Basis

- A basis that is an orthogonal (orthonormal) set is called an orthogonal (orthonormal) basis basis

## Orthogonal Decomposition Theory

subspace $W$ 中的任何 vector $u$ 都可以被拆解成 **orthogonal basis** 的 linear combination，而 linear combination 的 **coefficient $c_i = \dfrac{u\cdot v_i}{\|v_i\|^2}$**
- 而若是 orthonormal basis，公式更簡單：$c_i=u\cdot v_i$


### Example


### Orthogonal Projection

- **任何 vector $u$ 在 subspace $W$ 的 orthogonal projection 其實和上面的式子一模一樣**

#### Proof - Orthogonal Projection


影片看不到證明，應該是這樣推導
1. Let $S=\{v_1,v_2,...,v_k\}$ be an orthogonal basis for a subspace $W$. Let $u\in\mathbb R^n$ be any vector, and $w$ is the orthogonal projection of $u$ on $W$.
1. $C^T=\begin{bmatrix}v_1^T\\v_2^T\\\vdots\\v_k^T\end{bmatrix}\in\mathbb R^{k\times n}, C=\begin{bmatrix}v_1&v_2&...&v_k\end{bmatrix}\in\mathbb R^{n\times k}$ (老師表示投影片有些錯誤)
1. **若 $\{v_1,...,v_k\}$ 是 orthogonal 的，則 $C^TC$ 會是 diagonal matrix**，我們用 $D$ 來表示 diagonal matrix $C^TC$
- proof: $C^TC=\begin{bmatrix}v_1^Tv_1&v_1^Tv_2&\dots &v_1^Tv_k\\v_2^Tv_1&v_2^Tv_2&\dots&v_2^Tv_k\\\vdots&\vdots&\ddots&\vdots\\v_k^Tv_1&v_k^Tv_2&\dots&v_k^Tv_k\end{bmatrix}$，又 $\{v_1,...,v_k\}$ 是 orthogonal 的，因此非對角線的部分都是 0。$D=C^TC=\begin{bmatrix}v_1^Tv_1&0&\dots &0\\0&v_2^Tv_2&\dots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\dots&v_k^Tv_k\end{bmatrix}=\begin{bmatrix}\|v_1\|^2&0&\dots &0\\0&\|v_2\|^2&\dots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\dots&\|v_k\|^2\end{bmatrix}$

1. 此時 orthogonal projection matrix 可以表示成 $P_W=CD^{-1}C^T$，**而 projected vector $w=CD^{-1}C^Tu$**
- 其實 diagonal matrix 的 inverse 就是對角線每個 element 取倒數，因此 $D^{-1}=(C^TC)^{-1}=\begin{bmatrix}1/\|v_1\|^2&0&\dots &0\\0&1/\|v_2\|^2&\dots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\dots&1/\|v_k\|^2\end{bmatrix}$
1. 要算 $w=CD^{-1}C^Tu$ 可以先來看 $C^Tu\in\mathbb R^k$ 長什麼樣子，利用 matrix-vector product 的 row aspect (review Lec 5) 我們可以知道 $C^Tu=\begin{bmatrix}v_1^Tu\\v_2^Tu\\\vdots\\v_k^Tu\end{bmatrix}=\begin{bmatrix}v_1\cdot u\\v_2\cdot u\\\vdots\\v_k\cdot u\end{bmatrix}$

1. 所以 $w=CD^{-1}C^Tu=CD^{-1}\begin{bmatrix}v_1\cdot u\\v_2\cdot u\\\vdots\\v_k\cdot u\end{bmatrix}$
- 利用 4. 得出的結論，$D^{-1}\begin{bmatrix}v_1\cdot u\\v_2\cdot u\\\vdots\\v_k\cdot u\end{bmatrix}= \begin{bmatrix}1/\|v_1\|^2&0&\dots &0\\0&1/\|v_2\|^2&\dots&0\\\vdots&\vdots&\ddots&\vdots\\0&0&\dots&1/\|v_k\|^2\end{bmatrix}\begin{bmatrix}v_1\cdot u\\v_2\cdot u\\\vdots\\v_k\cdot u\end{bmatrix}=\begin{bmatrix}\dfrac{v_1\cdot u}{\|v_1\|^2}\\\dfrac{v_2\cdot u}{\|v_2\|^2}\\\vdots\\\dfrac{v_k\cdot u}{\|v_k\|^2}\end{bmatrix}$

1. 那麼 $w = CD^{-1}C^Tu=C\begin{bmatrix}\dfrac{v_1\cdot u}{\|v_1\|^2}\\\dfrac{v_2\cdot u}{\|v_2\|^2}\\\vdots\\\dfrac{v_k\cdot u}{\|v_k\|^2}\end{bmatrix}=\begin{bmatrix}v_1&v_2&...&v_k\end{bmatrix}\begin{bmatrix}\dfrac{v_1\cdot u}{\|v_1\|^2}\\\dfrac{v_2\cdot u}{\|v_2\|^2}\\\vdots\\\dfrac{v_k\cdot u}{\|v_k\|^2}\end{bmatrix}$

1. 再利用 column aspect (review Lec 5) 得證 $w=(\dfrac{v_1\cdot u}{\|v_1\|^2})v_1+(\dfrac{v_2\cdot u}{\|v_2\|^2})v_2+...+(\dfrac{v_k\cdot u}{\|v_k\|^2})v_k$

## How to find Orthonormal Basis

Let $\{u_1,...u_k\}$ be a basis of subspace $W$ (投影片筆誤). How to transform $\{u_1, ..., u_k\}$ into an orthogonal basis $\{v_1, ..., v_k\}$ ?
- **Gram-Schmidt Process**
- $v_1=u_1,\\v_2=u_2-\dfrac{u_2\cdot v_1}{\|v_1\|^2}v_1,\\v_3=u_3-\dfrac{u_3\cdot v_1}{\|v_1\|^2}v_1-\dfrac{u_3\cdot v_2}{\|v_2\|^2}v_2,\\\,\,\,\,\,\,\,\,\vdots\\v_k=u_k-\dfrac{u_k\cdot v_1}{\|v_1\|^2}v_1-\dfrac{u_k\cdot v_2}{\|v_2\|^2}v_2-...-\dfrac{u_k\cdot v_{k-1}}{\|v_{k-1}\|^2}v_{k-1}$

- **可以直觀理解成，把 vector 在某 subspace 的 orthogonal projection 扣掉，剩下的就落在 subspace 的 perp 裡面，做到最後就可以得到 orthogonal 的 basis**

# [Lecture 31-2: Gram-Schmidt Process](https://www.youtube.com/watch?v=PzqVLldlHTE&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=32)

### Visualization

[Gram-Schmidt Process / Orthonormalization of a basis in R³ (animation)](https://www.youtube.com/watch?v=Ys28-Yq21B8)
{%youtube Ys28-Yq21B8 %}
如何把 basis $\{v_1,v_2,v_3\}$ 轉成 orthogonal basis $\{u_1,u_2,u_3\}$
1. 把 $u_1$ 指定為 $v_1$
2. $v_2$ 減去它在 $u_1$ 上的投影得到 $u_2$
3. $v_3$ 減去它在 $u_1$ 上的投影得到 $v_3'$，再減去 $v_3'$ 在 $u_2$ 上的投影就得到 $u_3$
4. 要得到 orthonormal basis 只要再 normalize 就好

註：影片中的 $u,v$ 和這門課相反

### Proof - Gram-Schmidt Process

- $Span\,\{v_1,...,v_i\}=Span\,\{u_1,...,u_i\}$ 這裡的 $i$ 可以是任何值

用這種方式找出來的 vector set $\{v_1,...,v_k\}$，要證明以下兩點：
1. 它們是 orthogonal 的 vector set
2. 它們的 Span 會和 $\{u_1,...,u_k\}$ 相同

#### 證明 orthogonal

利用歸納法
1. 假設 $\{v_1,...,v_n\}$ 已經是一個 orthogonal vector set，證明這樣算出來的 $v_{n+1}$ 加進去也會是一個 orthogonal vector set
2. 把 $v_{n+1}$ 公式兩邊都和 $v_i$ 做 dot product，可以證明 $v_{n+1}\cdot v_i=0, \,\forall i<n+1$

#### 證明 Span 相同

1. Review: 對於 dimension 為 $k$ 的 subspace，只要能在 basis 中找到 $k$ 個 independnet vector，就能確定它們是 basis。因此只需要確認兩點
- $\{v_1,...,v_k\}\in Span\,\{u_1,...,u_k\}$
- $\{v_1,...,v_k\}$ 是 independent 的
1. 仔細觀察又可以發現，每個 $u$ 都是 $v$ 的 linear combination，因此 $\{v_1,...,v_k\}\in Span\,\{u_1,...,u_k\}$
1. 前面已經證明過它們是 orthogonal 的，那麼只要不含 zero vector，就是 independent 的
1. 根據公式可以推導出 $v_1,...,v_k$ 都不可能是 zero vector，因此它們是 independent 的。故得證 $Span\,\{v_1,...,v_k\} = Span\,\{u_1,...,u_k\}$

### Example