導讀：「金三銀四」面試求職季，今天，小編和大家分享一道關於推薦系統相關的面試題，如何通俗理解奇異值分解？讓我們一起來看看如何解析這道題吧。
特徵值和奇異值在大部分人的印象中，往往是停留在純粹的數學計算中。而且線性代數或者矩陣論裡面，也很少講任何跟特徵值與奇異值有關的應用背景。
奇異值分解是一個有著很明顯的物理意義的一種方法，它可以將一個比較複雜的矩陣用更小更簡單的幾個子矩陣的相乘來表示，這些小矩陣描述的是矩陣的重要的特性。就像是描述一個人一樣，給別人描述說這個人長得濃眉大眼，方臉，絡腮鬍，而且帶個黑框的眼鏡，這樣寥寥的幾個特徵，就讓別人腦海裡面就有一個較為清楚的認識，實際上，人臉上的特徵是有著無數種的，之所以能這麼描述，是因為人天生就有著非常好的抽取重要特徵的能力，讓機器學會抽取重要的特徵，SVD是一個重要的方法。
在機器學習領域，有相當多的應用與奇異值都可以扯上關係，比如做feature reduction的PCA，做數據壓縮（以圖像壓縮為代表）的算法，還有做搜尋引擎語義層次檢索的LSI（Latent Semantic Indexing）
一、特徵值與奇異值
特徵值分解和奇異值分解在機器學習領域都是屬於滿地可見的方法。兩者有著很緊密的關係，接下來會談到特徵值分解和奇異值分解的目的都是一樣，就是提取出一個矩陣最重要的特徵。先談特徵值分解。
1.1 特徵值
如果說一個向量v是方陣A的特徵向量，將一定可以表示成下面的形式：
這時候λ就被稱為特徵向量v對應的特徵值，一個矩陣的一組特徵向量是一組正交向量。特徵值分解是將一個矩陣分解成下面的形式：
其中Q是這個矩陣A的特徵向量組成的矩陣，Σ是一個對角陣，每一個對角線上的元素就是一個特徵值。我這裡引用了一些參考文獻中的內容來說明一下。
首先，要明確的是，一個矩陣其實就是一個線性變換，因為一個矩陣乘以一個向量後得到的向量，其實就相當於將這個向量進行了線性變換。比如說下面的一個矩陣：
它其實對應的線性變換是下面的形式：
因為這個矩陣M乘以一個向量(x,y)的結果是：
上面的矩陣是對稱的，所以這個變換是一個對x，y軸的方向一個拉伸變換（每一個對角線上的元素將會對一個維度進行拉伸變換，當值>1時，是拉長，當值<1時時縮短），當矩陣不是對稱的時候，假如說矩陣是下面的樣子：
它所描述的變換是下面的樣子：
這其實是在平面上對一個軸進行的拉伸變換（如藍色的箭頭所示），在圖中，藍色的箭頭是一個最主要的變化方向（變化方向可能有不止一個），如果我們想要描述好一個變換，那我們就描述好這個變換主要的變化方向就好了。反過頭來看看之前特徵值分解的式子，分解得到的Σ矩陣是一個對角陣，裡面的特徵值是由大到小排列的，這些特徵值所對應的特徵向量就是描述這個矩陣變化方向（從主要的變化到次要的變化排列）。
考慮更一般的非對稱矩陣
很遺憾，此時我們再也找不到一組網格，使得矩陣作用在該網格上之後只有拉伸變換（找不到背後的數學原因是對一般非對稱矩陣無法保證在實數域上可對角化，不明白也不要在意）。
我們退而求其次，找一組網格，使得矩陣作用在該網格上之後允許有拉伸變換和旋轉變換，但要保證變換後的網格依舊互相垂直，這是可以做到的，如下圖所示。
簡言之，當矩陣是高維的情況下，那麼這個矩陣就是高維空間下的一個線性變換，這個變換也同樣有很多的變換方向，我們通過特徵值分解得到的前N個特徵向量，那麼就對應了這個矩陣最主要的N個變化方向。我們利用這前N個變化方向，就可以近似這個矩陣（變換）。
也就是之前說的：提取這個矩陣最重要的特徵。總結一下，特徵值分解可以得到特徵值與特徵向量，特徵值表示的是這個特徵到底有多重要，而特徵向量表示這個特徵是什麼，可以將每一個特徵向量理解為一個線性的子空間，我們可以利用這些線性的子空間幹很多的事情。不過，特徵值分解也有很多的局限，比如說變換的矩陣必須是方陣。
下面我們就可以自然過渡到奇異值分解的引入。
1.2 奇異值
下面談談奇異值分解。特徵值分解是一個提取矩陣特徵很不錯的方法，但是它只是對方陣而言的，在現實的世界中，我們看到的大部分矩陣都不是方陣，比如說有N個學生，每個學生有M科成績，這樣形成的一個N * M的矩陣就不可能是方陣，我們怎樣才能描述這樣普通的矩陣呢的重要特徵呢？奇異值分解可以用來幹這個事情，奇異值分解是一個能適用於任意的矩陣的一種分解的方法：
假設A是一個N * M的矩陣，那麼得到的U是一個N * N的方陣（裡面的向量是正交的，U裡面的向量稱為左奇異向量），Σ是一個N * M的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值），V』(V的轉置)是一個N * N的矩陣，裡面的向量也是正交的，V裡面的向量稱為右奇異向量），從圖片來反映幾個相乘的矩陣的大小可得下面的圖片
那麼奇異值和特徵值是怎麼對應起來的呢？首先，我們將一個矩陣A的轉置 * A，將會得到一個方陣，我們用這個方陣求特徵值可以得到：
這裡得到的v，就是我們上面的右奇異向量。此外我們還可以得到：
這裡的σ就是上面說的奇異值，u就是上面說的左奇異向量。奇異值σ跟特徵值類似，在矩陣Σ中也是從大到小排列，而且σ的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就佔了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，這裡定義一下部分奇異值分解：
r是一個遠小於m、n的數，這樣矩陣的乘法看起來像是下面的樣子：
右邊的三個矩陣相乘的結果將會是一個接近於A的矩陣，在這兒，r越接近於n，則相乘的結果越接近於A。而這三個矩陣的面積之和（在存儲觀點來說，矩陣面積越小，存儲量就越小）要遠遠小於原始的矩陣A，我們如果想要壓縮空間來表示原矩陣A，我們存下這裡的三個矩陣：U、Σ、V就好了。
說句大白話，稱作「奇異值」可能無法顧名思義迅速理解其本質，那咱們換個說法，稱作「主特徵值」，你可能就迅速瞭然了。
而奇異值分解的幾何含義為：對於任何的一個矩陣，我們要找到一組兩兩正交單位向量序列，使得矩陣作用在此向量序列上後得到新的向量序列保持兩兩正交。
繼續拿1.1節的例子進一步闡述，奇異值的幾何含義為：這組變換後的新的向量序列的長度。
奇異值的計算是一個難題，是一個O(N^3)的算法。在單機的情況下當然是沒問題的，matlab在一秒鐘內就可以算出1000 * 1000的矩陣的所有奇異值，但是當矩陣的規模增長的時候，計算的複雜度呈3次方增長，就需要並行計算參與了。Google的吳軍老師在數學之美系列談到SVD的時候，說起Google實現了SVD的並行化算法，說這是對人類的一個貢獻，但是也沒有給出具體的計算規模，也沒有給出太多有價值的信息。
其實SVD還是可以用並行的方式去實現的，在解大規模的矩陣的時候，一般使用迭代的方法，當矩陣的規模很大（比如說上億）的時候，迭代的次數也可能會上億次，如果使用Map-Reduce框架去解，則每次Map-Reduce完成的時候，都會涉及到寫文件、讀文件的操作。個人猜測Google雲計算體系中除了Map-Reduce以外應該還有類似於MPI的計算模型，也就是節點之間是保持通信，數據是常駐在內存中的，這種計算模型比Map-Reduce在解決迭代次數非常多的時候，要快了很多倍。
Lanczos迭代就是一種解對稱方陣部分特徵值的方法（之前談到了，解A』* A得到的對稱方陣的特徵值就是解A的右奇異向量），是將一個對稱的方程化為一個三對角矩陣再進行求解。按網上的一些文獻來看，Google應該是用這種方法去做的奇異值分解的。請見Wikipedia上面的一些引用的論文，如果理解了那些論文，也「幾乎」可以做出一個SVD了。
二、奇異值的直觀應用
2.1 女神圖片壓縮
下面，咱們從女神上野樹裡（Ueno Juri）的一張像素為高度450*寬度333的照片，來直觀理解奇異值在物理上到底代表什麼意義（請屏幕前的痴漢暫停舔屏）。
我們都知道，圖片實際上對應著一個矩陣，矩陣的大小就是像素大小，比如這張圖對應的矩陣階數就是450*333，矩陣上每個元素的數值對應著像素值。我們記這個像素矩陣為A 現在我們對矩陣A進行奇異值分解。直觀上，奇異值分解將矩陣分解成若干個秩一矩陣之和，用公式表示就是：
如果不滿足的話重新排列順序即可，這無非是編號順序的問題。既然奇異值有從大到小排列的順序，我們自然要問，如果只保留大的奇異值，捨去較小的奇異值，這樣(1)式裡的等式自然不再成立，那會得到怎樣的矩陣——也就是圖像？
結果就是完全看不清是啥……我們試著多增加幾項進來：
再作圖
隱約可以辨別這是短髮伽椰子的臉……但還是很模糊，畢竟我們只取了5個奇異值而已。下面我們取20個奇異值試試，也就是(1)式等式右邊取前20項構成
雖然還有些馬賽克般的模糊，但我們總算能辨別出這是Juri醬的臉。當我們取到(1)式等式右邊前50項時：
奇異值往往對應著矩陣中隱含的重要信息，且重要性和奇異值大小正相關。每個矩陣A都可以表示為一系列秩為1的「小矩陣」之和，而奇異值則衡量了這些「小矩陣」對於A的權重。
2.2 圖像去噪
在圖像處理領域，奇異值不僅可以應用在數據壓縮上，還可以對圖像去噪。如果一副圖像包含噪聲，我們有理由相信那些較小的奇異值就是由於噪聲引起的。當我們強行令這些較小的奇異值為0時，就可以去除圖片中的噪聲。如下是一張25*15的圖像
但往往我們只能得到如下帶有噪聲的圖像（和無噪聲圖像相比，下圖的部分白格子中帶有灰色）：
通過奇異值分解，我們發現矩陣的奇異值從大到小分別為：14.15，4.67，3.00，0.21，……，0.05。除了前3個奇異值較大以外，其餘奇異值相比之下都很小。強行令這些小奇異值為0，然後只用前3個奇異值構造新的矩陣，得到
可以明顯看出噪聲減少了（白格子上灰白相間的圖案減少了）。奇異值分解還廣泛的用於主成分分析（Principle Component Analysis，簡稱PCA）和推薦系統（如Netflex的電影推薦系統）等。在這些應用領域，奇異值也有相應的意義。
參考文獻
1 https://www.cnblogs.com/LeftNotEasy/archive/2011/01/19/svd-and-applications.html
2 https://www.zhihu.com/question/22237507 3 We Recommend a Singular Value Decomposition（Feature Column from the AMS）
————
編輯 ∑Pluto
來源：七月算法
更多精彩：
☞泰勒定理的奇聞軼事
☞丘成桐：漫談微分幾何
☞Leibniz 如何想出微積分？（一）
☞線性相關和秩的物理意義
☞數學史上你認為最醜陋的公式是什麼？
☞陶哲軒談什麼是好的數學
☞田淵棟：數學的用處（下篇）
☞你絕對沒想過原來數學家這麼流氓，一言不合就進行暴力證明
☞世界上最牛的五篇博士論文
☞數學中有哪些巧合讓人眼前一亮？
☞算法立功！清華畢業教授美國被搶車，警察無能為力自己用「貪心算法」找回
☞學術史上的奇文：怎樣用數學抓獅子
☞臺大教授的反思：最難的一課 我們卻沒教給學生
☞麻省理工學院(MIT)研究生學習指導—— 怎樣做研究生
☞分享 數學，常識和運氣 ——投資大師詹姆斯·西蒙斯2010年在MIT的講座
算法數學之美微信公眾號歡迎賜稿
稿件涉及數學、物理、算法、計算機、編程等相關領域，經採用我們將奉上稿酬。
投稿郵箱：math_alg@163.com