SVD：Single Value Decomposition

08-24

來自專欄文明之光

奇異值分解（Single Value Decomposition，簡稱SVD），是線性代數中另一種非常重要的矩陣分解演算法（還有一個是特徵值分解，但特徵值分解只適用於n階方陣，並且不是所有的n階方陣都存在特徵分解，而SVD的應用更廣，它適用於任意給定的 $m imes n$ 階實數矩陣A。）除了適用於降維，SVD還能用於很多機器學習的工程領域，如推薦系統、文本主題相關性。圖1.1展示了SVD的分解樣例。

1.1 SVD分解樣例

形式化來說，設矩陣 $Ain R^{m imes n} 、Uin R^{m imes m} 、Sigmain R^{m imes n} 、Vin R^{n imes n}$ ，則矩陣A可以分解為下面的形式：

$A = USigma V^{T}$

其中， $U = left{ {u^{1},u^{2},...,u^{m}} ight}$ 是一個m階方陣， $u^{i}$ 的值矩陣 $AA^{T}$ 的第i大的特徵值對應的特徵向量。 $u^{i}$ 也是稱為矩陣A的左奇異向量。

$V = left{ {v^{1},v^{2},...,v^{n}} ight}$ 是一個n階方陣， $v^{i}$ 的值矩陣 $A^{T}A$ 的第i大的特徵值對應的特徵向量。 $v^{i}$ 也是稱為矩陣A的右奇異向量。

$Sigma$ 是一個對角矩陣，但要注意的是 $Sigma$ 不一定是方陣， $Sigma in R^{m imes n}$ ,設其對角線元素為 $（sigma _{1},sigma _{2},...,sigma _{k}）$ ，其中 $sigma _{i}$ 是矩陣 $A^{T}A$ 的第i大的特徵值的平方根，記為 $sigma _{i} = sqrt{lambda_{i}(A^{T}A)}$ 。

在很多情況下，不需要使分解的結果 $USigma V^{T}$ 準確性還原矩陣A，只需要接近於A即可。

事實上，奇異值 $sigma$ 與特徵值的性質相似，在矩陣 $Sigma$ 中也是從大到小排列，而且 $sigma$ 的值減少特別快，在很多情況下，前10%甚至1%的奇異值的和就佔了全部的奇異值之和的99%以上了。也就是說，可以用前r大的奇異值來近似描述矩陣，因此可以將公式轉化為：

$A approx USigma V^{T}$

其中， $Uin R^{m imes r} 、Sigmain R^{r imes r} 、Vin R^{r imes n}$ ,一般情況下r的值要遠遠小於m值和n值，因此 $m imes r+r imes r+r imes n$ 要遠遠小於 $m imes n$ 。我們只需要保存 $U$ 、 $Sigma$ 和 $V$ 這3個小矩陣就能還原矩陣A。