↑ 點(diǎn)擊藍(lán)字?關(guān)注極市平臺奇異值分解（Singular Value Decomposition）是線性代數(shù)中一種重要的矩陣分解，是在機(jī)器學(xué)習(xí)領(lǐng)域廣泛應(yīng)用的算法,本文對奇異值分解的概念進(jìn)行了介紹，以圖像舉例解釋了奇異值分解的應(yīng)用。?>>加入極市CV技術(shù)交流群，走在計(jì)算機(jī)視覺的最前沿
特征值和奇異值在大部分人的印象中，往往是停留在純粹的數(shù)學(xué)計(jì)算中。而且線性代數(shù)或者矩陣論里面，也很少講任何跟特征值與奇異值有關(guān)的應(yīng)用背景。奇異值分解是一個(gè)有著很明顯的物理意義的一種方法，它可以將一個(gè)比較復(fù)雜的矩陣用更小更簡單的幾個(gè)子矩陣的相乘來表示，這些小矩陣描述的是矩陣的重要的特性。就像是描述一個(gè)人一樣，給別人描述說這個(gè)人長得濃眉大眼，方臉，絡(luò)腮胡，而且?guī)€(gè)黑框的眼鏡，這樣寥寥的幾個(gè)特征，就讓別人腦海里面就有一個(gè)較為清楚的認(rèn)識，實(shí)際上，人臉上的特征是有著無數(shù)種的，之所以能這么描述，是因?yàn)槿颂焐陀兄浅：玫某槿≈匾卣鞯哪芰?，讓機(jī)器學(xué)會抽取重要的特征，SVD是一個(gè)重要的方法。在機(jī)器學(xué)習(xí)領(lǐng)域，有相當(dāng)多的應(yīng)用與奇異值都可以扯上關(guān)系，比如做feature reduction的PCA，做數(shù)據(jù)壓縮（以圖像壓縮為代表）的算法，還有做搜索引擎語義層次檢索的LSI（Latent Semantic Indexing）?特征值分解和奇異值分解在機(jī)器學(xué)習(xí)領(lǐng)域都是屬于滿地可見的方法。兩者有著很緊密的關(guān)系，接下來會談到特征值分解和奇異值分解的目的都是一樣，就是提取出一個(gè)矩陣最重要的特征。先談特征值分解。如果說一個(gè)向量v是方陣A的特征向量，將一定可以表示成下面的形式：
這時(shí)候λ就被稱為特征向量v對應(yīng)的特征值，一個(gè)矩陣的一組特征向量是一組正交向量。特征值分解是將一個(gè)矩陣分解成下面的形式：其中Q是這個(gè)矩陣A的特征向量組成的矩陣，Σ是一個(gè)對角陣，每一個(gè)對角線上的元素就是一個(gè)特征值。我這里引用了一些參考文獻(xiàn)中的內(nèi)容來說明一下。首先，要明確的是，一個(gè)矩陣其實(shí)就是一個(gè)線性變換，因?yàn)橐粋€(gè)矩陣乘以一個(gè)向量后得到的向量，其實(shí)就相當(dāng)于將這個(gè)向量進(jìn)行了線性變換。比如說下面的一個(gè)矩陣：它其實(shí)對應(yīng)的線性變換是下面的形式：因?yàn)檫@個(gè)矩陣M乘以一個(gè)向量(x,y)的結(jié)果是：上面的矩陣是對稱的，所以這個(gè)變換是一個(gè)對x，y軸的方向一個(gè)拉伸變換（每一個(gè)對角線上的元素將會對一個(gè)維度進(jìn)行拉伸變換，當(dāng)值>1時(shí)，是拉長，當(dāng)值<1時(shí)時(shí)縮短），當(dāng)矩陣不是對稱的時(shí)候，假如說矩陣是下面的樣子：這其實(shí)是在平面上對一個(gè)軸進(jìn)行的拉伸變換（如藍(lán)色的箭頭所示），在圖中，藍(lán)色的箭頭是一個(gè)最主要的變化方向（變化方向可能有不止一個(gè)），如果我們想要描述好一個(gè)變換，那我們就描述好這個(gè)變換主要的變化方向就好了。反過頭來看看之前特征值分解的式子，分解得到的Σ矩陣是一個(gè)對角陣，里面的特征值是由大到小排列的，這些特征值所對應(yīng)的特征向量就是描述這個(gè)矩陣變化方向（從主要的變化到次要的變化排列）。考慮更一般的非對稱矩陣
很遺憾，此時(shí)我們再也找不到一組網(wǎng)格，使得矩陣作用在該網(wǎng)格上之后只有拉伸變換（找不到背后的數(shù)學(xué)原因是對一般非對稱矩陣無法保證在實(shí)數(shù)域上可對角化，不明白也不要在意）。我們退而求其次，找一組網(wǎng)格，使得矩陣作用在該網(wǎng)格上之后允許有拉伸變換和旋轉(zhuǎn)變換，但要保證變換后的網(wǎng)格依舊互相垂直，這是可以做到的，如下圖所示。簡言之，當(dāng)矩陣是高維的情況下，那么這個(gè)矩陣就是高維空間下的一個(gè)線性變換，這個(gè)變換也同樣有很多的變換方向，我們通過特征值分解得到的前N個(gè)特征向量，那么就對應(yīng)了這個(gè)矩陣最主要的N個(gè)變化方向。我們利用這前N個(gè)變化方向，就可以近似這個(gè)矩陣（變換）。也就是之前說的：提取這個(gè)矩陣最重要的特征。總結(jié)一下，特征值分解可以得到特征值與特征向量，特征值表示的是這個(gè)特征到底有多重要，而特征向量表示這個(gè)特征是什么，可以將每一個(gè)特征向量理解為一個(gè)線性的子空間，我們可以利用這些線性的子空間干很多的事情。不過，特征值分解也有很多的局限，比如說變換的矩陣必須是方陣。下面談?wù)勂娈愔捣纸狻Ｌ卣髦捣纸馐且粋€(gè)提取矩陣特征很不錯(cuò)的方法，但是它只是對方陣而言的，在現(xiàn)實(shí)的世界中，我們看到的大部分矩陣都不是方陣，比如說有N個(gè)學(xué)生，每個(gè)學(xué)生有M科成績，這樣形成的一個(gè)N * M的矩陣就不可能是方陣，我們怎樣才能描述這樣普通的矩陣呢的重要特征呢？奇異值分解可以用來干這個(gè)事情，奇異值分解是一個(gè)能適用于任意的矩陣的一種分解的方法：假設(shè)A是一個(gè)N * M的矩陣，那么得到的U是一個(gè)N * N的方陣（里面的向量是正交的，U里面的向量稱為左奇異向量），Σ是一個(gè)N * M的矩陣（除了對角線的元素都是0，對角線上的元素稱為奇異值），V’(V的轉(zhuǎn)置)是一個(gè)N * N的矩陣，里面的向量也是正交的，V里面的向量稱為右奇異向量），從圖片來反映幾個(gè)相乘的矩陣的大小可得下面的圖片那么奇異值和特征值是怎么對應(yīng)起來的呢？首先，我們將一個(gè)矩陣A的轉(zhuǎn)置 * A，將會得到一個(gè)方陣，我們用這個(gè)方陣求特征值可以得到：這里得到的v，就是我們上面的右奇異向量。此外我們還可以得到：這里的σ就是上面說的奇異值，u就是上面說的左奇異向量。奇異值σ跟特征值類似，在矩陣Σ中也是從大到小排列，而且σ的減少特別的快，在很多情況下，前10%甚至1%的奇異值的和就占了全部的奇異值之和的99%以上了。也就是說，我們也可以用前r大的奇異值來近似描述矩陣，這里定義一下部分奇異值分解：r是一個(gè)遠(yuǎn)小于m、n的數(shù)，這樣矩陣的乘法看起來像是下面的樣子：右邊的三個(gè)矩陣相乘的結(jié)果將會是一個(gè)接近于A的矩陣，在這兒，r越接近于n，則相乘的結(jié)果越接近于A。而這三個(gè)矩陣的面積之和（在存儲觀點(diǎn)來說，矩陣面積越小，存儲量就越?。┮h(yuǎn)遠(yuǎn)小于原始的矩陣A，我們?nèi)绻胍獕嚎s空間來表示原矩陣A，我們存下這里的三個(gè)矩陣：U、Σ、V就好了。說句大白話，稱作「奇異值」可能無法顧名思義迅速理解其本質(zhì)，那咱們換個(gè)說法，稱作「主特征值」，你可能就迅速了然了。而奇異值分解的幾何含義為：對于任何的一個(gè)矩陣，我們要找到一組兩兩正交單位向量序列，使得矩陣作用在此向量序列上后得到新的向量序列保持兩兩正交。繼續(xù)拿1.1節(jié)的例子進(jìn)一步闡述，奇異值的幾何含義為：這組變換后的新的向量序列的長度。奇異值的計(jì)算是一個(gè)難題，是一個(gè)O(N^3)的算法。在單機(jī)的情況下當(dāng)然是沒問題的，matlab在一秒鐘內(nèi)就可以算出1000 * 1000的矩陣的所有奇異值，但是當(dāng)矩陣的規(guī)模增長的時(shí)候，計(jì)算的復(fù)雜度呈3次方增長，就需要并行計(jì)算參與了。Google的吳軍老師在數(shù)學(xué)之美系列談到SVD的時(shí)候，說起Google實(shí)現(xiàn)了SVD的并行化算法，說這是對人類的一個(gè)貢獻(xiàn)，但是也沒有給出具體的計(jì)算規(guī)模，也沒有給出太多有價(jià)值的信息。其實(shí)SVD還是可以用并行的方式去實(shí)現(xiàn)的，在解大規(guī)模的矩陣的時(shí)候，一般使用迭代的方法，當(dāng)矩陣的規(guī)模很大（比如說上億）的時(shí)候，迭代的次數(shù)也可能會上億次，如果使用Map-Reduce框架去解，則每次Map-Reduce完成的時(shí)候，都會涉及到寫文件、讀文件的操作。個(gè)人猜測Google云計(jì)算體系中除了Map-Reduce以外應(yīng)該還有類似于MPI的計(jì)算模型，也就是節(jié)點(diǎn)之間是保持通信，數(shù)據(jù)是常駐在內(nèi)存中的，這種計(jì)算模型比Map-Reduce在解決迭代次數(shù)非常多的時(shí)候，要快了很多倍。Lanczos迭代就是一種解對稱方陣部分特征值的方法（之前談到了，解A’* A得到的對稱方陣的特征值就是解A的右奇異向量），是將一個(gè)對稱的方程化為一個(gè)三對角矩陣再進(jìn)行求解。按網(wǎng)上的一些文獻(xiàn)來看，Google應(yīng)該是用這種方法去做的奇異值分解的。請見Wikipedia上面的一些引用的論文，如果理解了那些論文，也“幾乎”可以做出一個(gè)SVD了。下面，咱們從女神上野樹里（Ueno Juri）的一張像素為高度450*寬度333的照片，來直觀理解奇異值在物理上到底代表什么意義（請屏幕前的癡漢暫停舔屏）。我們都知道，圖片實(shí)際上對應(yīng)著一個(gè)矩陣，矩陣的大小就是像素大小，比如這張圖對應(yīng)的矩陣階數(shù)就是450*333，矩陣上每個(gè)元素的數(shù)值對應(yīng)著像素值。我們記這個(gè)像素矩陣為A 現(xiàn)在我們對矩陣A進(jìn)行奇異值分解。直觀上，奇異值分解將矩陣分解成若干個(gè)秩一矩陣之和，用公式表示就是：如果不滿足的話重新排列順序即可，這無非是編號順序的問題。既然奇異值有從大到小排列的順序，我們自然要問，如果只保留大的奇異值，舍去較小的奇異值，這樣(1)式里的等式自然不再成立，那會得到怎樣的矩陣——也就是圖像？結(jié)果就是完全看不清是啥……我們試著多增加幾項(xiàng)進(jìn)來：隱約可以辨別這是短發(fā)伽椰子的臉……但還是很模糊，畢竟我們只取了5個(gè)奇異值而已。下面我們?nèi)?0個(gè)奇異值試試，也就是(1)式等式右邊取前20項(xiàng)構(gòu)成
雖然還有些馬賽克般的模糊，但我們總算能辨別出這是Juri醬的臉。當(dāng)我們?nèi)〉?1)式等式右邊前50項(xiàng)時(shí)：奇異值往往對應(yīng)著矩陣中隱含的重要信息，且重要性和奇異值大小正相關(guān)。每個(gè)矩陣A都可以表示為一系列秩為1的“小矩陣”之和，而奇異值則衡量了這些“小矩陣”對于A的權(quán)重。在圖像處理領(lǐng)域，奇異值不僅可以應(yīng)用在數(shù)據(jù)壓縮上，還可以對圖像去噪。如果一副圖像包含噪聲，我們有理由相信那些較小的奇異值就是由于噪聲引起的。當(dāng)我們強(qiáng)行令這些較小的奇異值為0時(shí)，就可以去除圖片中的噪聲。如下是一張25*15的圖像
但往往我們只能得到如下帶有噪聲的圖像（和無噪聲圖像相比，下圖的部分白格子中帶有灰色）：通過奇異值分解，我們發(fā)現(xiàn)矩陣的奇異值從大到小分別為：14.15，4.67，3.00，0.21，……，0.05。除了前3個(gè)奇異值較大以外，其余奇異值相比之下都很小。強(qiáng)行令這些小奇異值為0，然后只用前3個(gè)奇異值構(gòu)造新的矩陣，得到可以明顯看出噪聲減少了（白格子上灰白相間的圖案減少了）。奇異值分解還廣泛的用于主成分分析（Principle Component Analysis，簡稱PCA）和推薦系統(tǒng)（如Netflex的電影推薦系統(tǒng)）等。在這些應(yīng)用領(lǐng)域，奇異值也有相應(yīng)的意義。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）
推薦閱讀
添加極市小助手微信（ID : cvmart2），備注：姓名-學(xué)校/公司-研究方向-城市（如：小極-北大-目標(biāo)檢測-深圳），即可申請加入極市目標(biāo)檢測/圖像分割/工業(yè)檢測/人臉/醫(yī)學(xué)影像/3D/SLAM/自動駕駛/超分辨率/姿態(tài)估計(jì)/ReID/GAN/圖像增強(qiáng)/OCR/視頻理解等技術(shù)交流群：每月大咖直播分享、真實(shí)項(xiàng)目需求對接、求職內(nèi)推、算法競賽、干貨資訊匯總、與?10000+來自港科大、北大、清華、中科院、CMU、騰訊、百度等名校名企視覺開發(fā)者互動交流~覺得有用麻煩給個(gè)在看啦~??
