SVD-矩陣奇異值分解 —— 原理與幾何意義

06-07

來自專欄機器學習知識點

1 簡介

SVD 全稱：Singular Value Decomposition。SVD 是一種提取信息的強大工具，它提供了一種非常便捷的矩陣分解方式，能夠發現數據中十分有意思的潛在模式。

主要應用領域包括：

隱性語義分析 (Latent Semantic Analysis, LSA) 或隱性語義索引 (Latent Semantic Indexing, LSI)；
推薦系統 (Recommender system)，可以說是最有價值的應用點；
矩陣形式數據（主要是圖像數據）的壓縮。

2 線性變換

在做 SVD 推導之前，先了解一下線性變換，以 $2 imes 2$ 的線性變換矩陣為例，先看簡單的對角矩陣：

$M=egin{bmatrix} 3 & 0 \ 0 & 1 end{bmatrix}$

從集合上講， $M$ 是將二維平面上的點 $(x, y)$ 經過線性變換到另一個點的變換矩陣，如下所示：

$egin{bmatrix} 3 & 0 \ 0 & 1 end{bmatrix} egin{bmatrix} x \ y end{bmatrix}=egin{bmatrix} 3x \ y end{bmatrix}$

該變換的幾何效果是，變換後的平面沿著 $x$ 水平方向進行了3倍拉伸，垂直方向沒有發生變化。

3 SVD 推導

該部分的推導從幾何層面上去理解二維的SVD，總體的思想是：藉助 SVD 可以將一個相互垂直的網格 (orthogonal grid) 變換到另外一個互相垂直的網格。

可以通過二維空間中的向量來描述這件事情。

首先，選擇兩個互相正交的單位向量 $v_1$ 和 $v_2$ （也可稱為一組正交基）。

$M$ 是一個變換矩陣。

向量 $Mv_1，Mv_2$ 也是一組正交向量（也就是 $v_1$ 和 $v_2$ 經過 $M$ 變換得到的）。

$u_1$ ， $u_2$ 分別是 $Mv_1$ , $Mv_2$ 的單位向量（即另一組正交基），且有：

$Mv_1=sigma_1 u_1$

$Mv_2=sigma_2 u_2$

則， $sigma_1, sigma_2$ 分別為 $Mv_1, Mv_2$ 的模（也稱為 $M$ 的奇異值）。

設任意向量 $x$ ，有：

$x = (v_1 cdot x) v_1 + (v_2 cdot x) v_2$

例如，當 $x=egin{bmatrix} 3 \ 2 end{bmatrix}$ 時， $x=left( egin{bmatrix} 1 \ 0 end{bmatrix} egin{bmatrix} 3 & 2 end{bmatrix} ight) egin{bmatrix} 1 \ 0 end{bmatrix} + left( egin{bmatrix} 0 \ 1 end{bmatrix} egin{bmatrix} 3 & 2 end{bmatrix} ight) egin{bmatrix} 0 \ 1 end{bmatrix}$ .

那麼，可得：

$Mx = (v_1 cdot x) M v_1 + (v_2 cdot x) M v_2$

$Mx = (v_1 cdot x) sigma_1 u_1 + (v_2 cdot x) sigma_2 u_2$

根據線代知識，向量的內積可用向量的轉置來表示：

$v_1 cdot x = v^T x$ ，則有：

$Mx = v_1^T x sigma_1 u_1 + v_1^T x sigma_2 u_2$

兩邊去掉 $x$ ，得：

$M=u_1 sigma_1 v_1^T + u_2 sigma_2 v_2^T$

將下標相同的向量合併起來，則該式可通用地表達為：

$M=U Sigma V^T$

至此，SVD 使用幾何意義的形式推導完畢，其中：

$U$ 矩陣的列向量分別是 $u_1, u_2$ ；
$Sigma$ 是一個對角矩陣，形如： $egin{bmatrix} sigma_1 & 0 \ 0 & sigma_2 end{bmatrix}$ ；
$V$ 矩陣的列向量分別是 $v_1, v_2$ 。

關於 SVD 的一些重要的結論性總結：

任意的矩陣 $M$ 是可以分解成三個矩陣；
$V$ 表示了原始域的標準正交基；
$U$ 表示經過 $M$ 變換後的新標準正交基；
$Sigma$ 表示了 $V$ 中的向量與 $U$ 中相對應向量之間的比例（伸縮）關係；
$Sigma$ 中的每個 $sigma$ 會按從大到小排好順序，值越大代表該維度重要性越高；
在利用 SVD 做數據信息提取或壓縮時，往往依據一些啟發式策略，如直接設定只提取 $Sigma$ 中的前 $k$ 項，或者另一種較常用的做法是保留矩陣中一定百分比的能量信息，一般可設定為 90%，能量信息比例的計算可先求得所有奇異值平方總和，然後將奇異值的平方依次累加到總值的 90% 為止，形如： $displaystyle k = arg min_{k} frac{sum_{i=0}^{k}sigma_i^2}{sum_{i=0}^{N}sigma_i^2} geqslant 0.9$ .

4 實現代碼

以下是基於 python 的 numpy 庫實現的 SVD 矩陣分解的代碼，用於實現圖像壓縮的功能。

代碼鏈接 : https://github.com/zlxy9892/ml_code/tree/master/basic_algorithm/svd

# -*- coding: utf-8 -*-import numpy as npimport numpy.linalg as laimport matplotlib.pyplot as pltfrom sklearn import datasetsfrom skimage import iodef getImgAsMat(index): ds = datasets.fetch_olivetti_faces() return np.mat(ds.images[index])def getImgAsMatFromFile(filename): img = io.imread(filename, as_grey=True) return np.mat(img) def plotImg(imgMat): plt.imshow(imgMat, cmap=plt.cm.gray) plt.show()def recoverBySVD(imgMat, k): # singular value decomposition U, s, V = la.svd(imgMat) # choose top k important singular values (or eigens) Uk = U[:, 0:k] Sk = np.diag(s[0:k]) Vk = V[0:k, :] # recover the image imgMat_new = Uk * Sk * Vk return imgMat_new# -------------------- main --------------------- #A = getImgAsMatFromFile(D:/pic.jpg)plotImg(A)A_new = recoverBySVD(A, 30)plotImg(A_new)

這裡用小黃人的大頭照做個例子看看：

原圖：

設置 k = 10，得到的壓縮圖：

k = 20：

k = 30：

繼續增加 k 值，將會得到越來越接近原始圖的壓縮圖。

5 參考資料

We Recommend a Singular Value Decomposition (AMS 上一篇非常經典的關於SVD幾何意義的介紹)
奇異值分解 (SVD) 的幾何意義中文翻譯