利用 Gramian 矩陣的譜分解推導奇異值分解

本文的閱讀等級:中級

LU 分解是高斯消去法的一種表達形式 (見“LU 分解”),QR 分解記錄 Gram-Schmidt 正交化的結果 (見“Gram-Schmidt 正交化與 QR 分解”)。那麼奇異值分解的根基又是甚麼?答案並非一個演算法,而是一個性質:Gramian 矩陣的譜分解 (spectral decomposition)。矩陣的特徵值也稱為譜,所謂譜分解就是將特徵值分解出來。設 A 為一 m\times n 階矩陣,我們稱 n\times nA^\ast Am\times mAA^\ast 為 Gramian 矩陣。不難確認 A^\ast AAA^\ast 皆為 Hermitian 半正定矩陣 (見“特殊矩陣 (14):Gramian 矩陣”)。Hermitian 矩陣的譜分解稱作么正對角化 (unitary diagonalization):任一 k\times k 階 Hermitian 矩陣 H 可表示為 H=Q\Lambda Q^\ast,其中 Q 是么正矩陣,Q^\ast=Q^{-1},且 \Lambda=\text{diag}(\lambda_1,\ldots,\lambda_k) 是實矩陣,\lambda_1,\ldots,\lambda_kH 的特徵值 (見“特殊矩陣 (9):Hermitian 矩陣”)。本文運用基礎矩陣代數從 A^\ast A 的譜分解推導 A 的奇異值分解[1] (採行 AA^\ast 的推導方式亦類似),這個過程能夠幫助我們對奇異值分解的構造矩陣有更深刻的理解。

 
由於 A^\ast A 是半正定矩陣,其特徵值不為負值,可令 \sigma_1^2,\ldots,\sigma_n^2A^\ast A 的特徵值。假設 \sigma_1\ge\cdots\ge\sigma_r>0,且 \sigma_{r+1}=\cdots=\sigma_n=0,稱為 A 的奇異值。稍後我們將證明 r=\text{rank}A。因為 A^\ast AAA^\ast 有相同的非零特徵值 (見“AB 和 BA 有何關係?”),故 AA^\ast 的非零特徵值亦為 \sigma_1^2,\ldots,\sigma_r^2。根據 Hermitian 矩陣的譜分解,存在一 n\times n 階么正矩陣 V 使得

\displaystyle  A^\ast A=V\begin{bmatrix}  D^2&0\\  0&0  \end{bmatrix}V^\ast

或表示為

\displaystyle  V^\ast A^\ast AV=\begin{bmatrix}  D^2&0\\  0&0  \end{bmatrix}

其中 D=\text{diag}(\sigma_1,\ldots,\sigma_r)。為便利分塊矩陣運算,設 V=\begin{bmatrix}  V_1 & V_2  \end{bmatrix},其中 V_1n\times r 階,V_2n\times(n-r) 階。代入上式,乘開可得

\displaystyle  \begin{bmatrix}  V_1^\ast\\  V_2^\ast  \end{bmatrix}A^\ast A\begin{bmatrix}  V_1 &V_2  \end{bmatrix}=\begin{bmatrix}  V_1^\ast A^\ast AV_1&V_1^\ast A^\ast AV_2\\  V_2^\ast A^\ast AV_1&V_2^\ast A^\ast AV_2  \end{bmatrix}=\begin{bmatrix}  D^2&0\\  0&0  \end{bmatrix}

比較最後一個等式的主對角分塊,即得 V_1^\ast A^\ast AV_1=D^2V_2^\ast A^\ast AV_2=(AV_2)^\ast(AV_2)=0。使用矩陣秩性質 \text{rank}(AV_2)=\text{rank}((AV_2)^\ast(AV_2))=\text{rank}0=0 (見“利用 Gramian 矩陣證明行秩等於列秩”),立知 AV_2=0。因為 V 是么正矩陣,

\displaystyle  V^\ast V=\begin{bmatrix}  V_1^\ast\\  V_2^\ast  \end{bmatrix}\begin{bmatrix}  V_1&V_2  \end{bmatrix}=\begin{bmatrix}  V_1^\ast V_1&V_1^\ast V_2\\  V_2^\ast V_1&V_2^\ast V_2  \end{bmatrix}=\begin{bmatrix}  I_r&0\\  0&I_{n-r}  \end{bmatrix}

就有 V_1^\ast V_1=I_rV_2^\ast V_2=I_{n-r}V_1^\ast V_2=0V_2^\ast V_1=0。。另一方面,

\displaystyle  VV^\ast=\begin{bmatrix}  V_1&V_2  \end{bmatrix}\begin{bmatrix}  V_1^\ast\\  V_2^\ast  \end{bmatrix}=V_1V_1^\ast+V_2V_2^\ast=I_n

 
接下來的工作是將 A 從關鍵式 V_1^\ast A^\ast AV_1=D^2 分離開來。定義 m\times r 階矩陣

\displaystyle  U_1=AV_1D^{-1}

因此,

\displaystyle\begin{aligned}  U_1DV_1^\ast&=AV_1D^{-1}DV_1^\ast=AV_1V_1^\ast\\  &=A(I-V_2V_2^\ast)=A-AV_2V_2^\ast=A.\end{aligned}

A=U_1DV_1^\ast 稱為瘦奇異值分解 (見“奇異值分解 (SVD)”)。注意,U_1r 個行向量組成單範正交集 (orthonormal set),驗證於下:

\displaystyle\begin{aligned}  U_1^\ast U_1&=(AV_1D^{-1})^\ast AV_1D^{-1}=D^{-1}V_1^\ast A^\ast AV_1D^{-1}\\  &=D^{-1}D^2D^{-1}=I_r.\end{aligned}

為了得到標準奇異值分解,選擇 m\times(m-r) 階矩陣 U_2 使得 U=\begin{bmatrix}  U_1&U_2  \end{bmatrix} 為一么正矩陣,也就有 U_1^\ast U_2=0。令 m\times n 階矩陣

\displaystyle  \Sigma=\begin{bmatrix}  D&0\\  0&0  \end{bmatrix}

其中底列由左至右分別是 (m-r)\times r 階和 (m-r)\times(n-r) 階零矩陣。套用瘦奇異值分解,

\displaystyle\begin{aligned}  U\Sigma V^\ast&=\begin{bmatrix}  U_1&U_2  \end{bmatrix}\begin{bmatrix}  D&0\\  0&0  \end{bmatrix}\begin{bmatrix}  V_1^\ast\\  V_2^\ast  \end{bmatrix}\\  &=\begin{bmatrix}  U_1&U_2  \end{bmatrix}\begin{bmatrix}  DV_1^\ast\\  0  \end{bmatrix}=U_1DV_1^\ast=A,\end{aligned}

此即奇異值分解。

 
最後我們討論奇異值分解的一些性質:

  1. AV_1=U_1DAV_2=0,也就是說,C(A)=C(U_1)N(A)=C(V_2)[2]

    瘦奇異值分解 A=U_1DV_1^\ast,右乘 V_1 即得 AV_1=U_1D。第二式 AV_2=0 先前已經證明過。因為 U_1 有線性獨立的行向量且 D 是可逆矩陣,推知 \text{rank}A=\text{rank}U_1=r

  2. A^\ast U_1=V_1DA^\ast U_2=0,也就是說,C(A^\ast)=C(V_1)N(A^\ast)=C(U_2)

    使用瘦奇異值分解,可得 A^\ast U_1=(U_1DV_1^\ast)^\ast U_1=V_1DU_1^\ast U_1=V_1DA^\ast U_2=V_1DU_1^\ast U_2=0

  3. A^\ast AV_1=V_1D^2A^\ast AV_2=0,也就是說,A^\ast A 的特徵向量為 V 的行向量,對應特徵值 \sigma_1^2,\ldots,\sigma_r^2,以及 (n-r) 個零。

    使用瘦奇異值分解和 (1),A^\ast AV_1=(V_1DU_1^\ast)(U_1D)=V_1D^2A^\ast AV_2=A^\ast 0=0

  4. AA^\ast U_1=U_1D^2AA^\ast U_2=0,也就是說,AA^\ast 的特徵向量為 U 的行向量,對應特徵值 \sigma_1^2,\ldots,\sigma_r^2,以及 (m-r) 個零。

    使用瘦奇異值分解和 (2),AA^\ast U_1=(U_1DV_1^\ast)(V_1D)=U_1D^2AA^\ast U_2=A0=0

 
註解與來源:
[1] 維基百科:Singular value decomposition
[2] C(A) 表示 A 的行空間 (column space),N(A) 表示 A 的零空間 (nullspace)。

相關閱讀:
Advertisements
This entry was posted in 線性代數專欄, 二次型 and tagged , , , . Bookmark the permalink.

發表迴響

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

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s