以下内容來自劉建平Pinard-部落格園的學習筆記
介紹
奇異值分解(Singular Value Decomposition，以下簡稱SVD)是在機器學習領域廣泛應用的算法，它不光可以用于降維算法中的特征分解，還可以用于推薦系統，以及自然語言處理等領域。是很多機器學習算法的基石。本文就對SVD的原理做一個總結，并讨論在在PCA降維算法中是如何運用運用SVD的。
特征值和特征向量
首先回顧下特征值和特征向量的定義如下：
A x = λ x Ax = \lambda x Ax=λx
其中 A是一個n×n矩陣， x 是一個 n 維向量，則 λ \lambda λ是矩陣 A 的一個特征值，而 x是矩陣A的特征值 λ \lambda λ所對應的特征向量。
求出特征值和特征向量有什麼好處呢？ 就是我們可以将矩陣A特征分解。如果我們求出了矩陣A的n個特征值λ1≤λ2≤…≤λn,以及這n個特征值所對應的特征向量{w1,w2,…wn}，，如果這n個特征向量線性無關，那麼矩陣A就可以用下式的特征分解表示：
A = W ∑ W − 1 A = W\sum W^{-1} A=W∑W−1
其中W是這n個特征向量所張成的n×n維矩陣，而Σ為這n個特征值為主對角線的n×n維矩陣。
一般我們會把W的這n個特征向量标準化，即滿足||wi||2=1, 或者說 w i T w i = 1 w^T_iw_i=1 wiTwi=1，此時W的n個特征向量為标準正交基，滿足 W T W = I W^TW=I WTW=I，即 W T = W − 1 W^T=W^{-1} WT=W−1, 也就是說W為酉矩陣
這樣我們的特征分解表達式可以寫成：
A = W ∑ W T A = W\sum W^T A=W∑WT
注意到要進行特征分解，矩陣A必須為方陣。那麼如果A不是方陣，即行和列不相同時，我們還可以對矩陣進行分解嗎？答案是可以，此時我們的SVD登場了。
SVD的定義
SVD也是對矩陣進行分解，但是和特征分解不同，SVD并不要求要分解的矩陣為方陣。假設我們的矩陣A是一個m×n的矩陣，那麼我們定義矩陣A的SVD為：
A = U ∑ V T A = U\sum V^T A=U∑VT
其中U是一個m×m的矩陣，Σ是一個m×n的矩陣，除了主對角線上的元素以外全為0，主對角線上的每個元素都稱為奇異值，V是一個n×n的矩陣。U和V都是酉矩陣，即滿足 U T U = I , V T V = I U^TU=I,V^TV=I UTU=I,VTV=I。下圖可以很形象的看出上面SVD的定義：
那麼我們如何求出SVD分解後的U,Σ,V這三個矩陣呢？
如果我們将A的轉置和A做矩陣乘法，那麼會得到n×n的一個方陣ATA。既然ATA是方陣，那麼我們就可以進行特征分解，得到的特征值和特征向量滿足下式：
( A T A ) v i = λ i v i (A^TA)v_i = \lambda_iv_i (ATA)vi=λivi
這樣我們就可以得到矩陣 A T A A^TA ATA的n個特征值和對應的n個特征向量v了。将 A T A A^TA ATA的所有特征向量張成一個n×n的矩陣V，就是我們SVD公式裡面的V矩陣了。一般我們将V中的每個特征向量叫做A的右奇異向量。
如果我們将A和A的轉置做矩陣乘法，那麼會得到m×m的一個方陣 A A T AA^T AAT。既然 A A T AA^T AAT是方陣，那麼我們就可以進行特征分解，得到的特征值和特征向量滿足下式：
( A A T ) u i = λ i u i (AA^T)u_i = \lambda_iu_i (AAT)ui=λiui
這樣我們就可以得到矩陣 A A T AA^T AAT的m個特征值和對應的m個特征向量u了。将 A A T AA^T AAT的所有特征向量張成一個m×m的矩陣U，就是我們SVD公式裡面的U矩陣了。一般我們将U中的每個特征向量叫做A的左奇異向量。
U和V我們都求出來了，現在就剩下奇異值矩陣Σ沒有求出了。由于Σ除了對角線上是奇異值其他位置都是0，那我們隻需要求出每個奇異值σ就可以了。
我們注意到:
A = U Σ V T ⇒ A T = V Σ T U T ⇒ A T A = V Σ T U T U Σ V T = V Σ 2 V T A=UΣ^VT⇒AT=VΣ^TU^T⇒A^TA=VΣ^TU^TUΣV^T=VΣ^2V^T A=UΣVT⇒AT=VΣTUT⇒ATA=VΣTUTUΣVT=VΣ2VT
上式證明使用了: U T U = I U^TU=I UTU=I, Σ T Σ = Σ 2 Σ^TΣ=Σ^2 ΣTΣ=Σ2。可以看出 A T A A^TA ATA的特征向量組成的的确就是我們SVD中的V矩陣。類似的方法可以得到 A A T AA^T AAT的特征向量組成的就是我們SVD中的U矩陣。
進一步我們還可以看出我們的特征值矩陣等于奇異值矩陣的平方，也就是說特征值和奇異值滿足如下關系：
σ i = λ i σ_i=\sqrt{\lambda_i} σi=λi
這樣也就是說，我們可以不用 σ i = A v i u i σ_i=\frac{Av_i}{u_i} σi=uiAvi來計算奇異值，也可以通過求出 A T A A^TA ATA的特征值取平方根來求奇異值。
SVD計算舉例
這裡我們用一個簡單的例子來說明矩陣是如何進行奇異值分解的。我們的矩陣A定義為：
X = { 0 1 1 1 1 0 } X = \left\{\begin{matrix} 0 & 1\\ 1 & 1 \\ 1 & 0 \end{matrix} \right\} X=⎩⎨⎧011110⎭⎬⎫
我們首先求出 A A T AA^T AAT和 A T A A^TA ATA
A A T = { 0 1 1 1 1 0 } { 0 1 1 1 1 0 } { 1 1 0 1 2 1 0 1 1 } AA^T = \left\{\begin{matrix} 0 & 1\\ 1 & 1 \\ 1 & 0 \end{matrix} \right\} \left\{\begin{matrix} 0 & 1 & 1 \\ 1&1&0 \end{matrix} \right\} \left\{\begin{matrix} 1&1&0\\ 1&2&1\\ 0&1&1 \end{matrix} \right\} AAT=⎩⎨⎧011110⎭⎬⎫{011110}⎩⎨⎧110121011⎭⎬⎫
A T A = { 0 1 1 1 1 0 } { 0 1 1 1 1 0 } { 2 1 1 2 } A^TA = \left\{\begin{matrix} 0 & 1 & 1 \\ 1&1&0 \end{matrix} \right\} \left\{\begin{matrix} 0 & 1\\ 1 & 1 \\ 1 & 0 \end{matrix} \right\} \left\{\begin{matrix} 2&1\\ 1&2\\ \end{matrix} \right\} ATA={011110}⎩⎨⎧011110⎭⎬⎫{2112}
接着求 A A T AA^T AAT的特征值和特征向量：
進而求出 A T A A^TA ATA的特征值和特征向量：
利用 A v i = σ i u i Av_i=σ_iu_i Avi=σiui,i=1,2求奇異值：
當然，我們也可以用 σ i = λ i σ_i=\sqrt{\lambda_i} σi=λi
直接求出奇異值為 3 \sqrt{3} 3
和1.
最終得到A的奇異值分解為：
SVD的一些性質
上面幾節我們對SVD的定義和計算做了詳細的描述，似乎看不出我們費這麼大的力氣做SVD有什麼好處。那麼SVD有什麼重要的性質值得我們注意呢？
對于奇異值,它跟我們特征分解中的特征值類似，在奇異值矩陣中也是按照從大到小排列，而且奇異值的減少特别的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上的比例。也就是說，我們也可以用最大的k個的奇異值和對應的左右奇異向量來近似描述矩陣。也就是說：
A m × n = U m × m Σ m × n V n × n T ≈ U m × k Σ k × k V k × n T A_{m×n}=U_{m×m}Σ_{m×n}V^T_{n×n}≈U_{m×k}Σ_{k×k}V^T_{k×n} Am×n=Um×mΣm×nVn×nT≈Um×kΣk×kVk×nT
其中k要比n小很多，也就是一個大的矩陣A可以用三個小的矩陣 U m × k , Σ k × k , V k × n T U_{m×k},Σ_{k×k},V^T_{k×n} Um×k,Σk×k,Vk×nT來表示。如下圖所示，現在我們的矩陣A隻需要灰色的部分的三個小矩陣就可以近似描述了。
由于這個重要的性質，SVD可以用于PCA降維，來做資料壓縮和去噪。也可以用于推薦算法，将使用者和喜好對應的矩陣做特征分解，進而得到隐含的使用者需求來做推薦。同時也可以用于NLP中的算法，比如潛在語義索引（LSI）。下面我們就對SVD用于PCA降維做一個介紹。
SVD用于PCA
在主成分分析（PCA）原理總結中，我們講到要用PCA降維，需要找到樣本協方差矩陣 X T X X^TX XTX的最大的d個特征向量，然後用這最大的d個特征向量張成的矩陣來做低維投影降維。可以看出，在這個過程中需要先求出協方差矩陣 X T X X^TX XTX，當樣本數多樣本特征數也多的時候，這個計算量是很大的。
注意到我們的SVD也可以得到協方差矩陣 X T X X^TX XTX最大的d個特征向量張成的矩陣，但是SVD有個好處，有一些SVD的實作算法可以不求先求出協方差矩陣 X T X X^TX XTX，也能求出我們的右奇異矩陣V。也就是說，我們的PCA算法可以不用做特征分解，而是做SVD來完成。這個方法在樣本量很大的時候很有效。實際上，scikit-learn的PCA算法的背後真正的實作就是用的SVD，而不是我們我們認為的暴力特征分解。
另一方面，注意到PCA僅僅使用了我們SVD的右奇異矩陣，沒有使用左奇異矩陣，那麼左奇異矩陣有什麼用呢？
假設我們的樣本是m×n的矩陣X，如果我們通過SVD找到了矩陣 X X T XX^T XXT最大的d個特征向量張成的m×d維矩陣U，則我們如果進行如下處理：
X ′ d × n = U d × m T X m × n X′_{d×n}=U^T_{d×m}X_{m×n} X′d×n=Ud×mTXm×n
可以得到一個d×n的矩陣X‘,這個矩陣和我們原來的m×n維樣本矩陣X相比，行數從m減到了d，可見對行數進行了壓縮。也就是說，左奇異矩陣可以用于行數的壓縮。相對的，右奇異矩陣可以用于列數即特征次元的壓縮，也就是我們的PCA降維。
SVD小結
SVD作為一個很基本的算法，在很多機器學習算法中都有它的身影，特别是在現在的大資料時代，由于SVD可以實作并行化，是以更是大展身手。SVD的原理不難，隻要有基本的線性代數知識就可以了解，實作也很簡單是以值得仔細的研究。當然，SVD的缺點是分解出的矩陣解釋性往往不強，有點黑盒子的味道，不過這不影響它的使用。