線性變換觀點下的奇異值分解

本文的閱讀等級：中級

1960年代初以前，奇異值分解 (singular value decomposition，簡稱 SVD) 普遍被視為一個模糊的理論概念，原因在於當時並不具備實際可行的算法。自從美國計算機科學教授格魯布 (Gene Golub) 與卡韓 (William Kahan) 於1965年率先發表了第一個有效的算法後，奇異值分解的價值才逐漸受到學者肯定，至今已成為線性代數中應用最廣的矩陣分解式^[1]。為甚麼奇異值分解這麼重要？這個問題可以從兩個層面加以剖析：奇異值分解的運作原理是甚麼？奇異值分解有哪些經典的應用？本文針對第一個問題提供部分解答。我們從線性變換觀點解釋奇異值分解的運算與意義，並藉此聯繫線性代數的一些核心概念，如值域、核、基本子空間、正交基底和座標變換。 (關於奇異值分解的推導和應用請參閱“奇異值分解專題”列舉的相關文章。)

令 $A$ 為一個 $m\times n$ 階實矩陣， $A$ 的奇異值分解 (SVD) 具有下列形式 (見“奇異值分解 (SVD)”)：

$A=U\Sigma V^T$ ，

其中

$U=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_m \end{bmatrix}$ 是 $m\times m$ 階正交矩陣 ( $U^T=U^{-1}$ )，行向量 $\mathbf{u}_i\in\mathbb{R}^m$ 稱為左奇異向量，它們組成一個單範正交集 (orthonormal set)： $\mathbf{u}_i^T\mathbf{u}_j=1$ 若 $i=j$ ， $\mathbf{u}_i^T\mathbf{u}_j=0$ 若 $i\neq j$ ；
$V=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}$ 是 $n\times n$ 階正交矩陣 ( $V^T=V^{-1}$ )，行向量 $\mathbf{v}_i\in\mathbb{R}^n$ 稱為右奇異向量，它們組成一個單範正交集： $\mathbf{v}_i^T\mathbf{v}_j=1$ 若 $i=j$ ， $\mathbf{v}_i^T\mathbf{v}_j=0$ 若 $i\neq j$ ；
$\Sigma$ 是 $m\times n$ 階對角矩陣，主對角元 $\sigma_1\ge\cdots\ge\sigma_r>0$ 和 $\sigma_{r+1}=\cdots=\sigma_{p}=0$ ， $p=\min\{m,n\}$ ，稱為奇異值，如下：

$\Sigma=\begin{bmatrix} \sigma_1&&&\vline&\\ &\ddots&&\vline&0\\ &&\sigma_r&\vline&\\\hline &0&&\vline&0\end{bmatrix}$ 。

以下討論限定於實矩陣，如欲將本文內容推廣至複矩陣，僅需將 $\mathbb{R}$ 替換為 $\mathbb{C}$ ，轉置 $(\cdot)^T$ 換為共軛轉置 $(\cdot)^\ast$ ， $U$ 和 $V$ 則為么正 (unitary) 矩陣 (見“特殊矩陣 (3)：么正矩陣 (酉矩陣)”)。

除了 $A=U\Sigma V^T$ ，奇異值分解還有其他等價的表達方式。上式等號兩邊右乘 $V$ ，可得 $AV=U\Sigma$ ，即

$A\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_r&\vline&\mathbf{v}_{r+1}&\cdots&\mathbf{v}_n \end{bmatrix}=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_r&\vline&\mathbf{u}_{r+1}&\cdots&\mathbf{u}_m \end{bmatrix}\begin{bmatrix} \sigma_1&&&\vline&\\ &\ddots&&\vline&0\\ &&\sigma_r&\vline&\\\hline &0&&\vline&0\end{bmatrix}$ 。

乘開可得下列方程組：

$\begin{aligned} A\mathbf{v}_i&=\sigma_i\mathbf{u}_i,~~i=1,\ldots,r\\ A\mathbf{v}_i&=\mathbf{0},~~i=r+1,\ldots,n,\end{aligned}$

稱為基底映射表達式 (稍後將詳細解釋)。使用矩陣乘法的行列展開 (見“矩陣乘法的現代觀點”)，可導出奇異值分解的另一個等價表達式：

$\begin{aligned} A&=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_r&\vline&\mathbf{u}_{r+1}&\cdots&\mathbf{u}_m \end{bmatrix}\begin{bmatrix} \sigma_1&&&\vline&\\ &\ddots&&\vline&0\\ &&\sigma_r&\vline&\\\hline &0&&\vline&0\end{bmatrix}\begin{bmatrix} \mathbf{v}_1^T\\ \vdots\\ \mathrm{v}_r^T\\\hline \mathbf{v}_{r+1}^T\\ \vdots\\ \mathbf{v}_n^T \end{bmatrix}\\ &=\sigma_1\mathbf{u}_1\mathbf{v}_1^T+\cdots+\sigma_r\mathbf{u}_r\mathbf{v}_r^T\\ &=\sigma_1E_1+\cdots+\sigma_rE_r,\end{aligned}$

稱為秩-1 (rank-one) 矩陣組合式，因為 $A$ 是 $r$ 個秩-1矩陣 $E_i=\mathbf{u}_i\mathbf{v}_i^T$ 的線性組合，組合權重即為奇異值 $\sigma_i$ 。

我們知道 $m\times n$ 階實矩陣 $A$ 是一個 $\mathbb{R}^n$ 映至 $\mathbb{R}^m$ 的線性變換，即 $A:\mathbb{R}^n\to\mathbb{R}^m$ 。因為 $\mathfrak{B}_V=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}$ 是一個單範正交集，故為 $\mathbb{R}^n$ 的一組基底。對於任一 $\mathbf{x}\in\mathbb{R}^n$ ，存在唯一數組 $c_1,\ldots,c_n$ 使得

$\mathbf{x}=c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}\begin{bmatrix} c_1\\ \vdots\\ c_n \end{bmatrix}=V\mathbf{c}$ ，

其中 $\mathbf{c}=(c_1,\ldots,c_n)^T=V^T\mathbf{x}$ 是 $\mathbf{x}$ 參考 $\mathfrak{B}_V$ 的座標向量，記為 $[\mathbf{x}]_{V}$ (見“圖解基底變換、座標變換、相似變換與相似矩陣”)。利用單範正交性質，上式左乘 $\mathbf{v}_i^T$ ，可得組合係數 $c_i$ ，推導如下：

$\mathbf{v}_i^T\mathbf{x}=\mathbf{v}_i^T\left(c_1\mathbf{v}_1+\cdots+c_n\mathbf{v}_n\right)=c_i\mathbf{v}_i^T\mathbf{v}_i=c_i$ 。

利用基底映射表達式，可求得 $\mathbf{x}$ 經線性變換 $A$ 的像 (image，即映射結果)：

$\begin{aligned} A\mathbf{x}&=A(c_1\mathbf{v}_1+\cdots+c_r\mathbf{v}_r+c_{r+1}\mathbf{v}_{r+1}+\cdots+c_n\mathbf{v}_n)\\ &=c_1A\mathbf{v}_1+\cdots+c_rA\mathbf{v}_r+c_{r+1}A\mathbf{v}_{r+1}+\cdots+c_nA\mathbf{v}_n\\ &=c_1\sigma_1\mathbf{u}_1+\cdots+c_r\sigma_r\mathbf{u}_r.\end{aligned}$

使用秩-1矩陣組合式也可得到相同結果：

$\displaystyle A\mathbf{x}=\left(\sum_{i=1}^r\sigma_i\mathbf{u}_i\mathbf{v}_i^T\right)\mathbf{x}=\sum_{i=1}^r\sigma_i\mathbf{u}_i(\mathbf{v}_i^T\mathbf{x})=\sum_{i=1}^rc_i\sigma_i\mathbf{u}_i$ 。

奇異值分解所表示的變換矩陣 $A$ 的映射過程包含三個步驟：先求 $\mathbf{x}$ 至基底向量 $\mathbf{v}_i$ 的正交投影 (見“正交投影──威力強大的線代工具”)，得到分量 $c_i\mathbf{v}_i$ ；計算此分量的像 $A(c_i\mathbf{v}_i)=c_i\sigma_i\mathbf{u}_i$ ；最後加總所有正交分量的像，此即 $A\mathbf{x}$ 。

接著討論奇異值分解給出的四個基本子空間基底。從上面的 $A\mathbf{x}$ 計算式和基底映射表達式可知 $A$ 的行空間 (即值域) $C(A)=\{A\mathbf{x}\vert\mathbf{x}\in\mathbb{R}^n\}$ 和零空間 (即核) $N(A)=\{\mathbf{x}\in\mathbb{R}^n\vert A\mathbf{x}=\mathbf{0}\}$ 分別是 (見“線性代數基本定理 (一)”)

$\begin{aligned} C(A)&=\mathrm{span}\{\mathbf{u}_1,\ldots,\mathbf{u}_r\}\\ N(A)&=\mathrm{span}\{\mathbf{v}_{r+1},\ldots,\mathbf{v}_n\}.\end{aligned}$

所以， $\mathrm{rank}A=\dim C(A)=r$ ， $\mathrm{nullity}A=\dim N(A)=n-r$ 。另一方面， $n\times m$ 階矩陣 $A^T$ 可看作從 $\mathbb{R}^m$ 映至 $\mathbb{R}^n$ 的逆向線性變換，即 $A^T:\mathbb{R}^m\to\mathbb{R}^n$ 。對 $A=U\Sigma V^T$ 取轉置， $A^T=V\Sigma^TU^T$ ，右乘 $U$ ，可得 $A^TU=V\Sigma^T$ 。對應 $A^T$ 奇異值分解的基底映射表達式為

$\begin{aligned} A^T\mathbf{u}_i&=\sigma_i\mathbf{v}_i,~~i=1,\ldots,r\\ A^T\mathbf{u}_i&=\mathbf{0},~~i=r+1,\ldots,m.\end{aligned}$

因為 $\mathfrak{B}_U=\{\mathbf{u}_1,\ldots,\mathbf{u}_m\}$ 是一個單範正交集，故為 $\mathbb{R}^m$ 的一組基底。對於任一 $\mathbf{y}\in\mathbb{R}^m$ ，存在唯一數組 $d_1,\ldots,d_m$ 使得

$\mathbf{y}=d_1\mathbf{u}_1+\cdots+d_m\mathbf{u}_m=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_m \end{bmatrix}\begin{bmatrix} d_1\\ \vdots\\ d_m \end{bmatrix}=U\mathbf{d}$ ，

其中 $\mathbf{d}=(d_1,\ldots,d_m)^T=U^T\mathbf{y}$ 是 $\mathbf{y}$ 參考 $\mathfrak{B}_U$ 的座標向量，記為 $[\mathbf{y}]_U$ 。使用基底映射表達式亦可求得 $\mathbf{y}$ 經矩陣變換 $A^T$ 的像：

$A^T\mathbf{y}=d_1\sigma_1\mathbf{v}_1+\cdots+d_r\sigma_r\mathbf{v}_r$ ，

故 $A$ 的列空間 $C(A^T)$ 和左零空間 $N(A^T)$ ，即 $A^T$ 的行空間和零空間，分別為

$\begin{aligned} C(A^T)&=\mathrm{span}\{\mathbf{v}_1,\ldots,\mathbf{v}_r\}\\ N(A^T)&=\mathrm{span}\{\mathbf{u}_{r+1},\ldots,\mathbf{u}_m\}.\end{aligned}$

以上結果說明列空間是零空間的正交補餘， $C(A^T)=N(A)^{\perp}$ ，行空間是左零空間的正交補餘， $C(A)=N(A^T)^{\perp}$ (見“線性代數基本定理 (二)”)。下圖顯示 $m\times n$ 階實矩陣 $A$ 的奇異值分解所描述的單範正交基底映射關係。

奇異值分解表達正交基底映射

最後我們想知道在座標變換觀點下，如何解釋線性映射 $\mathbf{y}=A\mathbf{x}$ ？代入奇異值分解，

$\mathbf{y}=U\Sigma V^T\mathbf{x}$ 。

上式左乘 $U^T$ ，可得 $U^T\mathbf{y}=\Sigma(V^T\mathbf{x})$ ，其中 $V^T\mathbf{x}=[\mathbf{x}]_V$ 是 $\mathbf{x}$ 參考 $\mathbb{R}^n$ 基底 $\mathfrak{B}_V$ 的座標向量， $U^T\mathbf{y}=[\mathbf{y}]_U$ 是 $\mathbf{y}$ 參考 $\mathbb{R}^m$ 基底 $\mathfrak{B}_U$ 的座標向量。所以，

$[\mathbf{y}]_U=\Sigma[\mathbf{x}]_V$ ，

這表明 $\Sigma$ 即是 $A$ 參考基底 $\mathfrak{B}_V$ – $\mathfrak{B}_U$ 的表示矩陣，一般記為 $~_U[A]_V$ 或 $[A]_V^U$ 。下面是奇異值分解的映射圖。

奇異值分解的亮點之一是向量 $\mathbf{x}$ 和 $\mathbf{y}$ 與其各自的座標向量 $[\mathbf{x}]_V$ 和 $[\mathbf{y}]_U$ 有相同的長度：

$\begin{aligned} \Vert V^T\mathbf{x}\Vert^2&=(V^T\mathbf{x})^T(V^T\mathbf{x})=\mathbf{x}^TVV^T\mathbf{x}=\Vert\mathbf{x}\Vert^2\\ \Vert U^T\mathbf{y}\Vert^2&=(U^T\mathbf{y})^T(U^T\mathbf{y})=\mathbf{y}^TUU^T\mathbf{y}=\Vert\mathbf{y}\Vert^2. \end{aligned}$

換句話說，正交矩陣 $V$ 和 $U$ 的實際作用僅在「旋轉」或「鏡射」座標系統。在新座標系統中，變換矩陣 $\Sigma$ 具有最簡約的主對角形式，每一奇異值 $\sigma_i$ 代表右奇異向量 $\mathbf{v}_i$ 的指向軸映至左奇異向量 $\mathbf{u}_i$ 的指向軸的拉伸量。利用奇異值分解的座標變換機制很容易解決較為複雜的映射問題。例如，「若 $\Vert\mathbf{x}\Vert=1$ ，求 $\mathbf{y}=A\mathbf{x}$ 所形成的集合。」轉換至新座標系統，等價問題變得異常簡單 (見“奇異值分解的幾何意義”)：「若 $[\mathbf{x}]_V$ 的長度等於 $1$ ，求 $[\mathbf{y}]_U=\Sigma[\mathbf{x}]_V$ 的集合。」所以在線性變換觀點下，我們可以推演出這樣的結論：奇異值分解 $A=U\Sigma V^T$ 對角化 $m\times n$ 階實矩陣 $A$ 好比譜分解 $B=S\Lambda S^{-1}$ 對角化 $n\times n$ 階矩陣 $B$ ，其中 $\Lambda$ 是 $B$ 的特徵值組成的對角矩陣， $S$ 由對應的線性獨立特徵向量所構成。

參考來源：
[1] Cleve Moler, Professor SVD, The MathWorks News & Notes, October 2006.

4 Responses to 線性變換觀點下的奇異值分解

莊仲翔 says:

08/28/2015 at 9:09 am

哈哈想不到多年以後回來看這一篇竟然還有領悟
謝謝老師 T^T

- ccjou says:
  
  08/28/2015 at 9:45 am
  
  哪天來新竹我們一起吃頓飯。
  
  - 莊仲翔 says:
    
    08/28/2015 at 9:52 am
    
    Of course, 該換我請客了 :)
    
xinrui says:

03/12/2017 at 1:23 pm

老师写的真的太好了，这么多年还在坚持！

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨