轉載請聲明出處http://blog.csdn.net/zhongkejingwang/article/details/43053513
在網上看到有很多文章介紹SVD的，講的也都不錯，但是感覺還是有需要補充的，特别是關于矩陣和映射之間的對應關系。前段時間看了國外的一篇文章，叫A Singularly Valuable Decomposition The SVD of a Matrix，覺得分析的特别好，把矩陣和空間關系對應了起來。本文就參考了該文并結合矩陣的相關知識把SVD原理梳理一下。
SVD不僅是一個數學問題，在工程應用中的很多地方都有它的身影，比如前面講的PCA，掌握了SVD原理後再去看PCA那是相當簡單的，在推薦系統方面，SVD更是名聲大噪，将它應用于推薦系統的是Netflix大獎的獲得者Koren，可以在Google上找到他寫的文章；用SVD可以很容易得到任意矩陣的滿秩分解，用滿秩分解可以對資料做壓縮。可以用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呢？如下
a’和b’實際上是x在e1’和e2’軸上的投影大小，是以直接做内積可得，then
從圖中可以看到
是以
正交陣U行（列）向量之間都是機關正交向量。上面求得的是一個旋轉矩陣，它對向量做旋轉變換！也許你會有疑問：剛才不是說向量空間位置不變嗎？怎麼現在又說它被旋轉了？對的，這兩個并沒有沖突，說空間位置不變是絕對的，但是坐标是相對的，加入你站在e1上看OA，随着e1旋轉到e1’，看OA的位置就會改變。如下圖：
如圖，如果我選擇了e1’、e2’作為新的标準坐标系，那麼在新坐标系中OA（原标準坐标系的表示）就變成了OA’，這樣看來就好像坐标系不動，把OA往順時針方向旋轉了“斯塔”角度，這個操作實作起來很簡單：将變換後的向量坐标仍然表示在目前坐标系中。
旋轉變換是正交變換的一個方面，這個挺有用的，比如在開發中需要實作某種旋轉效果，直接可以用旋轉變換實作。正交變換的另一個方面是反射變換，也即e1’的方向與圖中方向相反，這個不再讨論。
總結：正交矩陣的行（列）向量都是兩兩正交的機關向量，正交矩陣對應的變換為正交變換，它有兩種表現：旋轉和反射。正交矩陣将标準正交基映射為标準正交基（即圖中從e1、e2到e1’、e2’）
特征值分解——EVD
在讨論SVD之前先讨論矩陣的特征值分解（EVD），在這裡，選擇一種特殊的矩陣——對稱陣（酉空間中叫hermite矩陣即厄米陣）。對稱陣有一個很優美的性質：它總能相似對角化，對稱陣不同特征值對應的特征向量兩兩正交。一個矩陣能相似對角化即說明其特征子空間即為其列空間，若不能對角化則其特征子空間為列空間的子空間。現在假設存在mxm的滿秩對稱矩陣A，它有m個不同的特征值，設特征值為
對應的機關特征向量為
則有
進而
是以可得到A的特征值分解（由于對稱陣特征向量兩兩正交，是以U為正交陣，正交陣的逆矩陣等于其轉置）
這裡假設A有m個不同的特征值，實際上，隻要A是對稱陣其均有如上分解。
矩陣A分解了，相應的，其對應的映射也分解為三個映射。現在假設有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)。現在的目标就是：在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論文中的算法以及其推導過程。
參考文獻：A Singularly Valuable Decomposition The SVD of a Matrix