奇異值分解(SVD)原理詳解及推導

在網上看到有很多文章介紹SVD的，講的也都不錯，但是感覺還是有需要補充的，特別是關于矩陣和映射之間的對應關系。前段時間看了國外的一篇文章，叫A Singularly Valuable Decomposition The SVD of a Matrix，覺得分析的特別好，把矩陣和空間關系對應了起來。本文就參考了該文并結合矩陣的相關知識把SVD原理梳理一下。

SVD不僅是一個數學問題，在工程應用中的很多地方都有它的身影，比如前面講的PCA，掌握了SVD原理后再去看PCA那是相當簡單的，在推薦系統方面，SVD更是名聲大噪，將它應用于推薦系統的是Netflix大獎的獲得者Koren，可以在Google上找到他寫的文章；用SVD可以很容易得到任意矩陣的滿秩分解，用滿秩分解可以對數據做壓縮?？梢杂?a href='/map/svd/' style='color:#000;font-size:inherit;'>SVD來證明對任意M*N的矩陣均存在如下分解：

這個可以應用在數據降維壓縮上！在數據相關性特別大的情況下存儲X和Y矩陣比存儲A矩陣占用空間更??！

在開始講解SVD之前，先補充一點矩陣代數的相關知識。

正交矩陣

正交矩陣是在歐幾里得空間里的叫法，在酉空間里叫酉矩陣，一個正交矩陣對應的變換叫正交變換，這個變換的特點是不改變向量的尺寸和向量間的夾角，那么它到底是個什么樣的變換呢？看下面這張圖

假設二維空間中的一個向量OA，它在標準坐標系也即e1、e2表示的坐標是中表示為(a,b)'（用'表示轉置），現在把它用另一組坐標e1'、e2'表示為(a',b')'，存在矩陣U使得(a',b')'=U(a,b)'，則U即為正交矩陣。從圖中可以看到，正交變換只是將變換向量用另一組正交基表示，在這個過程中并沒有對向量做拉伸，也不改變向量的空間位置，加入對兩個向量同時做正交變換，那么變換前后這兩個向量的夾角顯然不會改變。上面的例子只是正交變換的一個方面，即旋轉變換，可以把e1'、e2'坐標系看做是e1、e2坐標系經過旋轉某個斯塔角度得到，怎么樣得到該旋轉矩陣U呢？如下

正交陣U行（列）向量之間都是單位正交向量。上面求得的是一個旋轉矩陣，它對向量做旋轉變換！也許你會有疑問：剛才不是說向量空間位置不變嗎？怎么現在又說它被旋轉了？對的，這兩個并沒有沖突，說空間位置不變是絕對的，但是坐標是相對的，加入你站在e1上看OA，隨著e1旋轉到e1'，看OA的位置就會改變。如下圖：

如圖，如果我選擇了e1'、e2'作為新的標準坐標系，那么在新坐標系中OA（原標準坐標系的表示）就變成了OA'，這樣看來就好像坐標系不動，把OA往順時針方向旋轉了“斯塔”角度，這個操作實現起來很簡單：將變換后的向量坐標仍然表示在當前坐標系中。

旋轉變換是正交變換的一個方面，這個挺有用的，比如在開發中需要實現某種旋轉效果，直接可以用旋轉變換實現。正交變換的另一個方面是反射變換，也即e1'的方向與圖中方向相反，這個不再討論。

總結：正交矩陣的行（列）向量都是兩兩正交的單位向量，正交矩陣對應的變換為正交變換，它有兩種表現：旋轉和反射。正交矩陣將標準正交基映射為標準正交基（即圖中從e1、e2到e1'、e2'）

特征值分解——EVD

在討論SVD之前先討論矩陣的特征值分解（EVD），在這里，選擇一種特殊的矩陣——對稱陣（酉空間中叫hermite矩陣即厄米陣）。對稱陣有一個很優美的性質：它總能相似對角化，對稱陣不同特征值對應的特征向量兩兩正交。一個矩陣能相似對角化即說明其特征子空間即為其列空間，若不能對角化則其特征子空間為列空間的子空間?，F在假設存在mxm的滿秩對稱矩陣A，它有m個不同的特征值，設特征值為

對應的單位特征向量為

則有

進而

所以可得到A的特征值分解（由于對稱陣特征向量兩兩正交，所以U為正交陣，正交陣的逆矩陣等于其轉置）

這里假設A有m個不同的特征值，實際上，只要A是對稱陣其均有如上分解。

矩陣A分解了，相應的，其對應的映射也分解為三個映射?，F在假設有x向量，用Ａ將其變換到Ａ的列空間中，那么首先由U'先對x做變換：

U是正交陣U'也是正交陣，所以U'對x的變換是正交變換，它將x用新的坐標系來表示，這個坐標系就是A的所有正交的特征向量構成的坐標系。比如將x用A的所有特征向量表示為：

則通過第一個變換就可以把x表示為[a1 a2 ... am]'：

緊接著，在新的坐標系表示下，由中間那個對角矩陣對新的向量坐標換，其結果就是將向量往各個軸方向拉伸或壓縮：

從上圖可以看到，如果A不是滿秩的話，那么就是說對角陣的對角線上元素存在0，這時候就會導致維度退化，這樣就會使映射后的向量落入m維空間的子空間中。

最后一個變換就是U對拉伸或壓縮后的向量做變換，由于U和U'是互為逆矩陣，所以U變換是U'變換的逆變換。

因此，從對稱陣的分解對應的映射分解來分析一個矩陣的變換特點是非常直觀的。假設對稱陣特征值全為1那么顯然它就是單位陣，如果對稱陣的特征值有個別是0其他全是1，那么它就是一個正交投影矩陣，它將m維向量投影到它的列空間中。

根據對稱陣A的特征向量，如果A是2*2的，那么就可以在二維平面中找到這樣一個矩形，是的這個矩形經過A變換后還是矩形：

這個矩形的選擇就是讓其邊都落在A的特征向量方向上，如果選擇其他矩形的話變換后的圖形就不是矩形了！

奇異值分解——SVD

上面的特征值分解的A矩陣是對稱陣，根據EVD可以找到一個（超）矩形使得變換后還是（超）矩形，也即A可以將一組正交基映射到另一組正交基！那么現在來分析：對任意M*N的矩陣，能否找到一組正交基使得經過它變換后還是正交基？答案是肯定的，它就是SVD分解的精髓所在。

現在假設存在M*N矩陣A，事實上，A矩陣將n維空間中的向量映射到k（k<=m）維空間中，k=Rank(A)?，F在的目標就是：在n維空間中找一組正交基，使得經過A變換后還是正交的。假設已經找到這樣一組正交基：

則A矩陣將這組基映射為：

如果要使他們兩兩正交，即

根據假設，存在

所以如果正交基v選擇為A'A的特征向量的話，由于A'A是對稱陣，v之間兩兩正交，那么

這樣就找到了正交基使其映射后還是正交基了，現在，將映射后的正交基單位化：

因為

所以有

所以取單位向量

由此可得

當k < i <= m時，對u1，u2，...，uk進行擴展u(k+1),...,um，使得u1，u2，...，um為m維空間中的一組正交基，即

同樣的，對v1，v2，...，vk進行擴展v(k+1),...,vn（這n-k個向量存在于A的零空間中，即Ax=0的解空間的基），使得v1，v2，...，vn為n維空間中的一組正交基，即

則可得到

繼而可以得到A矩陣的奇異值分解：

現在可以來對A矩陣的映射過程進行分析了：如果在n維空間中找到一個（超）矩形，其邊都落在A'A的特征向量的方向上，那么經過A變換后的形狀仍然為（超）矩形！

vi為A'A的特征向量，稱為A的右奇異向量，ui=Avi實際上為AA'的特征向量，稱為A的左奇異向量。下面利用SVD證明文章一開始的滿秩分解：

利用矩陣分塊乘法展開得：

可以看到第二項為0，有

則A=XY即是A的滿秩分解。

整個SVD的推導過程就是這樣，后面會介紹SVD在推薦系統中的具體應用，也就是復現Koren論文中的算法以及其推導過程。