線性代數 Cheat Sheet 7-4:奇異值分解

對角化定理有很多重要的應用,但並不是所有矩陣都有分解式 $A = PDP^{-1}$,且 $D$ 是對角的。但分解 $A = QDP^{-1}$ 對任意 $m \times n$ 矩陣 $A$ 都有可能。這類特殊的分解稱為奇異值分解。

奇異值分解基於一般的矩陣對角化性質,可以被長方形矩陣模仿:一個對稱矩陣 $A$ 的特徵值的絕對值表示度量 $A$ 拉長或壓縮一個矢量(特徵矢量)的成都。如果 $A \boldsymbol x = \lambda \boldsymbol x$,且 $\lVert \boldsymbol x \rVert = 1$,那麼

\begin{equation}

\lVert A \boldsymbol x \rVert = \lVert \lambda \boldsymbol x \rVert = |\lambda| \lVert \boldsymbol x \rVert = |\lambda| \tag{1}

\end{equation}

如果 $\lambda_1$ 是具有最大數值的特徵值,那麼對應的單位矢量 $\boldsymbol v_1$ 確定一個由 $A$ 拉長影響最大的方向,也就是説,$(1)$ 式表示 $\boldsymbol x = \boldsymbol v_1$ 時,$A \boldsymbol x$ 的長度最大化,且 $\lVert A \boldsymbol v_1 \rVert = |\lambda_1|$。這個對 $\boldsymbol v_1$ 和 $|\lambda_1|$ 的概述對長方形的矩陣來説也是類似地,這將導致奇異值分解。

Contents

1. 一個 $m \times n$ 矩陣的奇異值

令 $A$ 是 $m \times n$ 矩陣,那麼 $A^\mathsf{T}A$ 是對稱矩陣且可以正交對角化。令 $\{\boldsymbol v_1, \cdots, \boldsymbol v_n\}$ 是 $\mathbb{R}^n$ 的單位正交基且構成 $A^\mathsf{T}A$ 的特徵矢量,$\lambda_1, \cdots, \lambda_n$ 是 $A^\mathsf{T}A$ 對應的特徵值,那麼對 $1 \leq i \leq n$,

\begin{equation}

\lVert A \boldsymbol v_1 \rVert^2 = (A \boldsymbol v_1)^\mathsf{T} A \boldsymbol v_1 = \boldsymbol v_1^\mathsf{T} A^\mathsf{T} A \boldsymbol v_1 = \boldsymbol v_1^\mathsf{T} (\lambda_1 \boldsymbol v_1) = \lambda_1 \tag{2}

\end{equation}

所以,$A^\mathsf{T}A$ 的所有特徵值都非負。如果必要,通過重新編號,可以假設特徵值的重新排列滿足

\begin{equation}

\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0

\end{equation}

$A$ 的 奇異值 是 $A^\mathsf{T}A$ 的特徵值的平方根,記為 $\sigma_1, \cdots, \sigma_n$,且它們用遞減順序排列,也就是對 $1 \leq i \leq n$,$\sigma_i = \sqrt{\lambda_i}$。由 $(2)$ 可知,$A$ 的奇異值是矢量 $A \boldsymbol v_1, \cdots A \boldsymbol v_n$ 的長度。

定理 9假若 $\{\boldsymbol v_1, \cdots, \boldsymbol v_n\}$ 是包含 $A^\mathsf{T}A$ 的特徵矢量的 $\mathbb{R}^n$ 上的單位正交基,刷新使得對應的 $A^\mathsf{T}A$ 的特徵值滿足 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \geq 0$。假若 $A$ 有 $r$ 個非零奇異值,那麼 $\{A\boldsymbol v_1, \cdots, A\boldsymbol v_r\}$ 是 $\mathrm{Col}\; A$ 的一個正交基,且 $\mathrm{rank}\; A = r$。

2. 奇異值分解

矩陣 $A$ 的分解涉及一個 $m \times n$ “對角”矩陣 $\Sigma$,其形式是

\begin{equation}

\Sigma = \begin{bmatrix} D & 0 \\ 0 & 0\end{bmatrix} \tag{3}

\end{equation}

其中,$D$ 是一個 $r \times r$ 對角矩陣,且 $r$ 不超過 $m$ 和 $n$ 中較小的那個。

定理 10(奇異值分解)設 $A$ 是秩為 $r$ 的 $m \times n$ 矩陣,那麼存在一個類似 $(3)$ 中的 $m \times n$ 矩陣 $\Sigma$,其中 $D$ 的對角線元素是 $A$ 的前 $r$ 個奇異值,$\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$,並且存在一個 $m \times m$ 正交矩陣 $U$ 和一個 $n \times n$ 正交矩陣 $V$ 使得 $A = U \Sigma V^\mathsf{T}$。

任何分解 $A = U \Sigma V^\mathsf{T}$ 稱為 $A$ 的一個 奇異值分解 (或 SVD),其中 $U$ 和 $V$ 是正交矩陣,$\Sigma$ 形如 $(3)$ 式,$D$ 具有正的對角線元素。矩陣 $U$ 和 $V$ 不是 $A$ 惟一確定的,但 $\Sigma$ 的對角線元素必須是 $A$ 的奇異值。這樣的一個分解中,$U$ 的列稱為 $A$ 的 左奇異矢量 ,$V$ 的列稱為 $A$ 的 右奇異矢量

一個奇異值分解可分為三步進行。下面以 $A = \begin{bmatrix} 4 & 11 & 14 \\ 8 & 7 & -2\end{bmatrix}$ 為例,求 $A$ 的一個奇異值分解。

第一步,將 $A^\mathsf{T} A$ 正交對角化。即求矩陣 $A^\mathsf{T} A$ 的特徵值及其對應的特徵矢量的單位正交集。這裏

\begin{equation}

A^\mathsf{T} A =

\begin{bmatrix}

80 & 100 & 40 \\

100 & 170 & 140 \\

40 & 140 & 200

\end{bmatrix} \\

\lambda_1 = 360, \; \boldsymbol v_1 = \begin{bmatrix} 1/3 \\ 2/3 \\ 2/3 \end{bmatrix} \\

\lambda_2 = 90, \; \boldsymbol v_2 = \begin{bmatrix} -2/3 \\ -1/3 \\ 2/3 \end{bmatrix} \\

\lambda_3 = 0, \; \boldsymbol v_3 = \begin{bmatrix} 2/3 \\ -2/3 \\ 1/3 \end{bmatrix}

\end{equation}

第二步,計算 $V$ 和 $\Sigma$。將 $A^\mathsf{T} A$ 的特徵值按降序排列,使用對應特徵矢量的排列構造 $P$。在上面的結果中,$\lambda_1 > \lambda_2 > \lambda_3$,構造

\begin{equation}

P = \begin{bmatrix} \boldsymbol v_1 & \boldsymbol v_2 & \boldsymbol v_3\end{bmatrix} =

\begin{bmatrix}1/3 & -2/3 & 2/3 \\2/3 & -1/3 & -2/3 \\2/3 & 2/3 & 1/3\end{bmatrix}

\end{equation}

特徵值的平方根就是奇異值:$\sigma_1 = \sqrt{360} = 6 \sqrt{10}$,$\sigma_2 = \sqrt{90} = 3 \sqrt{10}$,$\sigma_3 = 0$。其中非零奇異值是矩陣 $D$ 的對角線元素。矩陣 $\Sigma$ 與矩陣 $A$ 的行列數相同,以矩陣 $D$ 為其左上角,其他元素為 $0$。

\begin{equation}

D = \begin{bmatrix} 6 \sqrt{10} & 0 \\ 0 & 3 \sqrt{10} \end{bmatrix} \\

\Sigma = \begin{bmatrix} D & 0 \end{bmatrix} = \begin{bmatrix} 6 \sqrt{10} & 0 & 0 \\ 0 & 3 \sqrt{10} & 0 \end{bmatrix}

\end{equation}

第三步,構造 $U$。當矩陣 $A$ 的秩為 $r$ 時,矩陣 $U$ 的前 $r$ 列是從 $A \boldsymbol v_1 \cdots A \boldsymbol v_r$ 計算得到的單位矢量。這裏 $A$ 有兩個非零奇異值,因此 $\mathrm{rank}\; A = 2$。根據式 $(2)$,有 $\lVert A \boldsymbol v_1 \rVert = \sigma_1$,$\lVert A \boldsymbol v_2 \rVert = \sigma_2$,於是

\begin{equation}

\boldsymbol u_1 = \frac{1}{\sigma_1} A \boldsymbol v_1 = \frac{1}{6\sqrt{10}} \begin{bmatrix} 18 \\ 6 \end{bmatrix} = \begin{bmatrix} 3/\sqrt{10} \\ 1/\sqrt{10} \end{bmatrix} \\

\boldsymbol u_2 = \frac{1}{\sigma_2} A \boldsymbol v_2 = \frac{1}{3\sqrt{10}} \begin{bmatrix} 3 \\ -9 \end{bmatrix} = \begin{bmatrix} 1/\sqrt{10} \\ -3/\sqrt{10} \end{bmatrix} \\

\end{equation}

留意到 $\{\boldsymbol u_1, \boldsymbol u_2 \}$ 已經是 $\mathbb{R}^2$ 的一個基,因此構造 $U$ 不需要另外的矢量,$U = \begin{bmatrix} \boldsymbol u_1 & \boldsymbol u_2 \end{bmatrix}$。$A$ 的奇異值分解是

\begin{equation}

A = \begin{bmatrix} 3\sqrt{10} & 1\sqrt{10} \\ 1\sqrt{10} & -3\sqrt{10} \end{bmatrix}

\begin{bmatrix} 6 \sqrt{10} & 0 & 0 \\ 0 & 3 \sqrt{10} & 0 \end{bmatrix}

\begin{bmatrix}1/3 & -2/3 & 2/3 \\2/3 & -1/3 & -2/3 \\2/3 & 2/3 & 1/3\end{bmatrix}

\end{equation}

3. 奇異值分解的應用

奇異值分解常用於估計矩陣的秩。

當應用矩陣 $A$ 的奇異值分解時,多數涉及方程 $A \boldsymbol x = \boldsymbol b$ 的數值計算要儘可能地可靠。兩個正交矩陣 $U$ 和 $V$ 不影響矢量的長度和兩個矢量的夾角(定理 7)。數值計算中的任何不穩定因素都與 $\Sigma$ 有關。如果 $A$ 的奇異值非常大或非常小,則舍入誤差幾乎不可避免,此時,知道 $\Sigma$ 和 $V$ 中的元素對分析誤差特別有用。

如果 $A$ 是一個 $n \times n$ 可逆矩陣,那麼最大奇異值和最小奇異值的比率 $\sigma_1 / \sigma_n$ 給出了矩陣 $A$ 的 條件數 。條件數影響 $A \boldsymbol x = \boldsymbol b$ 的解對 $A$ 元素變化(或誤差)的敏感程度。

給定 $m \times n$ 矩陣 $A$ 的一個奇異值分解,取 $\boldsymbol u_1, \cdots, \boldsymbol u_m$ 是左奇異矢量,$\boldsymbol v_1, \cdots, \boldsymbol v_m$ 是右奇異矢量,且 $\sigma_1, \cdots, \sigma_n$ 是奇異值,$r$ 為 $A$ 的秩。由定理 9,

\begin{equation}

\{\boldsymbol u_1, \cdots, \boldsymbol u_m\} \tag{4}

\end{equation}

是 $\mathrm{Col}\; A$ 的一個單位正交基。由 6-1定理 3,$(\mathrm{Col}\; A)^\perp = \mathrm{Nul}\; A^\mathsf{T}$,因此

\begin{equation}

\{\boldsymbol u_{r+1}, \cdots, \boldsymbol u_m\} \tag{5}

\end{equation}

是 $\mathrm{Nul}\; A$ 的一個正交基。

由於當 $1 \leq i \leq n$ 時 $\lVert A \boldsymbol v_i \rVert = \sigma_i$,且 $\sigma_i$ 是零的充分必要條件是 $i > r$,因此矢量 $\boldsymbol v_{r+1}, \cdots, \boldsymbol v_n$ 生成一個維數為 $n – r$ 的子空間 $\mathrm{Nul}\; A$。由秩定理可知,$\dim \mathrm{Nul}\; A = n – \mathrm{rank}\; $,從而説明

\begin{equation}

\{\boldsymbol v_{r+1}, \cdots, \boldsymbol v_n\} \tag{6}

\end{equation}

是 $\mathrm{Nul}\; A$ 的一個單位正交基。

由 $(4)$ 和 $(5)$ 可知,空間 $\mathrm{Nul}\; A^\mathsf{T}$ 的正交補是 $\mathrm{Col}\; A$。將 $A$ 和 $A^\mathsf{T}$ 交換,有

\begin{equation}

(\mathrm{Nul}\; A)^\perp = \mathrm{Col}\; A^\mathsf{T} = \mathrm{Row}\; A

\end{equation}

因此,右 $(6)$ 得

\begin{equation}

\{\boldsymbol v_1, \cdots, \boldsymbol v_r\} \tag{7}

\end{equation}

是 $\mathrm{Row}\; A$ 的一個單位正交基。

定理(可逆矩陣定理)設 $A$ 為 $m \times n$ 矩陣,那麼下述命題中的每一個都與 $A$ 是可逆矩陣的命題等價。

u. $(\mathrm{Col}\; A)^\perp = \{\boldsymbol 0 \}$

v. $(\mathrm{Nul}\; A)^\perp = \mathbb{R}^n$

w. $\mathrm{Row}\; A = \mathbb{R}^n$

x. $A$ 有 $n$ 個非零的特徵值。

當 $\Sigma$ 包含零元素的行或列時,矩陣 $A$ 具有更簡潔的分解。利用上面創建的符號,取 $r = \mathrm{rank}\; A$,將 $U$ 和 $V$ 矩陣分塊稱為第一塊包含 $r$ 列的子矩陣:

\begin{equation}

U = \begin{bmatrix} U_r & U_{m-r} \end{bmatrix}, \; 其中 U_r = \begin{bmatrix} \boldsymbol u_1 & \cdots & \boldsymbol u_r \end{bmatrix} \\

V = \begin{bmatrix} V_r & V_{n-r} \end{bmatrix}, \; 其中 V_r = \begin{bmatrix} \boldsymbol v_1 & \cdots & \boldsymbol v_r \end{bmatrix}

\end{equation}

那麼 $U_r$ 是 $m \times r$,$V_r$ 是 $n \times r$。分塊矩陣的乘法表明

\begin{equation}

A = \begin{bmatrix} U_r & U_{m-r} \end{bmatrix}

\begin{bmatrix} D & 0 \\ 0 & 0 \end{bmatrix}

\begin{bmatrix} V_r^\mathsf{T} \\ V_{n-r}^\mathsf{T} \end{bmatrix} =

U_r D V_r^\mathsf{T}

\end{equation}

矩陣 $A$ 的這個分解稱為 $A$ 的 簡化的奇異值分解 。由於 $D$ 的對角線元素非零,因此 $D$ 是可逆矩陣。下面的矩陣稱為 $A$ 的 偽逆 (也稱 穆爾-彭羅斯逆 ):

\begin{equation}

A^+ = V_r D^{-1} U_r^\mathsf{T}

\end{equation}