---
# System prepended metadata

title: 'Linear Algebra - Lec 29~30: Orthogonality and Orthogonal Projection'
tags: [Linear Algebra - HungYiLee]

---

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

Linear Algebra - Lec 29~30: Orthogonality and Orthogonal Projection
===

[TOC]

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

# [Lecture 29: Orthogonality](https://www.youtube.com/watch?v=hxI7stenqaw&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=29)

## Dot Product & Orthogonal

![](https://i.imgur.com/zrKFHtf.png)
- **重要**：$u\cdot v = u^T v$ 
- Orthogonal means $u\cdot v=0$
- Orthogonal is actually **"perpendicular"**
- **zero vector** is orthogonal to every vector

## Norm & Distance

![](https://i.imgur.com/OA6C0xY.png)

### More about Norm

- $L^p$ norm of vector $v$ is $\lVert v\rVert_p=\begin{pmatrix}\sum_\limits{i=1}^n\lvert v_i\rvert^p\end{pmatrix}^{1/p}$
- 自行補充：$L^\infty$ norm (max norm) is $\max_i(v_i)$
![](https://i.imgur.com/l8lGr72.png)

### More about Dot Product

![](https://i.imgur.com/PD4u9k8.png)
- 特別 $(Au)\cdot v=u\cdot (A^Tv)$
    - proof: $Au\cdot v\\=(Au)^Tv\\=(u^TA^T)v\\=u\cdot A^Tv$
    - 記法：利用 $u\cdot v=u^Tv$ 的性質，得知 $A$ 要放到後面就要先 transpose。
- 可以利用這些來證明 $\lVert 2u+3v\rVert^2=4\lVert u\rVert^2+12(v\cdot u)+9\lVert v\rVert^2$
    - proof: $\lVert 2u+3v\rVert^2\\=(2u+3v)\cdot(2u+3v)\\=2u\cdot(2u+3v)+3v\cdot(2u+3v)\\=4\lVert u\rVert^2+12(v\cdot u)+9\lVert v\rVert^2$

## Pythagorean Theorem 

![](https://i.imgur.com/Th2NG2K.png)
- 其實就是 畢氏定理

![](https://i.imgur.com/4pSRGIg.png)
- parallelogram: 對角線
- rhombus: 菱形
- 如果平行四邊形的兩個向量分別 $u,v$，且**對角線是 orthogonal，則它是菱形**
- proof: 兩個對角線分別是 $u+v$ 和 $u-v$，又 $(u+v)\cdot(u-v)=0$，得證 $\lVert u\rVert=\lVert v\rVert$

## Triangle Inequality 三角不等式

- 利用 Cauchy-Schwarz Inequality (柯西不等式) $|u\cdot v|\leq|u||v|$ 就能證明
![](https://i.imgur.com/v42LgV6.png)

### 後面沒注意聽哈哈

# [Lecture 30: Orthogonal Projection](https://www.youtube.com/watch?v=6WJikUaKKNo&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=30)

## Orthogonal Complement

- $S$ 不一定要是 subspace，只要是 vector set 即可
- $S$ 的 orthogonal complement $S^\perp$ **又稱 $S$ 的 perp**
![](https://i.imgur.com/X8EeY4o.png)
- 要證明某個 vector set $V$ 就是 $W^\perp$，那就只要證明 $V\subseteq W^\perp$ 且 $W^\perp\subseteq V$ 即可得證 $V=W^\perp$

## Properties of Orthogonal Complement

1. $S^\perp$ 必定是個 subspace
2. $(Span\,S)^\perp=S^\perp$ for any non-empty vector set $S$
3. if $B$ is a basis of subspace $W$, then $B^\perp=W^\perp$
4. $S\cap S^\perp$ is zero vector
    - ***Q: 個人覺得存疑欸，$S$ 不一定包含 zero vector 吧? 前提應該是 $S$ 有 zero vector?***

### Example

![](https://i.imgur.com/GkO8AjQ.png)

## Properties of Orthogonal Complement II

1. 任何 matrix $A$ 的 row space 的 perp 就是 $A$ 的 null space
    - $(Row\,A)^\perp=Null\,A$
2. 同理，$(Col\,A)^\perp=Null\,A^T$
3. $\dim(W)+\dim(W^\perp)=n$
    - 容易理解的 example：在三維空間中，$W$ 是二維平面，則 $W^\perp$ 就是該平面的法向量(一維)
    - proof 沒注意聽

![](https://i.imgur.com/bIoKfjP.png)

## Unique

![](https://i.imgur.com/2ZhtAeH.png)
Conclusion
1. 若 $W$ 的 basis 有 $k$ 個 vector；則 $W^\perp$ 的 basis 有 $n-k$ 個 vector，而且所有這些 vector 會組成 $\mathbb R^n$ 的 basis，也就是所有 vector 是 independent 的
    - proof 好像是寫在黑板上的，改天自己證

2. $W$ 是一個 subspace，則 ***任何一個 vector 都可以被拆解成兩個 vector***，一個 vector 落在 $W$ ；另一個 vector 落在 $W^\perp$，並且 ***這個拆解是唯一的***
    - proof 也是寫在黑板上?

## Orthogonal Projection

- orthogonal projection 是一個 **linear** 的 operation
    - proof 沒注意聽，要利用 "唯一" 的特性

![](https://i.imgur.com/vXpESBX.png)

## Closest Vector Property

- $w$ 和 $u$ 的距離是最短的

proof:
1. $u-w$ 和 subspace $W$ 中的任何 vector 一定是 orthogonal
2. 因此 $(u-w)\cdot(w-w')=0$
3. 故 $\lVert u-w'\rVert^2 = ((u-w)+(w-w'))^2=\lVert u-w\rVert^2+\lVert w-w'\rVert^2>\lVert u-w\rVert^2$

## Orthogonal Projection Matrix

![](https://i.imgur.com/2PWf3UK.png)
- 既然 $U_w(\cdot)$ 這個 projection function 是 linear 的，那就有一個 projection matrix $P_W$ 來代表這個 function
- 也就是說 $P_Wu = w$
- 注意，在 subspace 的 vector $v$ 乘上 projection matrix $P_W$ 後仍然是它自己
    - $P_Wv = v$

## How to do Orthogonal Projection

### Orthogonal Projection on a line

先做做看一維 subspace 的 orthogonal projection
![](https://i.imgur.com/Bh4OIGb.png)
- Conclusion
    - 任何 vector $v$ 在 $u$ 上的 orthogonal projection $w$ 可以寫成 $u$ 乘上 scalar $c$，即 $w=cu$
    - $c=\dfrac{v\cdot u}{\|u\|^2}$

- Proof
    - 利用 $(v-w)\cdot u=0$ 即可解出 $c$

#### Example

![](https://i.imgur.com/SyshafB.png)

### Find the Orthogonal Projection Matrix

#### Conclusion
- 令 matrix $C\in\mathbb R^{n\times k}$ 的 columns 就是 subspace $W$ 的 basis
    - 也就是說 $W\in\mathbb R^n$ 且 $W$ 的 dimension 就是 $k$
- 則 **subspace $W$ 的 orthogonal projection matrix $P_W=C(C^TC)^{-1}C^T$**

#### Proof
1. 若 $u\in\mathbb R^n$ 是我們要 projection 的對象，$w$ 是 projection 後的 vector。$w=U_W(u)=P_Wu$
2. 我們知道 $W=Col(C)$，故 $w=Cb, \exists b\in\mathbb R^k$
3. $u-w\in W^\perp$，又 $C^T$ 的每個 row 都是 $W$ 的 basis，故 $0=C^T(u-w)=C^Tu-C^Tw=C^Tu-C^TCb$
4. 因此 $C^Tu=C^TCb$
5. 那麼就可以得到 $b=(C^TC)^{-1}C^Tu$ (若 $C^TC$ 是 invertible 的)
6. 得證 $w = Cb = C(C^TC)^{-1}C^Tu$，即 $P_W=C(C^TC)^{-1}C^T$

以上要成立必須再證明若 $C$ 的 columns 是 independent 的，則 $C^TC$ 是 invertible 的，即 $C^TC$ 的 columns 也是 independent 的。那麼我們只要證明 $C^TCb=0$ 的解 $b$ 只有 zero vector 即可。
![](https://i.imgur.com/BuPcTF6.png)

## Application of Orthogonal Projection

### Solution of Inconsistent System of Linear Equations

$Ax=b$ 無解，那就找最近似的解
- Suppose $Ax=b$ is an inconsistent system of linear equations.
- then $b$ is not in the column space of $A$
- Find vector $z$ minimizing $\|Az-b\|$

![](https://i.imgur.com/7TkAynD.png)

### Least Square Approximation

![](https://i.imgur.com/td2xVSp.png)

![](https://i.imgur.com/0IIoqHG.png)

![](https://i.imgur.com/oGv4fwt.png)

![](https://i.imgur.com/62WiI1N.png)

#### Conclusion

希望找到一個 vector $a$ 使得 $\|y-Ca\|^2$ 越小越好，那其實就跟前面那個 inconsistent linear system 的問題一樣，我們希望找到 $x$ 使得 $\|Ax-b\|$ 的值越小越好

#### Example

![](https://i.imgur.com/JVzckca.png)

#### Example: Best quadratic fit

![](https://i.imgur.com/UXPHaXp.png)

![](https://i.imgur.com/9Ka69sU.png)

### Multivariable Least Square Approximation

![](https://i.imgur.com/vhjzXyE.png)