# 李宏毅_Linear Algebra Lecture 36: Singular Value Decomposition
###### tags: `Hung-yi Lee` `NTU` `Linear Algebra Lecture`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW)
## Linear Algebra Lecture 36: Singular Value Decomposition
[課程連結](https://www.youtube.com/watch?v=OEJ0wxxLO7M&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=37)

### Outline

先前課程提過對稱矩陣一定可以被對角化，其它的方形矩陣就不一定，而Singular Value Decomposition神奇的是，每一個矩陣，就算不是方形的，它都有Singular Value Decomposition。

### SVD

任何的矩陣_$A$，它都可以被拆成$U, \Sigma, V^T$
* $U, V^T$的columns都是Orthonormal Set(Independent)
* $\Sigma$是Diagonal Matrix
* 它可能不是方形的，但總之就是只有對角線的地方有值，值也可以是0
* 而且一定都是非負值，舉例來說，$\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{bmatrix}$
* 左上到右下的值是由大到小的排序

值得注意的是，如果對角線有$k$個非0的值，那$\Sigma$的Rank就會是$k$，那$A$的Rank呢?它左右還乘上$U, V^T$：
* 根據定理，兩個矩陣A(mxn)、B(nxk)相乘，其相乘之後的Rank會小於等於原本兩個矩陣中較小的那個Rank，因此我們先知道，$A$的Rank會小於等於$k$
* 如果B的Rank=n，那兩個矩陣相乘之後的Rank會是Rank(A)，因為$V^T$是Independent，因此$\Sigma$乘上$V^T$並不會改變Rank
* 如果A的Rank=n，那兩個矩陣相乘之後的Rank會是Rank(B)，因為$U$是Independent，因此$\Sigma$乘上$U$並不會改變Rank

從上面可以知道，只要知道$\Sigma$有多少非0的數值，就可以知道$A$的rank是多少。

### SVD

將$\Sigma$中全0的部份蓋掉，這樣我們就得到一個kxk的matrix(因為對角線有k個非0值)，假設為$\Sigma '$，$U, V^T$也一樣，也就是$U$只取k個columns、$V^T$取前k個rows，得到$U_1, V_1^T$，神奇的是，$U_1 \Sigma ' V_1^T$得到的結果還會是$A$。這可以拿來做為矩陣的壓縮，後續會有說明。

(推論的部份寫在黑板)

### SVD

如果今天蓋掉的不是單純的0的部份，而是超過了，蓋掉非0值的部份，那整個結果就不再相等。不過有一個很有趣的特性，這時候$A'$的Rank已經是$k-1$，而且$A'$是所有Rank為$k-1$的矩陣中，最接近$A$的那一個，也就是兩個inner product之後的值最小。

### Low rank approximation using the singular value decomposition

SVD可以拿來做一張圖片的壓縮，左圖減中圖等於右圖，這取決於你k的設置。

[影片](https://www.youtube.com/watch?v=pAiVb7gWUrM)可以看出不同k設置的變化，我們可以看到，k到一個值之後的變化已經不大。