# 線性代數 Linear Algebra (U1014) - 6.7 Singular Value Decomposition (SVD)
###### tags: `Linear Algebra (U1014, Spring, 2021)`
通訊系 江振宇 副教授

> 20210629 初版
> 20230614 修改 Heading Level 2
> 20230617 增加講解影片
> 20230625 增加 assignment 5 詳解
> 20250603 修正排版以及小錯、增加 SVD 以及 rank-1 matrices 的推導關係

---

## 教學影片

教學影片 Part 1: https://youtu.be/PDV8cRCaIh8 (27 min)
教學影片 Part 2: https://youtu.be/iB62TWTTnxQ (63 min)
教學影片 Part 3: https://youtu.be/rbm9TrkY_iU (47 min)

---

## A. Preface - Eigen for Square Matrices

回顧 linear transformation 的意義：

$$y_{(m\times 1)}=A_{(m\times n)}x_{(n\times 1)}\tag{1}$$

其實就是拿 $A$ 的 row vectors $A(i,:)_{(1 \times n)}$ 打直後，也就是 $(A(i,:)^T)_{(n \times 1)}$ 和 $x_{(n\times 1)}$ 做 inner product:
$$y_i=(A(i,:)^T)_{(n \times 1)}\cdot x_{(n\times 1)}=A(i,:)x\tag{2}$$

inner product 其實是類似投影的概念，也就是對於原本的軸做旋轉和放大，這部分的概念可以回顧 https://hackmd.io/@cychiang-ntpu/ByFR-Os08#1-Linear-Transformation 。

在 eigen 觀念裡面，如果 $A$ 是一個 square matrix，則 $m=n$，我們可以找到 $n$ 個 eigenvectors $s_i\text{ for } i=1,2,...,n$ 使得以下條件成立：
$$A_{(n\times n)}{s_i}_{(n\times 1)}={s_i}_{(n\times 1)} {\lambda_i}_{(1\times 1)}\tag{3}$$

其中 ${\lambda_i}_{(1\times 1)} \text{ for }i=1,2,...,n$ 是 eigenvalues，把所有的 eigenvector 聚在一起變成：
$$A_{(n\times n)}S_{(n\times n)}=S_{(n\times n)}\Lambda_{(n\times n)}\tag{4}$$
其中：
$$S_{(n\times n)}=\left[
\begin{matrix}
s_1 & s_2 & ... & s_n
\end{matrix}
\right]\tag{5}$$

$$\Lambda_{(n\times n)}=\left[
\begin{matrix}
\lambda_1 & 0 & ... & 0 \\
0 & \lambda_2 & 0 & 0 \\
0 & 0 & \ddots & 0 \\
0 & 0 & ... & \lambda_n. \\
\end{matrix}
\right]\tag{6}$$

若要求取 $S$ 以及 $\Lambda$，就必須解：

$$A_{(n\times n)}{s_i}_{(n\times 1)}={\lambda_i}_{(1\times 1)}{s_i}_{(n\times 1)}={\lambda_i}_{(n\times 1)}I_{(n\times n)}{s_i}_{(n\times 1)}\tag{7}$$

$$(A_{(n\times n)}-{\lambda_i}_{(n\times 1)}I_{(n\times n)}){s_i}_{(n\times 1)}=0_{(n\times 1)}\tag{8}$$

因此我們要找到一個非 zero vector 的 $s_i$，讓式(8)成立，則 $P_{(n\times n)}=A_{(n\times n)}-{\lambda_i}_{(n\times 1)}I_{(n\times n)}$ 這個 square matrix 要是 singular，也就是 $rank(P)<n$ 或是 $|P|=0$，$|P|=0$ 的求取就是求 $\lambda_i$ 的 $n$-th order 的多項式解，會有 $n$ 個解，代表有 $n$ 個 eigenvalue。得到 $\lambda_i$ 之後，就可以求取 $Ps_i=0$ 的 null solution 即是 $n$ 個 eigenvectors。

因此我們可以將 $A$ 使用以下方法拆解 (decomposition) 表示：

$$AS=S\Lambda\tag{9}$$

或

$$A=S\Lambda S^{-1}\tag{10}$$

但如果 $A_{(m\times n)}$ 不是 square matrix ($m\neq n$)，則無法用數學式(10)表示，因為也無法利用數學式(8)來求解。

---

## B. Eigen for Non-Square Matrices

為了要能夠把 $A_{(m\times n)}$ 做拆解，我們在這裡可以先解釋一次數學式(9)的意義：向量 $s_i$ 和 $A$ 的 row vectors 內積之後，或是把 $s_i$ 做 linear transformation (rotation and scaling) 之後，會等於是將 $S$ 的 column vectors ($s_i$) 以 $\lambda_i$ 直接做放大。我們可以把這精神應用於 $A_{(m\times n)}$：

$$A_{(m\times n)}V_{(n\times n)}=U_{(m\times n)}\Sigma_{(n\times n)}\tag{11}$$

其中 $A_{(m\times n)}V_{(n\times n)}$ 代表將 $V$ 經過 $A$ 的 linear transformation 之後變成 $U$ 裡面 column vectors 以 $\Sigma$ 裡面的係數伸縮，我們希望 $V$、$U$、以及$\Sigma$ 有類似數學式(9)裡面的特性：
1. 希望數學式(11)裡面的 $V$ 和 $U$ 像是數學式(9)裡面的 $S$，而且最好是 $V_{(n\times n)}^TV_{(n\times n)}=I_{(n\times n)}$ 且 $(U^T)_{(n\times m)}U_{(m\times n)}=I_{(n\times n)}$，很像是如果數學式(9)裡面的 matrix $A$ 是 symmetric matrix 的話，根據 spectral theorem 的特性，也就是 $S^{-1}=S^T$。
2. 希望數學式(11)裡面的 $\Sigma$ 像數學式(9)右手邊的 $\Lambda$ 一樣，是 diagonal matrix。

所以 Singular Value Decomposition 的問題，就變成將 $A_{(m\times n)}$ 符合以下的數學式的問題：

$$A_{(m\times n)}V_{(n\times n)}=U_{(m\times n)}\Sigma_{(n\times n)}\tag{12}$$

其中
$$V_{(n\times n)}^TV_{(n\times n)}=I_{(n\times n)}\tag{13}$$

$$(U^T)_{(n\times m)}U_{(m\times n)}=I_{(n\times n)}\tag{14}$$

$$\Sigma_{(n\times n)}=\left[
\begin{matrix}
\sigma_1 & 0 & ... & 0 \\
0 & \sigma_2 & 0 & 0 \\
0 & 0 & \ddots & 0 \\
0 & 0 & ... & \sigma_n. \\
\end{matrix}
\right]\tag{15}$$

這樣子，數學式(12)的每一項都很像數學式(9)的形式和特性，很像把數學式(9)的 $S$ 找了兩個分身 $V_{(n\times n)}$ 以及 $U_{(m\times n)}$，注意 $V$ 和 $U$ 的 size 是不一樣的。根據數學式(13)的特性，因為 $V$ 是 square matrix，我們可以把數學式(12)的 $V$ 放到右手邊去變成：

$$\begin{multline*}
A_{(m\times n)}V_{(n\times n)}(V_{(n\times n)})^{-1}=
A_{(m\times n)}\\=U_{(m\times n)}\Sigma_{(n\times n)}(V_{(n\times n)})^{-1}=
U_{(m\times n)}\Sigma_{(n\times n)}(V_{(n\times n)})^{T}\tag{16}
\end{multline*}$$

把數學式(16)整理乾淨變成：

$$A_{(m\times n)}=U\Sigma V^T\tag{17}$$

知道 symmetric matrix 的 eigenvector 之間互相 orthogonal 的特性，就會像是數學式(13)和(14)的特性產生，所以我們已知道任何的 $A^TA$ 或是 $AA^T$ 都會是 symmetric matrix，並代入數學式(17)得：

$$A^TA=(U\Sigma V^T)^TU\Sigma V^T=V(\Sigma)^TU^TU\Sigma V^T\tag{18}$$

$$AA^T=U\Sigma V^T(U\Sigma V^T)^T=U\Sigma V^TV{\Sigma}^TU^T\tag{19}$$

假如數學式(18)和(19)裡面的 $U$ 和 $V$ 符合數學式(13)和(14)的特性，且因為 $\Sigma$ 是 diagonal，所以 $\Sigma^T=\Sigma$，則：

$$(A^TA)_{(n\times n)}=V_{(n\times n)}(\Sigma^2)_{(n\times n)}(V^T)_{(n\times n)}\tag{20}$$

$$(AA^T)_{(m\times m)}=U_{(m\times n)}(\Sigma^2)_{(n\times n)}(U^T)_{(n\times m)}\tag{21}$$

#### Key Points:
* 小心！！！數學式 (20)、(21) 中間夾的是 $\Sigma^2=\Sigma \Sigma$，就是 diagonal matrix $\Sigma$ 乘了兩次！
* 觀察數學式(20)，可以發現到，$V$ 的 column vectors 就是 matrix $A^TA$ 的 eigenvectors，$\Sigma^2$ 對角線上的值就是對應的 eigenvalue。
* 觀察數學式(21)，可以發現到，$U$ 的 column vectors 就是 matrix $AA^T$ 的 eigenvectors，$\Sigma^2$ 對角線上的值就是對應的 eigenvalue。
* $\Sigma$ 對角線上的值稱為 singular value，而 $\Sigma^2$ 對角線上的值是 $A^TA$ 以及 $AA^T$ 兩個 square matrix 的 eigenvalue，說到這裡不要迷向，別忘了你希望拆解 $A$ 變成 $A=U\Sigma V^T$。

## C. 觀察 $A^TA=V\Sigma^2 V^T$
1. 左手邊 $X_{(n\times n)}=A^TA$ 可以看成使用 $A^T$ 這個 matrix 對 $A$ 做 row operation，所以 $A$ 的 row space 和 $X$ 的 row space 是一樣的，也就是 $C(A^T)=C(X^T)$
2. 右手邊 $V\Sigma^2 V^T$ 是類似 $X=Q\Lambda Q^T$ 的形式，其實就是 symmetric matrix 做 eigen 分解的結果。也就是：
$$(A^TA)V=V\Sigma^2\tag{22}$$
對比於 eigen 分解：
$$XQ=Q\Lambda\tag{23}$$
3. 對照數學式(22)以及(23)，因為 $X=A^TA$ 是 symmetric matrix，可能為 positive definite 或 positive semidefinite，所以 $\Lambda=\Sigma^2$ 這個 matrix 裡面的 eigenvalue $\lambda_i=(\sigma_i)^2\geq0$，而 $V$ 裡面的 column vectors 就是 $\lambda_i$ 對應的 eigenvector $v_i$，也就是：
$$\begin{multline*}\left[
\begin{matrix}
a_1^Ta_1 & a_1^Ta_2 & ... & a_1^Ta_n \\
a_2^Ta_1 & a_2^Ta_2 & ... & a_2^Ta_n \\
\vdots & ... & \ddots & ... \\
a_n^Ta_1 & a_{n}^Ta_2 & ... & a_n^Ta_n \\
\end{matrix}
\right]\left[
\begin{matrix}
{v_1}_{(n\times 1)} & {v_2}_{(n\times 1)} & ... & {v_n}_{(n\times 1)}
\end{matrix}
\right]\\=\left[
\begin{matrix}
{v_1}_{(n\times 1)} & {v_2}_{(n\times 1)} & ... & {v_n}_{(n\times 1)}
\end{matrix}
\right]\left[
\begin{matrix}
\sigma_1^2 & 0 & ... & 0 \\
0 & \sigma_2^2 & 0 & 0 \\
0 & 0 & \ddots & 0 \\
0 & 0 & ... & \sigma_n^2. \\
\end{matrix}
\right]\end{multline*}\tag{24}$$
## D. 求得 $V$ 以及 $\Sigma^2$
4. 所以 $V$ 以及 $\Sigma^2$ 就是 symmetrixc $X_{(n\times n)}=A^TA$ 的 eigenvector matrix 以及 eigenvalue matrix
5. 若 $X=A^TA$ 是 positive semidefinite 的情況下，會有 eigenvalue $\lambda_i=(\sigma_i)^2=0$，代表 $X_{(n\times n)}{v_i}_{(n\times 1)}={v_i}_{(n\times 1)}0_{(1\times 1)}=0_{(n\times 1)}$，代表 $v_i$ 和 $X$ 的 vectors in row space (row vectors) 相互正交 (orthogonal)，所以其實 $v_i\in N(X)$，又因為 $C(A^T)=C(X^T)$，所以 $v_i\in N(A)$。而 $\lambda_j=(\sigma_j)^2>0$ 對應的 $v_j$，因為 $Xv_j\neq0_{(n\times 1)}$，也就是 $Av_j\neq0_{(n\times 1)}$，所以符合此條件的 $v_j\in C(A^T)$
6. 呼應前面第5點，因為 $C(A^T)=C(X^T)$，且 $N(A)=N(X)$，所以 $rank(A)=rank(X)=r$ 且 $r\leq m$ and $r\leq n$，或可以直接寫成 $rank(A)\leq\min(m, n)$
7. 接續前面第6點，$\dim C(A^T)=rank(A)=r$，$\dim N(A)=n-r$
8. $\dim C(X^T)=\dim C(A^T)=rank(A)=r$ 代表 $A$ 的 row space 有多少 basis vectors，而這些 row space 的 basis vectors 就是 eigenvalue $\sigma_i^2>0$ 對應的 eigenvectors $v_i$，如果有 eigenvalue 為 0，則 matrix $A$ 為 singular，討論 $\sigma_i^2$ 對於 $rank(A)=\dim C(A^T)$ 的影響等於是討論 $\sigma_i$ 對 $rank(A)=\dim C(A^T)$ 的影響，因此我們特別稱這個 $\sigma_i$ 為 Singular Value，當有 $\sigma_i=0$ 的時候，$A^TA$ 為 singular。
## E. 求得 $U$
9. 根據數學式(22)的 eigen 拆解得到 $\sigma_i^2 \text{ for }i=1,2,...,n$ 以及對應的 ${v_i}_{(n\times 1)} \text{ for }i=1,2,...,n$ 之後，將 $v_i$ 和 $\sigma_i$ 代入數學式(12)，可以得到 $U_{(m\times n)}$：
$$U_{(m\times n)}=(\Sigma^{-1})_{(n\times n)}A_{(m\times n)}V_{(n\times n)}\tag{25}$$
10. 數學式(25)有一個問題是，如果有 singular value $\sigma_i=0$，且 $r=rank(A)<n$，則 $\Sigma^{-1}$ 無法計算，此時回顧數學式(12)：
$$A_{(m\times n)}V_{(n\times n)}=U_{(m\times n)}\Sigma_{(n\times n)}\tag{12}$$
我們可以將 $\Sigma$ 裡面的 singular values 重新排序，讓 $\sigma_1\geq \sigma_2\geq \sigma_3...\geq \sigma_n$，然後原本相對應的 eigenvectors ${v_i}_{(n\times 1)}$ 也重新根據 singular value 的大小來排序，會發現到 $\sigma_{r+1}=0$,$\sigma_{r+2}=0$,...,$\sigma_n=0$，因此：
$$\begin{multline*}U_{(m\times n)}\Sigma_{(n\times n)}\\
=\left[
\begin{matrix}
{u_1}_{(m\times 1)} & {u_2}_{(m\times 1)} & ... & {u_r}_{(m\times 1)} & {u_{r+1}}_{(m\times 1)} & ... & {u_n}_{(m\times 1)}
\end{matrix}
\right]_{(m\times n)}\\\left[
\begin{matrix}
\sigma_1 & 0 & ... & 0 & 0 & ... & 0\\
0 & \sigma_2 & 0 & 0 & 0 & ... & 0\\
0 & 0 & \ddots & 0 & 0 & ... & 0\\
0 & 0 & ... & \sigma_{r} & 0 & ... & 0\\
0 & 0 & ... & 0 & \sigma_{r+1} & ... & 0\\
0 & 0 & ... & 0 & 0 & \ddots & 0\\
0 & 0 & ... & 0 & 0 & ... & \sigma_n
\end{matrix}
\right]_{(n\times n)}\\
=\left[
\begin{matrix}
{u_1}_{(m\times 1)} & {u_2}_{(m\times 1)} & ... & {u_r}_{(m\times 1)}
\end{matrix}
\right]_{(m\times r)}\\\left[
\begin{matrix}
\sigma_1 & 0 & ... & 0 & 0 & ... & 0\\
0 & \sigma_2 & 0 & 0 & 0 & ... & 0\\
0 & 0 & \ddots & 0 & 0 & ... & 0\\
0 & 0 & ... & \sigma_{r} & 0 & ... & 0
\end{matrix}
\right]_{(r\times n)}\end{multline*}\tag{26}$$
11. 續上面第10點，可以令：
$$A_{(m\times n)}V_{(n\times n)}=\hat{U}_{(m\times r)}\hat{\Sigma}_{(r\times n)}\tag{27}$$
其中：
$$\hat{U}_{(m\times r)}=\left[
\begin{matrix}
{u_1}_{(m\times 1)} & {u_2}_{(m\times 1)} & ... & {u_r}_{(m\times 1)}
\end{matrix}
\right]_{(m\times r)}\tag{28}$$
$$\hat{\Sigma}_{(r\times n)}=\left[
\begin{matrix}
\sigma_1 & 0 & ... & 0 & 0 & ... & 0\\
0 & \sigma_2 & 0 & 0 & 0 & ... & 0\\
0 & 0 & \ddots & 0 & 0 & ... & 0\\
0 & 0 & ... & \sigma_{r} & 0 & ... & 0
\end{matrix}
\right]_{(r\times n)}\tag{29}$$
**要很小心 $V$ 的 column 排列順序是根據 eigenvalue 的排序排好的！ ${v_i}_{(n\times 1)} \text{ for }i=1,2,...r \in C(A^T)$ 而 ${v_i}_{(n\times 1)} \text{ for }i=r+1,r+2,...n \in N(A)$**
將數學式(27)以每一個 column vector 來寫可得：
$$A_{(m\times n)}{v_j}_{(n\times 1)}=\sigma_j{u_j}_{(m\times 1)}\text{ for }j=1,2,...,r\tag{30}$$
所以最後 $\hat{U}_{(m\times r)}$ 的 $r$ 個 column vector 是：
$${u_j}_{(m\times 1)}=\frac{1}{\sigma_j}A_{(m\times n)}{v_j}_{(n\times 1)}\text{ for }j=1,2,...,r\tag{31}$$

## F. Singular Value Decomposition (SVD) in Brief
由上面的推導，得知 $A_{(m\times n)}$ 可以拆解為：
$$A_{(m\times n)}=U_{(m\times r)}\Sigma_{(r\times r)}(V_{n\times r})^T\tag{32}$$
其中：
$$r=rank(A)\tag{33}\leq\min(m,n)$$
$$V^TV=I_{(n\times n)}\tag{34}$$
$$U^TU=I_{(r\times r)}\tag{35}$$
$V$ 的 column vectors 是 matrix $A^TA$ 的 eigenvectors；$\Sigma$ 對角線的值為 $V$ 裡面 eigenvector 對應的 singular value；先求得 $\Sigma$，便可求得 $V$，最後得到 $U$。
## G. 觀察 $AA^T=U\Sigma^2 U^T$
12. 觀察 $AA^T=U\Sigma^2 U^T$ 和 觀察 $A^TA=V\Sigma^2 V^T$ 的方法是相似的。
13. 左手邊 $Y_{(m\times m)}=AA^T$ 可以看成使用 $A^T$ 這個 matrix 對 $A$ 做 column operation，所以 $A$ 的 column space 和 $Y$ 的 column space 是一樣的，也就是 $C(A)=C(Y)$
14. 右手邊 $U\Sigma^2 U^T$ 是類似 $Y=Q\Lambda Q^T$ 的形式，其實就是 symmetric matrix 做 eigen 分解的結果。也就是：
$$(AA^T)_{(m\times m)}U_{(m\times m)}=U_{(m\times m)}{\Sigma^2}_{(m\times m)}\tag{36}$$
要小心這裡的 $U$ 和 $\Sigma$ 的 size 和分析 $A^TA$ 的時候的 $U$ 和 $\Sigma$ 不一樣了。
15. 因為 $Y=AA^T$ 是 symmetric matrix，可能為 positive definite 或 positive semidefinite，所以 $\Lambda=\Sigma^2$ 這個 matrix 裡面的 eigenvalue $\lambda_i=(\sigma_i)^2\geq0$，而 $U$ 裡面的 column vectors 就是 $\lambda_i$ 對應的 eigenvector $u_i$，也就是：
$$\begin{multline*}\left[
\begin{matrix}
AA^T
\end{matrix}
\right]_{(m\times m)}\left[
\begin{matrix}
{u_1}_{(m\times 1)} & {u_2}_{(m\times 1)} & ... & {u_m}_{(m\times 1)}
\end{matrix}
\right]\\=\left[
\begin{matrix}
{u_1}_{(m\times 1)} & {u_2}_{(m\times 1)} & ... & {u_m}_{(m\times 1)}
\end{matrix}
\right]\left[
\begin{matrix}
\sigma_1^2 & 0 & ... & 0 \\
0 & \sigma_2^2 & 0 & 0 \\
0 & 0 & \ddots & 0 \\
0 & 0 & ... & \sigma_m^2 \\
\end{matrix}
\right]\end{multline*}\tag{37}$$
16. 所以 $U$ 以及 $\Sigma^2$ 就是 symmetrixc $Y_{(m\times m)}=AA^T$ 的 eigenvector matrix 以及 eigenvalue matrix
17. 若 $Y=AA^T$ 是 positive semidefinite 的情況下，會有 eigenvalue $\lambda_i=(\sigma_i)^2=0$，代表 $Y_{(m\times m)}{u_i}_{(m\times 1)}={u_i}_{(m\times 1)}0_{(1\times 1)}=0_{(m\times 1)}$，代表 $u_i$ 和 $Y$ 的 vectors in row space (row vectors) 相互正交 (orthogonal)，又知道 $Y$ 就是 $A^T$ 的 row vectors 以 $A$ 做 row operation，所以
$$Y_{(m\times m)}{u_i}_{(m\times 1)}=AA^T{u_i}_{(m\times 1)}=A0_{m\times 1}=0_{(m\times 1)}\tag{38}$$
其實就是：
$$A^Tu_i=0\tag{39}$$
$u_i\in N(A^T)$，代表 singular value 為零對應到的 eigenvector $u_i$ 是 $A$ 的 left nullspace 之 basis vector，而 $\lambda_j=(\sigma_j)^2>0$ 對應的 $u_j$，因為 $Yu_j\neq0_{(m\times 1)}$，也就是 $A^Tu_j\neq0_{(m\times 1)}$，所以符合此條件的 $u_j\in C(A)$
18. 呼應前面第5點和第17點，因為 $C(A)=C(Y)$，且 $N(A^T)=N(Y^T)$，所以 $rank(A)=rank(Y)=r$ 且 $r\leq m$ and $r\leq n$，或可以直接寫成 $rank(A)\leq\min(m, n)$
7. 接續前面，$\dim C(A)=\dim C(A^T)=rank(A)=r$，$\dim N(A)=n-r$，$\dim N(A^T)=m-r$
19. $\dim C(Y)=\dim C(A)=rank(A)=r$ 代表 $A$ 的 column space 有多少 basis vectors，而這些 column space 的 basis vectors 就是 eigenvalue $\sigma_i^2>0$ 對應的 eigenvectors $u_i$，如果有 eigenvalue 為 0，則 matrix $A$ 為 singular，討論 $\sigma_i^2$ 對於 $rank(A)=\dim C(A)$ 的影響等於是討論 $\sigma_i$ 對 $rank(A)=\dim C(A)$ 的影響，因此我們特別稱這個 $\sigma_i$ 為 Singular Value，當有 $\sigma_i=0$ 的時候，$AA^T$ 為 singular。

## H. The Four Subspace and Singular Value Decomposition
當我們把 $A_{(m\times n)}$ 寫成 SVD 形式：
$$A_{(m\times n)}=U_{(m\times r)}\Sigma_{(r\times r)}(V_{n\times r})^T\tag{40}$$
由前面討論得到：
1. 若 $rank(A)=r$，當然 $r\leq \min(m,n)$，則 $V_{(n\times r)}$ 是 symmetric matrix $(A^TA)_{(n\times n)}$ $r$ 個非 0 的 singular value 對應的 eigenvectors。
2. 習慣上，我們會把 singular value 取正的值，相對應的 $v_i$ 也要有相對的正負符號處理，然後將 $\Sigma$ 裡面的值由大排至小，也就是 $\sigma_1\geq \sigma_2\geq \sigma_3...\geq \sigma_r$，越大的 singular value，其對應的 eigenvector 就越重要。
3. 續，$U_{(m\times r)}$ 是 symmetric matrix $(AA^T)_{(m\times m)}$ $r$ 個非 0 的 singular value 對應的 eigenvectors。
4. $A^TA$ 和 $AA^T$ 求得的非零的 eigenvalues 是一樣的。
5. $U_{(m\times r)}$ 裡面的 $r$ 個 column vectors 是 $C(A)$/column space 的 orthonormal basis vectors。
6. $V_{(n\times r)}$ 的 column vectors 是 $C(A^T)$/row space 的 $r$ 個 orthonormal basis vectors。
7. 因為 $\Sigma$ 是 diagonal matrix，SVD 的原本數學式 (40) 也可以寫成 $r$ 個 rank-one matrices 的線性組合，而線性組合的係數就是 singular values：
$$A_{(m\times n)}=\sum_{k=1}^{r}\sigma_k(u_k)_{(m\times 1)}(v_k^T)_{(1\times n)}\tag{41}$$
為什麼是 rank-one？因為 ${M_k}_{(m\times n)}=u_kv_k^T$ 就是把 $u_k$ 這個 basis vector 用 $v_k$ 裡面的係數 scaling 擴展成一個 $m\times n$ 的 matrix，這個 $M_k$ 的 column vectors 都是 $u_k$ 的 linear combination。
8. 我們可以用 $K<r$ 個 column space vectors($u_k$) 以及 row space vectors ($v_k$) 來逼近原本的 $A_{(m\times n)}$：
$$\hat{A}_{(m\times n)}=\sum_{k=1}^{K}\sigma_k(u_k)_{(m\times 1)}(v_k^T)_{(1\times n)}\tag{42}$$
如此在 $rank(\hat{A})=K<r$ 的情況下，$\hat{A}=\sum_{k=1}^{K}\sigma_ku_kv_k^T$ 與 rank 為 $r$ 的 $A$ 有最小的誤差！

## I. Relationship between outer product and SVD
Please read the document: https://drive.google.com/file/d/1ydxDBt-XhKQ0Ah9GDAP2WY08M8I0ILS3/view?usp=sharing

## Old Homework-8

$$A=\left[
\begin{matrix}
2 & 1 & 2\\
2 & 0 & 2\\
-2 & 0 & -2\\
-2 & 1 & -2
\end{matrix}
\right]$$

### Problem 8-1 (10 points)
求取 $rank(A)$

Solution:

### Problem 8-2 (30 points)
將 $A$ 以 SVD 拆解成：
$$A=U\Sigma V^T$$

Solution:

### Problem 8-3 (40 points)
請用求取 SVD 的計算過程 (求 $A^TA$ 和 $AA^T$ 的 eigen) 來求取 $C(A)$、$N(A^T)$、$C(A^T)$、以及 $N(A)$ 這 four subspaces 的 orthonormal basis vectors

注意！
1. 用間單的 row operation 做 forward elimination 得到 row echelon form ($U$)，或是再做 backward elimination 得到 reduced row echelon form ($R$)，non-zero row vectors 就是 $C(A^T)$ 的一組 basis，但是這個 basis 裡面的 basis vectors 互相不見得 orthogonal or orthonormal，因為 elimination 過程並沒有像 QR decomposition 使用 Gram–Schmidt process 保證每一個 basis vector 之間要 orthogonal。
2. Gram–Schmidt process 可以求到 orthonormal 的 basis vectors，但不見得是 matrix A 的 eigenvector。
3. 求取 $A^TA$ 的 eigenvectors，因為 symmetrix matrix 的特性，得到的 eigenvectors 會互相 orthogonal，且剛剛可以是 $A$ 的 row space 之 basis vectors。
4. 求取 $AA^T$ 的 eigenvectors，因為 symmetrix matrix 的特性，得到的 eigenvectors 會互相 orthogonal，且剛剛可以是 $A$ 的 column space 之 basis vectors。
5. 所以 $A$ 的 The Four Subspace 的 basis 有很多組，他們都可以表示 (span出/linear combination) The Four Subspace，只是我們也可以 "選" 幾組 basis 符合 basis vectors 之間 orthogonal 或甚至 orthonormal，注意喔！是 “選”，所以代表是有很多組 basis 都可以是某個 subspace 的基底。
6. QR Decomposition 或是 SVD 的過程來得到 basis vectors for the Four Subspace 會有 orthogonal/orthonormal 的特性。
7. 本題請用 SVD 來做。

Solution:

### Problem 8-4 (20 points)
求取一個 $\hat{A}$ 使得 $rank(\hat{A})=1$ 且 $\hat{A}$ 與 $A$ 誤差最小。

Solution:


---

## Assignment 5 (Due: 2023/6/22)

$$A=\left[
\begin{matrix}
\frac{3}{2} & \frac{-1}{2} & 1\\
0 & 0 & 0\\
\frac{-1}{2} & \frac{3}{2} & 1\\
0 & 0 & 0
\end{matrix}
\right]$$

### Problem 1 (10 points)
求取 $rank(A)$


### Problem 2 (30 points)
將 $A$ 以 SVD 拆解成：
$$A=U\Sigma V^T$$


### Problem 3 (40 points)
請用求取 SVD 的計算過程 (求 $A^TA$ 和 $AA^T$ 的 eigen) 來求取 $C(A)$、$N(A^T)$、$C(A^T)$、以及 $N(A)$ 這 four subspaces 的 orthonormal basis vectors


### Problem 4 (20 points)
求取一個 $\hat{A}$ 使得 $rank(\hat{A})=1$ 且 $\hat{A}$ 與 $A$ 誤差最小。