SVD分解算法及其應(yīng)用

時(shí)間?2013-07-16 11:39:27??十一城 原文?http://elevencitys.com/?p=3923 主題奇異值分解?主成分分析?算法

矩陣的奇異值分解在矩陣?yán)碚摰闹匾圆谎远?#xff0c;它在最優(yōu)化問(wèn)題、特征值問(wèn)題、最小乘方問(wèn)題、廣義逆矩陣問(wèn),統(tǒng)計(jì)學(xué),圖像壓縮等方面都有十分重要的應(yīng)用。

定義：?設(shè)A為m*n階矩陣，?A?^H?A?的n個(gè)特征值的非負(fù)平方根叫作A的奇異值。記為?σ_i?(A)。?>?如果把A?^H?A的特征值記為λ?_i?(A)，則σ?_i?(A)＝?λ?_i?(A?^H?A)^(1/2)。?

定理?（奇異值分解）設(shè)A為m*n階復(fù)矩陣，則存在m階酉陣U和n階酉陣V，使得：

A = U*S*V’

其中S=diag(σ?_i?,σ?₂?,……,σ?_r?)，σ?_i?>0??(i=1,…,r)，r=rank(A)?。?

推論：?設(shè)A為m*n階實(shí)矩陣，則存在m階正交陣U和n階正交陣V，使得

A = U*S*V’

其中S=diag(σ?_i?,σ?₂?,……,σ?_r?)，σ?_i?>0??(i=1,…,r)，r=rank(A)?。

奇異值分解提供了一些關(guān)于A的信息，例如非零奇異值的數(shù)目（S的階數(shù)）和A的秩相同，一旦秩r確定，那么U的前r?列構(gòu)成了A的列向量空間的正交基，另外V的從右向左n-r列為A的kernel的基。

非退化的奇異值具有唯一的左、右奇異向量，如果?A?的所有奇異值都是非退化且非零，則它的奇異值分解是唯一的，因?yàn)?U?中的一列要乘以一個(gè)單位相位因子且同時(shí)?V中相應(yīng)的列也要乘以同一個(gè)相位因子。

根據(jù)定義，退化的奇異值具有不唯一的奇異向量。因?yàn)?#xff0c;如果?u?₁?和?u?₂?為奇異值σ的兩個(gè)左奇異向量，則兩個(gè)向量的任意規(guī)范線性組合也是奇異值σ一個(gè)左奇異向量，類似的，右奇異向量也具有相同的性質(zhì)。因此，如果?MA?具有退化的奇異值，則它的奇異值分解是不唯一的。

在壓縮圖像應(yīng)用中，抽象的例子可以入下圖所示：

上圖中三個(gè)矩陣相乘的結(jié)果將會(huì)是一個(gè)接近于A的矩陣，在這兒，r越接近于n，則相乘的結(jié)果越接近于A。而這三個(gè)矩陣的面積之和（在存儲(chǔ)觀點(diǎn)來(lái)說(shuō)，矩陣面積越小，存儲(chǔ)量就越小）要遠(yuǎn)遠(yuǎn)小于原始的矩陣A，我們?nèi)绻胍獕嚎s空間來(lái)表示原矩陣A，我們存下這里的三個(gè)矩陣：U、Σ、V就好了。

主要應(yīng)用領(lǐng)域

一、奇異值與主成分分析（PCA）

PCA的問(wèn)題其實(shí)是一個(gè)基的變換，使得變換后的數(shù)據(jù)有著最大的方差。方差的大小描述的是一個(gè)變量的信息量，我們?cè)谥v一個(gè)東西的穩(wěn)定性的時(shí)候，往往說(shuō)要減小方差，如果一個(gè)模型的方差很大，那就說(shuō)明模型不穩(wěn)定了。但是對(duì)于我們用于機(jī)器學(xué)習(xí)的數(shù)據(jù)（主要是訓(xùn)練數(shù)據(jù)），方差大才有意義，不然輸入的數(shù)據(jù)都是同一個(gè)點(diǎn)，那方差就為0了，這樣輸入的多個(gè)數(shù)據(jù)就等同于一個(gè)數(shù)據(jù)了。以下面這張圖為例子：

???? 這個(gè)假設(shè)是一個(gè)攝像機(jī)采集一個(gè)物體運(yùn)動(dòng)得到的圖片，上面的點(diǎn)表示物體運(yùn)動(dòng)的位置，假如我們想要用一條直線去擬合這些點(diǎn)，那我們會(huì)選擇什么方向的線呢？當(dāng)然是圖上標(biāo)有signal的那條線。如果我們把這些點(diǎn)單純的投影到x軸或者y軸上，最后在x軸與y軸上得到的方差是相似的（因?yàn)檫@些點(diǎn)的趨勢(shì)是在45度左右的方向，所以投影到x軸或者y軸上都是類似的），如果我們使用原來(lái)的xy坐標(biāo)系去看這些點(diǎn)，容易看不出來(lái)這些點(diǎn)真正的方向是什么。但是如果我們進(jìn)行坐標(biāo)系的變化，橫軸變成了signal的方向，縱軸變成了noise的方向，則就很容易發(fā)現(xiàn)什么方向的方差大，什么方向的方差小了。

一般來(lái)說(shuō)，方差大的方向是信號(hào)的方向，方差小的方向是噪聲的方向，我們?cè)跀?shù)據(jù)挖掘中或者數(shù)字信號(hào)處理中，往往要提高信號(hào)與噪聲的比例，也就是信噪比。對(duì)上圖來(lái)說(shuō)，如果我們只保留signal方向的數(shù)據(jù)，也可以對(duì)原數(shù)據(jù)進(jìn)行不錯(cuò)的近似了。

PCA的全部工作簡(jiǎn)單點(diǎn)說(shuō)，就是對(duì)原始的空間中順序地找一組相互正交的坐標(biāo)軸，第一個(gè)軸是使得方差最大的，第二個(gè)軸是在與第一個(gè)軸正交的平面中使得方差最大的，第三個(gè)軸是在與第1、2個(gè)軸正交的平面中方差最大的，這樣假設(shè)在N維空間中，我們可以找到N個(gè)這樣的坐標(biāo)軸，我們?nèi)∏皉個(gè)去近似這個(gè)空間，這樣就從一個(gè)N維的空間壓縮到r維的空間了，但是我們選擇的r個(gè)坐標(biāo)軸能夠使得空間的壓縮使得數(shù)據(jù)的損失最小。

還是假設(shè)我們矩陣每一行表示一個(gè)樣本，每一列表示一個(gè)feature，用矩陣的語(yǔ)言來(lái)表示，將一個(gè)m * n的矩陣A的進(jìn)行坐標(biāo)軸的變化，P就是一個(gè)變換的矩陣從一個(gè)N維的空間變換到另一個(gè)N維的空間，在空間中就會(huì)進(jìn)行一些類似于旋轉(zhuǎn)、拉伸的變化。

而將一個(gè)m * n的矩陣A變換成一個(gè)m * r的矩陣，這樣就會(huì)使得本來(lái)有n個(gè)feature的，變成了有r個(gè)feature了（r < n)，這r個(gè)其實(shí)就是對(duì)n個(gè)feature的一種提煉，我們就把這個(gè)稱為feature的壓縮。用數(shù)學(xué)語(yǔ)言表示就是：

??? 但是這個(gè)怎么和SVD扯上關(guān)系呢？之前談到，SVD得出的奇異向量也是從奇異值由大到小排列的，按PCA的觀點(diǎn)來(lái)看，就是方差最大的坐標(biāo)軸就是第一個(gè)奇異向量，方差次大的坐標(biāo)軸就是第二個(gè)奇異向量…我們回憶一下之前得到的SVD式子：

???? 在矩陣的兩邊同時(shí)乘上一個(gè)矩陣V，由于V是一個(gè)正交的矩陣，所以V轉(zhuǎn)置乘以V得到單位陣I，所以可以化成后面的式子

???? 將后面的式子與A * P那個(gè)m * n的矩陣變換為m * r的矩陣的式子對(duì)照看看，在這里，其實(shí)V就是P，也就是一個(gè)變化的向量。這里是將一個(gè)m * n 的矩陣壓縮到一個(gè)m * r的矩陣，也就是對(duì)列進(jìn)行壓縮，如果我們想對(duì)行進(jìn)行壓縮（在PCA的觀點(diǎn)下，對(duì)行進(jìn)行壓縮可以理解為，將一些相似的sample合并在一起，或者將一些沒有太大價(jià)值的sample去掉）怎么辦呢？同樣我們寫出一個(gè)通用的行壓縮例子：

??? 這樣就從一個(gè)m行的矩陣壓縮到一個(gè)r行的矩陣了，對(duì)SVD來(lái)說(shuō)也是一樣的，我們對(duì)SVD分解的式子兩邊乘以U的轉(zhuǎn)置U’

??? 這樣我們就得到了對(duì)行進(jìn)行壓縮的式子。可以看出，其實(shí)PCA幾乎可以說(shuō)是對(duì)SVD的一個(gè)包裝，如果我們實(shí)現(xiàn)了SVD，那也就實(shí)現(xiàn)了PCA了，而且更好的地方是，有了SVD，我們就可以得到兩個(gè)方向的PCA，如果我們對(duì)A’A進(jìn)行特征值的分解，只能得到一個(gè)方向的PCA。

二、奇異值與潛在語(yǔ)義索引LSI

潛在語(yǔ)義索引（Latent Semantic Indexing）與PCA不太一樣，至少不是實(shí)現(xiàn)了SVD就可以直接用的，不過(guò)LSI也是一個(gè)嚴(yán)重依賴于SVD的算法，在?矩陣計(jì)算與文本處理中的分類問(wèn)題?中談到：

??? “三個(gè)矩陣有非常清楚的物理含義。第一個(gè)矩陣X中的每一行表示意思相關(guān)的一類詞，其中的每個(gè)非零元素表示這類詞中每個(gè)詞的重要性（或者說(shuō)相關(guān)性），數(shù)值越大越相關(guān)。最后一個(gè)矩陣Y中的每一列表示同一主題一類文章，其中每個(gè)元素表示這類文章中每篇文章的相關(guān)性。中間的矩陣則表示類詞和文章雷之間的相關(guān)性。因此，我們只要對(duì)關(guān)聯(lián)矩陣A進(jìn)行一次奇異值分解，w 我們就可以同時(shí)完成了近義詞分類和文章的分類。（同時(shí)得到每類文章和每類詞的相關(guān)性）。”

上面這段話可能不太容易理解，不過(guò)這就是LSI的精髓內(nèi)容，我下面舉一個(gè)例子來(lái)說(shuō)明一下，下面的例子來(lái)自LSA tutorial：

????? 這就是一個(gè)矩陣，不過(guò)不太一樣的是，這里的一行表示一個(gè)詞在哪些title中出現(xiàn)了（一行就是之前說(shuō)的一維feature），一列表示一個(gè)title中有哪些詞，（這個(gè)矩陣其實(shí)是我們之前說(shuō)的那種一行是一個(gè)sample的形式的一種轉(zhuǎn)置，這個(gè)會(huì)使得我們的左右奇異向量的意義產(chǎn)生變化，但是不會(huì)影響我們計(jì)算的過(guò)程）。比如說(shuō)T1這個(gè)title中就有g(shù)uide、investing、market、stock四個(gè)詞，各出現(xiàn)了一次，我們將這個(gè)矩陣進(jìn)行SVD，得到下面的矩陣：

????? 左奇異向量表示詞的一些特性，右奇異向量表示文檔的一些特性，中間的奇異值矩陣表示左奇異向量的一行與右奇異向量的一列的重要程序，數(shù)字越大越重要。

繼續(xù)看這個(gè)矩陣還可以發(fā)現(xiàn)一些有意思的東西，首先，左奇異向量的第一列表示每一個(gè)詞的出現(xiàn)頻繁程度，雖然不是線性的，但是可以認(rèn)為是一個(gè)大概的描述，比如book是0.15對(duì)應(yīng)文檔中出現(xiàn)的2次，investing是0.74對(duì)應(yīng)了文檔中出現(xiàn)了9次，rich是0.36對(duì)應(yīng)文檔中出現(xiàn)了3次；

其次，右奇異向量中一的第一行表示每一篇文檔中的出現(xiàn)詞的個(gè)數(shù)的近似，比如說(shuō)，T6是0.49，出現(xiàn)了5個(gè)詞，T2是0.22，出現(xiàn)了2個(gè)詞。

然后我們反過(guò)頭來(lái)看，我們可以將左奇異向量和右奇異向量都取后2維（之前是3維的矩陣），投影到一個(gè)平面上，可以得到：

???? 在圖上，每一個(gè)紅色的點(diǎn)，都表示一個(gè)詞，每一個(gè)藍(lán)色的點(diǎn)，都表示一篇文檔，這樣我們可以對(duì)這些詞和文檔進(jìn)行聚類，比如說(shuō)stock 和 market可以放在一類，因?yàn)樗麄兝鲜浅霈F(xiàn)在一起，real和estate可以放在一類，dads，guide這種詞就看起來(lái)有點(diǎn)孤立了，我們就不對(duì)他們進(jìn)行合并了。按這樣聚類出現(xiàn)的效果，可以提取文檔集合中的近義詞，這樣當(dāng)用戶檢索文檔的時(shí)候，是用語(yǔ)義級(jí)別（近義詞集合）去檢索了，而不是之前的詞的級(jí)別。這樣一減少我們的檢索、存儲(chǔ)量，因?yàn)檫@樣壓縮的文檔集合和PCA是異曲同工的，二可以提高我們的用戶體驗(yàn)，用戶輸入一個(gè)詞，我們可以在這個(gè)詞的近義詞的集合中去找，這是傳統(tǒng)的索引無(wú)法做到的。

三、圖像壓縮

我們來(lái)看一個(gè)奇異值分解在數(shù)據(jù)表達(dá)上的應(yīng)用。假設(shè)我們有如下的一張 15 x 25 的圖像數(shù)據(jù)。

如圖所示，該圖像主要由下面三部分構(gòu)成。

我們將圖像表示成 15 x 25 的矩陣，矩陣的元素對(duì)應(yīng)著圖像的不同像素，如果像素是白色的話，就取 1，黑色的就取 0. 我們得到了一個(gè)具有375個(gè)元素的矩陣，如下圖所示

如果我們對(duì)矩陣M進(jìn)行奇異值分解以后，得到奇異值分別是

σ?₁??= 14.72?
σ?₂??= 5.22?
σ?₃??= 3.31

矩陣M就可以表示成

M?=?u?₁?σ?₁???v?₁?^T??+??u?₂?σ?₂???v?₂?^T??+??u?₃?σ?₃???v?₃?^T

v?_i?具有15個(gè)元素，?u?_i??具有25個(gè)元素，σ?_i??對(duì)應(yīng)不同的奇異值。如上圖所示，我們就可以用123個(gè)元素來(lái)表示具有375個(gè)元素的圖像數(shù)據(jù)了。

四、去除噪聲

前面的例子的奇異值都不為零，或者都還算比較大，下面我們來(lái)探索一下?lián)碛辛慊蛘叻浅Ｐ〉钠娈愔档那闆r。通常來(lái)講，大的奇異值對(duì)應(yīng)的部分會(huì)包含更多的信息。比如，我們有一張掃描的，帶有噪聲的圖像，如下圖所示

我們采用跟實(shí)例二相同的處理方式處理該掃描圖像。得到圖像矩陣的奇異值：

σ?₁??= 14.15?
σ?₂??= 4.67?
σ?₃??= 3.00?
σ?₄??= 0.21?
σ?₅??= 0.19?
…?
σ?₁₅??= 0.05

很明顯，前面三個(gè)奇異值遠(yuǎn)遠(yuǎn)比后面的奇異值要大，這樣矩陣?M?的分解方式就可以如下：

M??????u?₁?σ?₁???v?₁?^T??+??u?₂?σ?₂???v?₂?^T??+??u?₃?σ?₃???v?₃?^T

經(jīng)過(guò)奇異值分解后，我們得到了一張降噪后的圖像。

五、數(shù)據(jù)分析

我們搜集的數(shù)據(jù)中總是存在噪聲：無(wú)論采用的設(shè)備多精密，方法有多好，總是會(huì)存在一些誤差的。如果你們還記得上文提到的，大的奇異值對(duì)應(yīng)了矩陣中的主要信息的話，運(yùn)用SVD進(jìn)行數(shù)據(jù)分析，提取其中的主要部分的話，還是相當(dāng)合理的。

作為例子，假如我們搜集的數(shù)據(jù)如下所示：

我們將數(shù)據(jù)用矩陣的形式表示：

經(jīng)過(guò)奇異值分解后，得到

σ?₁??= 6.04?
σ?₂??= 0.22

由于第一個(gè)奇異值遠(yuǎn)比第二個(gè)要大，數(shù)據(jù)中有包含一些噪聲，第二個(gè)奇異值在原始矩陣分解相對(duì)應(yīng)的部分可以忽略。經(jīng)過(guò)SVD分解后，保留了主要樣本點(diǎn)如圖所示

就保留主要樣本數(shù)據(jù)來(lái)看，該過(guò)程跟PCA( principal component analysis)技術(shù)有一些聯(lián)系，PCA也使用了SVD去檢測(cè)數(shù)據(jù)間依賴和冗余信息.

參考資料：

1）?http://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html?
2）A Tutorial on Principal Component Analysis, Jonathon Shlens?
3）?http://www.puffinwarellc.com/index.php/news-and-articles/articles/30-singular-value-decomposition-tutorial.html?
4）?http://www.puffinwarellc.com/index.php/news-and-articles/articles/33-latent-semantic-analysis-tutorial.html?
5）?http://www.miislita.com/information-retrieval-tutorial/svd-lsi-tutorial-1-understanding.html?
6）Singular Value Decomposition and Principal Component Analysis, Rasmus Elsborg Madsen, Lars Kai Hansen and Ole Winther, 2004?
7）?http://blog.sciencenet.cn/blog-696950-699432.html

總結(jié)

以上是生活随笔為你收集整理的SVD分解算法及其应用的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。