原文：http://blog.sciencenet.cn/blog-696950-699432.html
關(guān)于線性變換部分的一些知識(shí)可以猛戳這里奇異值分解(SVD) --- 線性變換幾何意義
奇異值分解( The singular value decomposition )
該部分是從幾何層面上去理解二維的SVD：對于任意的 2 x 2 矩陣，通過SVD可以將一個(gè)相互垂直的網(wǎng)格(orthogonal grid)變換到另外一個(gè)相互垂直的網(wǎng)格。
我們可以通過向量的方式來描述這個(gè)事實(shí): 首先，選擇兩個(gè)相互正交的單位向量v1和v2, 向量Mv1和Mv2正交。
u1和u2分別表示Mv1和Mv2的單位向量，σ1*u1=Mv1和 σ2*u2=Mv2。σ1和 σ2分別表示這不同方向向量上的模，也稱作為矩陣 M 的奇異值。
這樣我們就有了如下關(guān)系式
Mv1= σ1u1
Mv2= σ2u2
我們現(xiàn)在可以簡單描述下經(jīng)過?M?線性變換后的向量?x?的表達(dá)形式。由于向量v1和v2是正交的單位向量，我們可以得到如下式子：
x= (v1x)v1+ (v2x)v2
這就意味著：
Mx= (v1x)Mv1+ (v2x)Mv2
Mx= (v1x) σ1u1+ (v2x) σ2u2
向量內(nèi)積可以用向量的轉(zhuǎn)置來表示，如下所示
vx=vTx
最終的式子為
Mx=u1σ1v1Tx+u2σ2v2Tx
M=u1σ1v1T+u2σ2v2T
上述的式子經(jīng)常表示成
M=UΣVT
u矩陣的列向量分別是u1,u2，Σ?是一個(gè)對角矩陣，對角元素分別是對應(yīng)的σ1和?σ2，V矩陣的列向量分別是v1,v2。上角標(biāo)T表示矩陣V的轉(zhuǎn)置。
這就表明任意的矩陣?M?是可以分解成三個(gè)矩陣。V表示了原始域的標(biāo)準(zhǔn)正交基，u表示經(jīng)過?M?變換后的co-domain的標(biāo)準(zhǔn)正交基，Σ?表示了V中的向量與u中相對應(yīng)向量之間的關(guān)系。(V describes an orthonormal basis in the domain, and U describes an orthonormal basis in the co-domain, and Σ describes how much the vectors in V are stretched to give the vectors in U.)
如何獲得奇異值分解？( How do we find the singular decomposition? )
事實(shí)上我們可以找到任何矩陣的奇異值分解，那么我們是如何做到的呢？假設(shè)在原始域中有一個(gè)單位圓，如下圖所示。經(jīng)過 M 矩陣變換以后在co-domain中單位圓會(huì)變成一個(gè)橢圓，它的長軸(Mv1)和短軸(Mv2)分別對應(yīng)轉(zhuǎn)換后的兩個(gè)標(biāo)準(zhǔn)正交向量，也是在橢圓范圍內(nèi)最長和最短的兩個(gè)向量。
換句話說，定義在單位圓上的函數(shù)|Mx|分別在v1和v2方向上取得最大和最小值。這樣我們就把尋找矩陣的奇異值分解過程縮小到了優(yōu)化函數(shù)|Mx|上了。結(jié)果發(fā)現(xiàn)（具體的推到過程這里就不詳細(xì)介紹了）這個(gè)函數(shù)取得最優(yōu)值的向量分別是矩陣 MT M 的特征向量。由于MTM是對稱矩陣，因此不同特征值對應(yīng)的特征向量都是互相正交的，我們用vi 表示MTM的所有特征向量。奇異值σi= |Mvi|?， 向量ui為Mvi方向上的單位向量。但為什么ui也是正交的呢？
推導(dǎo)如下：
σi和?σj分別是不同兩個(gè)奇異值
Mvi= σiui
Mvj= σjuj.
我們先看下MviMvj，并假設(shè)它們分別對應(yīng)的奇異值都不為零。一方面這個(gè)表達(dá)的值為0，推到如下
MviMvj=viTMTMvj=viMTMvj= λjvivj= 0
另一方面，我們有
MviMvj= σiσjuiuj= 0
因此，ui和uj是正交的。但實(shí)際上，這并非是求解奇異值的方法，效率會(huì)非常低。這里也主要不是討論如何求解奇異值，為了演示方便，采用的都是二階矩陣。
應(yīng)用實(shí)例(Another example)
現(xiàn)在我們來看幾個(gè)實(shí)例。
實(shí)例一
經(jīng)過這個(gè)矩陣變換后的效果如下圖所示
在這個(gè)例子中，第二個(gè)奇異值為 0，因此經(jīng)過變換后只有一個(gè)方向上有表達(dá)。
M =u1σ1v1T.
換句話說，如果某些奇異值非常小的話，其相對應(yīng)的幾項(xiàng)就可以不同出現(xiàn)在矩陣?M?的分解式中。因此，我們可以看到矩陣?M?的秩的大小等于非零奇異值的個(gè)數(shù)。
實(shí)例二
我們來看一個(gè)奇異值分解在數(shù)據(jù)表達(dá)上的應(yīng)用。假設(shè)我們有如下的一張 15 x 25 的圖像數(shù)據(jù)。
如圖所示，該圖像主要由下面三部分構(gòu)成。
我們將圖像表示成 15 x 25 的矩陣，矩陣的元素對應(yīng)著圖像的不同像素，如果像素是白色的話，就取 1，黑色的就取 0. 我們得到了一個(gè)具有375個(gè)元素的矩陣，如下圖所示
如果我們對矩陣M進(jìn)行奇異值分解以后，得到奇異值分別是
σ1= 14.72
σ2= 5.22
σ3= 3.31
矩陣M就可以表示成
M=u1σ1v1T+u2σ2v2T+u3σ3v3T
vi具有15個(gè)元素，ui具有25個(gè)元素，σi對應(yīng)不同的奇異值。如上圖所示，我們就可以用123個(gè)元素來表示具有375個(gè)元素的圖像數(shù)據(jù)了。
實(shí)例三
減噪(noise reduction)
前面的例子的奇異值都不為零，或者都還算比較大，下面我們來探索一下?lián)碛辛慊蛘叻浅Ｐ〉钠娈愔档那闆r。通常來講，大的奇異值對應(yīng)的部分會(huì)包含更多的信息。比如，我們有一張掃描的，帶有噪聲的圖像，如下圖所示
我們采用跟實(shí)例二相同的處理方式處理該掃描圖像。得到圖像矩陣的奇異值：
σ1= 14.15
σ2= 4.67
σ3= 3.00
σ4= 0.21
σ5= 0.19
...
σ15= 0.05
很明顯，前面三個(gè)奇異值遠(yuǎn)遠(yuǎn)比后面的奇異值要大，這樣矩陣?M?的分解方式就可以如下：
Mu1σ1v1T+u2σ2v2T+u3σ3v3T
經(jīng)過奇異值分解后，我們得到了一張降噪后的圖像。
實(shí)例四
數(shù)據(jù)分析(data analysis)
我們搜集的數(shù)據(jù)中總是存在噪聲：無論采用的設(shè)備多精密，方法有多好，總是會(huì)存在一些誤差的。如果你們還記得上文提到的，大的奇異值對應(yīng)了矩陣中的主要信息的話，運(yùn)用SVD進(jìn)行數(shù)據(jù)分析，提取其中的主要部分的話，還是相當(dāng)合理的。
作為例子，假如我們搜集的數(shù)據(jù)如下所示：
我們將數(shù)據(jù)用矩陣的形式表示：
經(jīng)過奇異值分解后，得到
σ1= 6.04
σ2= 0.22
由于第一個(gè)奇異值遠(yuǎn)比第二個(gè)要大，數(shù)據(jù)中有包含一些噪聲，第二個(gè)奇異值在原始矩陣分解相對應(yīng)的部分可以忽略。經(jīng)過SVD分解后，保留了主要樣本點(diǎn)如圖所示
就保留主要樣本數(shù)據(jù)來看，該過程跟PCA( principal component analysis)技術(shù)有一些聯(lián)系，PCA也使用了SVD去檢測數(shù)據(jù)間依賴和冗余信息.
總結(jié)(Summary)
這篇文章非常的清晰的講解了SVD的幾何意義，不僅從數(shù)學(xué)的角度，還聯(lián)系了幾個(gè)應(yīng)用實(shí)例形象的論述了SVD是如何發(fā)現(xiàn)數(shù)據(jù)中主要信息的。在netflix prize中許多團(tuán)隊(duì)都運(yùn)用了矩陣分解的技術(shù)，該技術(shù)就來源于SVD的分解思想，矩陣分解算是SVD的變形，但思想還是一致的。之前算是能夠運(yùn)用矩陣分解技術(shù)于個(gè)性化推薦系統(tǒng)中，但理解起來不夠直觀，閱讀原文后醍醐灌頂，我想就從SVD能夠發(fā)現(xiàn)數(shù)據(jù)中的主要信息的思路，就幾個(gè)方面去思考下如何利用數(shù)據(jù)中所蘊(yùn)含的潛在關(guān)系去探索個(gè)性化推薦系統(tǒng)。也希望路過的各位大俠不吝分享呀。
