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

本文的閱讀等級：中級

LU 分解是高斯消去法的一種表達形式 (見“LU 分解”)，QR 分解記錄 Gram-Schmidt 正交化的結果 (見“Gram-Schmidt 正交化與 QR 分解”)。那麼奇異值分解的根基又是甚麼？答案並非一個演算法，而是一個性質：Gramian 矩陣的譜分解 (spectral decomposition)。矩陣的特徵值也稱為譜，所謂譜分解就是將特徵值分解出來。設 $A$ 為一 $m\times n$ 階矩陣，我們稱 $n\times n$ 階 $A^\ast A$ 和 $m\times m$ 階 $AA^\ast$ 為 Gramian 矩陣。不難確認 $A^\ast A$ 和 $AA^\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_k$ 是 $H$ 的特徵值 (見“特殊矩陣 (9)：Hermitian 矩陣”)。本文運用基礎矩陣代數從 $A^\ast A$ 的譜分解推導 $A$ 的奇異值分解^[1] (採行 $AA^\ast$ 的推導方式亦類似)，這個過程能夠幫助我們對奇異值分解的構造矩陣有更深刻的理解。

由於 $A^\ast A$ 是半正定矩陣，其特徵值不為負值，可令 $\sigma_1^2,\ldots,\sigma_n^2$ 為 $A^\ast A$ 的特徵值。假設 $\sigma_1\ge\cdots\ge\sigma_r>0$ ，且 $\sigma_{r+1}=\cdots=\sigma_n=0$ ，稱為 $A$ 的奇異值。稍後我們將證明 $r=\text{rank}A$ 。因為 $A^\ast A$ 和 $AA^\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_1$ 是 $n\times r$ 階， $V_2$ 是 $n\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^2$ ， $V_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_r$ ， $V_2^\ast V_2=I_{n-r}$ ， $V_1^\ast V_2=0$ 且 $V_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_1$ 的 $r$ 個行向量組成單範正交集 (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}$

此即奇異值分解。

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

$AV_1=U_1D$ ， $AV_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$ 。
$A^\ast U_1=V_1D$ ， $A^\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_1D$ 和 $A^\ast U_2=V_1DU_1^\ast U_2=0$ 。
$A^\ast AV_1=V_1D^2$ ， $A^\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^2$ 且 $A^\ast AV_2=A^\ast 0=0$ 。
$AA^\ast U_1=U_1D^2$ ， $AA^\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^2$ 且 $AA^\ast U_2=A0=0$ 。

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

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

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

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱

閱讀導引

學習資源

專題探究

急救查詢

其他分頁

Meta

網路狀態

Blog Stats

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

Share this:

Like this:

Leave a Reply Cancel reply

搜尋(繁體中文或英文)

訊息看板

近期文章

線性代數專欄

其他主題專欄

每週問題

數據充分性問題

其他分類

Recent Comments

近期最多人點閱

分類

Archives

標籤雲

線代線上影音課程

線代學習網站

線代電子書

矩陣計算器

LaTeX

Blogroll

訂閱