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

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

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

這個可以應(yīng)用在數(shù)據(jù)降維壓縮上！在數(shù)據(jù)相關(guān)性特別大的情況下存儲X和Y矩陣比存儲A矩陣占用空間更??！

在開始講解SVD之前，先補(bǔ)充一點(diǎn)矩陣代數(shù)的相關(guān)知識。

正交矩陣

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

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

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

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

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

總結(jié)：正交矩陣的行（列）向量都是兩兩正交的單位向量，正交矩陣對應(yīng)的變換為正交變換，它有兩種表現(xiàn)：旋轉(zhuǎn)和反射。正交矩陣將標(biāo)準(zhǔn)正交基映射為標(biāo)準(zhǔn)正交基（即圖中從e1、e2到e1'、e2'）

特征值分解——EVD

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

對應(yīng)的單位特征向量為

則有

進(jìn)而

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

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

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

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

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

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

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

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

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

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

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

奇異值分解——SVD

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

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

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

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

根據(jù)假設(shè)，存在

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

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

因為

所以有

所以取單位向量

由此可得

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

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

則可得到

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

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

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

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

可以看到第二項為0，有

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

整個SVD的推導(dǎo)過程就是這樣，后面會介紹SVD在推薦系統(tǒng)中的具體應(yīng)用，也就是復(fù)現(xiàn)Koren論文中的算法以及其推導(dǎo)過程。