李宏毅_Linear Algebra Lecture 36: Singular Value Decomposition

tags: Hung-yi Lee NTU Linear Algebra Lecture

課程撥放清單

Linear Algebra Lecture 36: Singular Value Decomposition

課程連結

Outline

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

SVD

任何的矩陣_

$A$，它都可以被拆成

$U,\mathrm{\Sigma },V^T$

• $U,V^T$的columns都是Orthonormal Set(Independent)
• $\mathrm{\Sigma }$是Diagonal Matrix
  • 它可能不是方形的，但總之就是只有對角線的地方有值，值也可以是0
  • 而且一定都是非負值，舉例來說，
    $\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]$
  • 左上到右下的值是由大到小的排序

值得注意的是，如果對角線有

$k$個非0的值，那

$\mathrm{\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，因此
  $\mathrm{\Sigma }$乘上
  $V^T$並不會改變Rank
• 如果A的Rank=n，那兩個矩陣相乘之後的Rank會是Rank(B)，因為
  $U$是Independent，因此
  $\mathrm{\Sigma }$乘上
  $U$並不會改變Rank

從上面可以知道，只要知道

$\mathrm{\Sigma }$有多少非0的數值，就可以知道

$A$的rank是多少。

SVD

將

$\mathrm{\Sigma }$中全0的部份蓋掉，這樣我們就得到一個kxk的matrix(因為對角線有k個非0值)，假設為

${\mathrm{\Sigma }}^{\prime }$，

$U,V^T$也一樣，也就是

$U$只取k個columns、

$V^T$取前k個rows，得到

$U_1,V_1^T$，神奇的是，

$U_1{\mathrm{\Sigma }}^{\prime }{V}_1^T$得到的結果還會是

$A$。這可以拿來做為矩陣的壓縮，後續會有說明。

(推論的部份寫在黑板)

SVD

如果今天蓋掉的不是單純的0的部份，而是超過了，蓋掉非0值的部份，那整個結果就不再相等。不過有一個很有趣的特性，這時候

$A^{\prime }$的Rank已經是

$k-1$，而且

$A^{\prime }$是所有Rank為

$k-1$的矩陣中，最接近

$A$的那一個，也就是兩個inner product之後的值最小。

Low rank approximation using the singular value decomposition

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

影片可以看出不同k設置的變化，我們可以看到，k到一個值之後的變化已經不大。