?奇異值分解(SVD) --- 幾何意義?2013-12-16 22:33:42

分類：?大數據

PS：一直以來對SVD分解似懂非懂，此文為譯文，原文以細致的分析+大量的可視化圖形演示了SVD的幾何意義。能在有限的篇幅把 這個問題講解的如此清晰，實屬不易。原文舉了一個簡單的圖像處理問題，簡單形象，真心希望路過的各路朋友能從不同的角度闡述下自己對SVD實際意義的理 解，比如 個性化推薦中應用了SVD，文本以及Web挖掘的時候也經常會用到SVD。

原文：We recommend a singular value decomposition

關于線性變換部分的一些知識可以猛戳這里??奇異值分解(SVD) --- 線性變換幾何意義

奇異值分解( The singular value decomposition )

該部分是從幾何層面上去理解二維的SVD：對于任意的 2 x 2 矩陣，通過SVD可以將一個相互垂直的網格(orthogonal grid)變換到另外一個相互垂直的網格。

我們可以通過向量的方式來描述這個事實: 首先，選擇兩個相互正交的單位向量?v_1?和?v₂, 向量Mv₁?和?Mv₂?正交。

u₁?和?u₂分別表示Mv₁?和?Mv₂的單位向量，σ₁?*?u₁?= ?Mv₁?和?σ₂?*?u₂?= ?Mv₂。σ₁?和?σ₂分別表示這不同方向向量上的模，也稱作為矩陣?M?的奇異值。

這樣我們就有了如下關系式

Mv₁?= σ₁u₁?
Mv₂?= σ₂u₂

我們現在可以簡單描述下經過?M?線性變換后的向量?x?的表達形式。由于向量v₁?和?v₂是正交的單位向量，我們可以得到如下式子：

x?= (v₁x)?v₁?+ (v₂x)?v₂

這就意味著：

Mx?= (v₁x)?Mv₁?+ (v₂x)?Mv₂?
Mx?= (v₁x) σ₁u₁?+ (v₂x) σ₂u₂

向量內積可以用向量的轉置來表示，如下所示

vx?=?v^Tx

最終的式子為

Mx?=?u₁σ₁?v₁^Tx?+?u₂σ₂?v₂^Tx?
M?=?u₁σ₁?v₁^T?+?u₂σ₂?v₂^T

上述的式子經常表示成

M?=?UΣV^T

u?矩陣的列向量分別是u₁,u_2?，Σ?是一個對角矩陣，對角元素分別是對應的σ₁?和?σ₂，V?矩陣的列向量分別是v₁,v₂。上角標?T?表示矩陣?V?的轉置。

? ?這就表明任意的矩陣?M?是可以分解成三個矩陣。V?表示了原始域的標準正交基，u?表示經過?M?變換后的co-domain的標準正交基，Σ?表示了V?中的向量與u?中 相對應向量之間的關系。(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? )

? ?事實上我們可以找到任何矩陣的奇異值分解，那么我們是如何做到的呢？假設在原始域中有一個單位圓，如下圖所示。經過?M?矩陣變換以后在co-domain中單位圓會變成一個橢圓，它的長軸(Mv₁)和短軸(Mv₂)分別對應轉換后的兩個標準正交向量，也是在橢圓范圍內最長和最短的兩個向量。

換句話說，定義在單位圓上的函數|Mx|分別在v₁和v₂方向上取得最大和最小值。這樣我們就把尋找矩陣的奇異值分解過程縮小到了優化函數|Mx|上了。結果發現（具體的推到過程這里就不詳細介紹了）這個函數取得最優值的向量分別是矩陣 MT M 的特征向量。由于MTM是對稱矩陣，因此不同特征值對應的特征向量都是互相正交的，我們用vi 表示MTM的所有特征向量。奇異值σ_i?= |Mv_i|?， 向量?u_i?為?Mv_i?方向上的單位向量。但為什么u_i也是正交的呢？

推倒如下：

σ_i?和?σ_j分別是不同兩個奇異值

Mv_i?= σ_iu_i?
Mv_j?= σ_ju_j.

我們先看下Mv_iMv_j，并假設它們分別對應的奇異值都不為零。一方面這個表達的值為0，推到如下

Mv_i?Mv_j?=?v_i^TM^T?Mv_j?=?v_i?M^TMv_j?= λ_jv_i?v_j?= 0

另一方面，我們有

Mv_i?Mv_j?= σ_iσ_j?u_i?u_j?= 0

因此，u_i?和?u_j是正交的。但實際上，這并非是求解奇異值的方法，效率會非常低。這里也主要不是討論如何求解奇異值，為了演示方便，采用的都是二階矩陣。

應用實例(Another example)

現在我們來看幾個實例。

實例一

經過這個矩陣變換后的效果如下圖所示

在這個例子中，第二個奇異值為 0，因此經過變換后只有一個方向上有表達。

M =?u₁σ₁?v₁^T.

換句話說，如果某些奇異值非常小的話，其相對應的幾項就可以不同出現在矩陣?M?的分解式中。因此，我們可以看到矩陣?M?的秩的大小等于非零奇異值的個數。

實例二

我們來看一個奇異值分解在數據表達上的應用。假設我們有如下的一張 15 x 25 的圖像數據。

如圖所示，該圖像主要由下面三部分構成。

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

如果我們對矩陣M進行奇異值分解以后，得到奇異值分別是

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

矩陣M就可以表示成

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

v_i具有15個元素，u_i?具有25個元素，σ_i?對應不同的奇異值。如上圖所示，我們就可以用123個元素來表示具有375個元素的圖像數據了。

實例三

減噪(noise reduction)

前面的例子的奇異值都不為零，或者都還算比較大，下面我們來探索一下擁有零或者非常小的奇異值的情況。通常來講，大的奇異值對應的部分會包含更多的信息。比如，我們有一張掃描的，帶有噪聲的圖像，如下圖所示

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

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

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

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

經過奇異值分解后，我們得到了一張降噪后的圖像。

實例四

數據分析(data analysis)

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

作為例子，假如我們搜集的數據如下所示：

我們將數據用矩陣的形式表示：

經過奇異值分解后，得到

σ₁?= 6.04?
σ₂?= 0.22

由于第一個奇異值遠比第二個要大，數據中有包含一些噪聲，第二個奇異值在原始矩陣分解相對應的部分可以忽略。經過SVD分解后，保留了主要樣本點如圖所示

就保留主要樣本數據來看，該過程跟PCA( principal component analysis)技術有一些聯系，PCA也使用了SVD去檢測數據間依賴和冗余信息.

總結(Summary)

? ?這篇文章非常的清晰的講解了SVD的幾何意義，不僅從數學的角度，還聯系了幾個應用實例形象的論述了SVD是如何發現數據中主要信息的。在 netflix prize中許多團隊都運用了矩陣分解的技術，該技術就來源于SVD的分解思想，矩陣分解算是SVD的變形，但思想還是一致的。之前算是能夠運用矩陣分解 技術于個性化推薦系統中，但理解起來不夠直觀，閱讀原文后醍醐灌頂，我想就從SVD能夠發現數據中的主要信息的思路，就幾個方面去思考下如何利用數據中所 蘊含的潛在關系去探索個性化推薦系統。也希望路過的各位大俠不吝分享呀。

References:

Gilbert Strang,?Linear Algebra and Its Applications. Brooks Cole

William H. Press?et al,?Numercial Recipes in C: The Art of Scientific Computing. Cambridge University Press.

Dan Kalman,?A Singularly Valuable Decomposition: The SVD of a Matrix,?The College Mathematics Journal?27?(1996), 2-23.

If You Liked This, You're Sure to Love That,?The New York Times, November 21, 2008.

http://blog.sciencenet.cn/blog-696950-699432.html

總結

以上是生活随笔為你收集整理的奇异值分解(SVD) --- 几何意义的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。