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

本文的閱讀等級:中級

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=1i=j\mathbf{u}_i^T\mathbf{u}_j=0i\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=1i=j\mathbf{v}_i^T\mathbf{v}_j=0i\neq j
  • \Sigma 是一 m\times n 階對角矩陣,主對角元 \sigma_1\ge\cdots\ge\sigma_r>0\sigma_{r+1}=\cdots=\sigma_{p}=0p=\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)^\astUV 則為么正 (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) 矩陣組合式,因為 Ar 個秩-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 的奇異值分解所描述的單範正交基底映射關係。

orthonormal-basis-vectors3

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

 
最後我們想知道在座標變換觀點下,如何解釋線性映射 \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}

換句話說,正交矩陣 VU 的實際作用僅在「旋轉」或「鏡射」座標系統。在新座標系統中,變換矩陣 \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,其中 \LambdaB 的特徵值組成的對角矩陣,S 由對應的線性獨立特徵向量所構成。

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

This entry was posted in 線性代數專欄, 二次型 and tagged , , , , , , , , . Bookmark the permalink.

3 則回應給 線性變換觀點下的奇異值分解

  1. 莊仲翔 說:

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

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s