We Recommend a Singular Value Decomposition

我們推薦奇異值分解

奇異值分解可以方便地把一個矩陣（包含我們感興趣的數(shù)據(jù)）分解得更加簡單和有意義。 本文講解了奇異值分解的幾何解釋，順便也介紹了一些應用。

From http://www.ams.org/samplings/feature-column/fcarc-svd

David Austin旭贬，Grand ValleyState University

介紹

  本文的主題是奇異值分解(singular value decomposition佃延，SVD)用含，它應該是數(shù)學系研究生標準課程的一部分羊始，但是經常被忽略。除了十分直觀笙纤，此類分解(decomposition)還極其有用耗溜。比如，Netflix省容，一在線電影租賃公司抖拴，為改進他們的推薦系統(tǒng)設立了100萬美元獎金，要求是準確度(accuracy)提高10%腥椒。 令人驚訝的是城舞，這個看起來很普通的問題，實際上十分具有挑戰(zhàn)性寞酿。參與的團隊正在使用十分復雜的技術家夺。這些技術的核心便是奇異值分解。

  奇異值分解可以方便地把一個矩陣（包含我們感興趣的數(shù)據(jù)）分解得更加簡單和有意義伐弹。 本文講解了奇異值分解的幾何解釋拉馋，順便也介紹了一些應用。

線性轉換的幾何學解釋

讓我們先看一些簡單的2x2的矩陣惨好。第一個例子是如下對角矩陣(diagonal matad-images.jianshu.io/upload_images/10000468-3f74806ef09d3c2c?imageMogr2/auto-orient/strip%7CimageView2/2/w/1240)

從幾何學角度煌茴，我們可以把類似矩陣看作是一種轉換：在平面上取一點(x, y)宏悦，然后通過矩陣相乘创淡，把此點轉換到另外一點:

image

此轉換效果是：平面在水平方向伸展了3倍，垂直方向無變化刁品。

image

現(xiàn)在我們再看矩陣

image

它產生以下效果：

image

此轉換看上去不像前面的簡單明了龄句。但是讓我們把網(wǎng)格(grid回论，http://mathworld.wolfram.com/Grid.html)旋轉45度散罕，看看會發(fā)生什么情況。

image

啊哈傀蓉。我們發(fā)現(xiàn)這個新網(wǎng)格的轉換與第一張圖的網(wǎng)格轉換一樣：乘以一個對角矩陣欧漱，網(wǎng)格在某個方向上拉伸了3倍。

因為矩陣M是對稱的葬燎，即M的轉置(transpose误甚，沿著對角翻轉)等于M，所以這只是一類特殊的情況谱净。如果我們有一2x2的對稱矩陣窑邦，通常會產生以下轉換效果：先在domain中旋轉網(wǎng)格，然后在兩個方向上拉伸(stretch)或者反射(reflect)壕探。換句話講冈钦，對稱矩陣的行為像對角矩陣（除了旋轉）。

說得更數(shù)學化些：給定一對稱矩陣M, 我們可能會找到一由正交向量(orthogonal vector) v_i 組成的集合浩蓉，M*****v_i是v_i的標量倍(scalarmultiple)派继，也就是說

M****v_i = λ_iv**_i

其中λ_i 是一標量宾袜。

從幾何角度來說捻艳，這意味著當向量v_i乘以M后，它被簡單的拉伸(stretch)或者反射(reflect)了庆猫。

正因為這個特性认轨，我把向量v_i 稱為矩陣M的特征向量（eigenvector）；標量λ_i 稱為特征值(eigenvalue)月培。一個容易驗證的重要的事實是：對稱矩陣的特征向量（帶不同特征值）是正交的嘁字。

如果用對稱矩陣的特征向量按放(align)網(wǎng)格，這個矩陣會再拉伸(stretch)或者反射(reflect)這個（被旋轉后的）網(wǎng)格杉畜，如同它對自己的特征向量一樣纪蜒。

這個線性轉換的幾何描述屬于簡單的一類：網(wǎng)格只是在某個方向被拉伸了。對于更加普通的矩陣此叠，我們會問這么一個問題：我們能否找到一個正交網(wǎng)格（兩組線相互垂直的）纯续，能轉換到另外一個正交網(wǎng)格。讓我們看最后一個例子灭袁，它使用一非對稱矩陣：

image

這個矩陣產生一個稱為 “修剪”（shear）的幾何效果猬错。

image

沿著水平軸，容易找到一組特征向量茸歧。但是倦炒，上面的圖片顯示這些特征向量不能用于創(chuàng)建正交的網(wǎng)格（能轉換到另外一個正交網(wǎng)格），雖然如此软瞎，我們還是先看一下我們旋轉這個網(wǎng)格30度會發(fā)生什么逢唤。

image

注意由平行四邊形構成的位于坐標原點的夾角在右邊增加了拉讯。讓我們把網(wǎng)格旋轉60度。

image

嗯智玻。右邊的網(wǎng)格看上去是正交的了遂唧。實際上，通過在domain中旋轉網(wǎng)格大約58.28度吊奢，兩個網(wǎng)格就全是正交的了盖彭。

image

奇異值分解(Singular Value Decomposition)

這就是SVD在2x2矩陣下的幾何學本質：對于任意的2x2矩陣，我們能找到一個正交的網(wǎng)格(grid)页滚，它被轉換到了另外一個正交網(wǎng)格召边。

我們使用向量來描述這個現(xiàn)象：如果我們通過某種方式挑出兩個單位向量（unit vector）v₁和v₂，它們是正交的裹驰，向量Mv₁ 和Mv₂ 也是正交的隧熙。

image

我們用u₁和u₂代表向量Mv₁ 和Mv₂ 方向的單位向量，用σ₁ andσ₂代表向量Mv₁ 和Mv₂的長度幻林，它們描述網(wǎng)格在這些方向上的拉伸量贞盯。這些數(shù)字稱為M的奇異值(singularvalue，在這個例子里沪饺，奇異值是golden ratio 和它的reciprocal,但是在這里不重要)躏敢。

image

因此我們有

Mv₁ = σ₁u₁

Mv₂ = σ₂u₂

現(xiàn)在我們可簡單說一下矩陣M是如何處理普通向量x的。因為單位向量v₁和v₂是正交的（譯者注：形成了一規(guī)范正交基整葡，****orthonomal basis）件余，所以我們有：

x = (v₁?x)v1 + (v2?x)v2

（譯者注：x ?v1 = (v1?x) v1?v1 + (v2?x)v2?v1 = (v1?x) 1+0 = v1?x=x*?v1）

這意味著

Mx = (v₁?x)M****v₁ + (v₂?x)Mv**₂

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

記住dot product 操作可以用矩陣轉置實現(xiàn)：

v?x = v^Tx

從而導出

Mx = u₁σ₁v₁^Tx +u₂σ₂v₂^Tx**

M = u₁σ₁v₁^T +u₂σ₂v₂^T**

上述表達式可以簡寫成

M = UΣV^T

其中U 是由向量u₁ 和u₂（作為列）組成的矩陣,Σ 是對角矩陣，對角線上的值是σ₁ 和σ₂,V 是向量v₁和v₂(作為列)組成的矩陣. 矩陣V的上標T 代表V的矩陣轉置遭居。

上面顯示了如何將矩陣M分解為三矩陣的積: V描述在domain中的規(guī)范正交基（orthonomal basis）啼器，U描述co-domain中的規(guī)范正交基，Σ描述在V中的向量在U中拉伸量俱萍。

譯者注：

1. 如果把每個矩陣看作一種轉換動作端壳，可以描述為：先旋轉，然后拉伸展枪蘑，然后再一次旋轉损谦。

2．所以SVD的Idea是：如果我們在向量空間Rⁿ 和R^m上選擇正確的基(basis)，每個mxn矩陣均可對角線化(diagonalized)腥寇。計算的問題就是如何找到這些basis成翩。

如何作奇異值分解？

奇異值分解的強大之處在于適用于任何矩陣赦役。那我們是如何做到呢麻敌？讓我們回顧前面的一個例子，在domain中加上一個單位圓掂摔。在co-domain中它將是橢圓术羔，它的長軸(major axis)和短軸(minoraxis) 定義了在co-domain中的正交網(wǎng)格赢赊。

image

注意長軸短軸分別由Mv₁和Mv₂定義。因此這兩個向量是單位圓上向量（在橢圓上的）最長和最短的向量级历。

image

換句話講释移，單位圓上的函數(shù)|Mx| 在x=v₁時有最大值，x=v₂有最小值寥殖。這把問題降低到一個十分標準的微積分問題：我們希望在單位圓上優(yōu)化一個函數(shù)玩讳。可以證明函數(shù)的臨界點在矩陣M^TM的特征向量上嚼贡。因此這個矩陣是對稱的熏纯，對應于不同的特征值的特征向量將是正交的。這就產生了一組向量v_i粤策。

奇異值定義為σ_i = |Mv_i|, 向量u_i則是Mv_i方向上的單位向量樟澜。但是為什么這些u_i是正交的呢？

要解釋這個叮盘，我們假設σ_i and σ_j 是兩個不同的奇異值秩贰。于是有

Mv_i = σ_iu_i

Mv_j = σ_ju_j

讓我們先看表達式Mv_i?Mv_j。 為了方便先假設它們的奇異值是非零的柔吼。另外一方面毒费，v_i和v_j是對稱矩陣M^TM的特征向量，它們是相互正交的嚷堡，結果是這個表達式等于零蝗罗。

Mv_i?Mv_j =v_i^TM^TMv_j = v_i?M^TMv_j =v_i?λ_jv_j = λ_jv_i?v_j =0.**

另外一方面艇棕，我們有

Mv_i?Mv_j =σ_iσ_ju_i?u_j =0**

因此u_i和u_j是正交的蝌戒。到此為止，我們發(fā)現(xiàn)了一組正交向量v_i沼琉，它能轉換為另外一組正交向量u_i北苟。(v_i對應的)奇異值描述了在不同方向上的拉伸程度。

在實際應用中打瘪，這不是為矩陣尋找奇異值分解的過程友鼻，因為這種方法效率不高，或者說數(shù)值計算上是低效的闺骚。

另外一個例子

讓我們看一矩陣：

image

這個矩陣在幾何上的效果如下圖：

image

| | | |

在這種情況下彩扔，第二個奇異值是0，因此我們寫成

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

（譯者注：M = u1σ1 v1^T+ u2σ2 v2^T）

換句話講僻爽，如果其中的一些奇異值是0虫碉，對應的項就不出現(xiàn)在M的分解中。這樣胸梆，我們發(fā)現(xiàn)M的rank（矩陣秩敦捧，它等于線性轉換后的維度）就等于非0奇異值的數(shù)量须板。

數(shù)據(jù)壓縮

奇異值分解能讓數(shù)據(jù)表示更加有效。例如兢卵，我們想傳輸以下圖片习瑰，含15x25個黑或白的像素點。

image

因為圖片中只有三種列秽荤，就像下圖顯示的甜奄，也許我們能用更加緊湊的形式。

image

我們用0代表黑色窃款，1代表白色贺嫂，用一個15x25的矩陣表示這個圖像。如此一來雁乡，便有了375個元素的矩陣：

image

如果我們對上述M作奇異值分解第喳，會發(fā)現(xiàn)只有三個非0的奇異值

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

因此，矩陣可表示為：

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

這意味著我們有：三個向量v_i踱稍，每個有15 個元素曲饱；三個向量u_i，每個有25個元素珠月；三個奇異值σ_i扩淀。這意味著我們能只用123個數(shù)字代表矩陣（153+253+3=123），而不是375個啤挎。就這樣奇異值分解幫助我們發(fā)現(xiàn)了矩陣中存在的冗余驻谆，并提供了剔除它們的方法。

為什么只有三個非零的奇異值呢庆聘？前面講過胜臊，非0奇異值的數(shù)量等于矩陣的rank。在這個例子中伙判，矩陣只有三個線性獨立的列象对，也就是它的rank=3。

降噪

前面的例子顯示我們是如何利用“很多奇異值是0”來解決問題的宴抚。通常大的奇異值對應著有趣信息多的所在勒魔。比如，設想我們用一個掃描儀把這個圖像輸入到電腦菇曲。但是冠绢，掃描儀在圖像中引入了一些非理想的數(shù)據(jù)（通常稱為“噪音”）。

image

與前面的例子一樣我們用15x25的矩陣表示數(shù)據(jù)常潮，然后進行奇異值分解弟胀。可發(fā)現(xiàn)以下奇異值

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

顯然，前三個是最重要的（最大）邮利，我們可以假設其他小的奇異值是噪音造成的弥雹，所以近似表示矩陣如下

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

這導致了以下改進的圖像。

image

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

在收集數(shù)據(jù)的時候會遇到噪音數(shù)據(jù)：無論如何好的器材延届，測量經常會有誤差剪勿。因為大的奇異值(singular values)對應了矩陣中的重要特性。因此一旦數(shù)據(jù)收集完成方庭，便自然可用SVD來研究厕吉。

例如，我們收集了以下數(shù)據(jù)

image

我們可能會把這些數(shù)據(jù)放到一個矩陣中

-1.03 0.74 -0.02 0.51 -1.31 0.99 0.69 -0.12 -0.72 1.11

-2.23 1.61 -0.02 0.88 -2.39 2.02 1.62 -0.35 -1.67 2.46

然后運行SVD械念，我們發(fā)現(xiàn)如下奇異值

σ₁ = 6.04

σ₂ = 0.22

其中一個奇異值如此之大头朱，可以安全地假設小的σ₂ 是由于數(shù)據(jù)噪音引起的，這個奇異值在理想情況下應該是0龄减。在這則案例中项钮，矩陣的rank 等于1，意味著所有數(shù)據(jù)應該在向量u_i定義的這條線上希停。

image

這個簡單的例子說出了PCA（principal component analysis）起源烁巫，它是一組使用奇異值剔除數(shù)據(jù)中依賴和冗余的技術。

同樣宠能，SVD可用于檢測數(shù)據(jù)中的存在的分組(group)亚隙。這就可以解釋，為什么SVD正用于改進netflix的電影推薦系統(tǒng)违崇。系統(tǒng)會根據(jù)你的電影評分（觀看過的）阿弃，把你分到某個組中，組內人員的評分與你的相似羞延，然后系統(tǒng)就向你推薦組內其他人評分高的電影渣淳。

參考文獻

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

  Strang's book is something of a classic though some may find it to be a little too formal.

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

  Authoritative, yet highly readable. Older versions are available online.

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

  Kalman's article, like this one, aims to improve the profile of the singular value decomposition. It also a description of how least-squares computations are facilitated by the decomposition.

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

  This article describes Netflix's prize competition as well as some of the challenges associated with it.