奇異值分解的幾何意義

本文的閱讀等級：高級

理解線性變換 $T:\mathcal{V}\rightarrow\mathcal{W}$ 的一個有效方式是透過解釋其幾何意義來呈現從向量空間 $\mathcal{V}$ 經過線性變換 $T$ 映射至向量空間 $\mathcal{W}$ 的變化性質。實際作法可由兩方面著手，第一個作法是在輸入空間 $\mathcal{V}$ 和輸出空間 $\mathcal{W}$ 中分別挑選出適當的基底，藉由基底之間的映射關係解析線性變換 $T$ ，這個結果稱為對角化；第二個作法是固定輸入向量 $\mathbf{x}\in\mathcal{V}$ 的某些幾何性質，從觀察輸出向量 $\mathbf{y}=T(\mathbf{x})$ 的變化情況來瞭解 $T$ 的作用。本文採用上述兩種方法解說奇異值分解 (singular value decomposition，簡稱 SVD) 的幾何意義 (見“奇異值分解 (SVD)”)。

奇異值分解是一個相當重要的矩陣分解式，在訊號處理和統計分析尤其有廣泛的應用。令 $A$ 為一個 $m\times n$ 階實線性變換表示矩陣，且 $\mathbf{x}\in\mathbb{R}^n$ 。(本文將討論範圍限於實矩陣，如要推廣至複矩陣只須將轉置運算 $A^{T}$ 替換為共軛轉置 $A^{\ast}$ 即可。) 奇異值分解常出現於兩種問題形式，第一是約束最佳化 (constrained optimization) 問題：考慮單位輸入向量 $\mathbf{x}$ ， $\Vert\mathbf{x}\Vert=1$ ，求最長的輸出向量 $A\mathbf{x}$ ，即

$\displaystyle\max_{\Vert\mathbf{x}\Vert=1}\Vert A\mathbf{x}\Vert$

第二是較為一般性的輸出界定問題：同樣設 $\Vert\mathbf{x}\Vert=1$ ，求 $A\mathbf{x}$ 的所有可能範圍。毫無疑問，我們選擇從較為單純的約束最佳化問題下手。

輸出向量 $A\mathbf{x}$ 的長度平方算式可推得下面的二次型：

$\Vert A\mathbf{x}\Vert^2=(A\mathbf{x})^{T}(A\mathbf{x})=\mathbf{x}^{T}(A^{T}A)\mathbf{x}\ge 0$

這說明 $n\times n$ 階交互乘積 $A^{T}A$ 是實對稱半正定矩陣。既然 $\Vert A\mathbf{x}\Vert$ 由 $A^{T}A$ 決定，於是我們將焦點集中在此方陣上。考慮特徵方程式

$A^{T}A\mathbf{v}_i=\lambda_i\mathbf{v}_i,~~i=1,\ldots,n$

實對稱矩陣 $A^{T}A$ 擁有單範正交 (orthonormal) 特徵向量，即 $\mathbf{v}_i^{T}\mathbf{v}_j=0$ 若 $i\neq j$ ，且對任意 $i$ ， $\mathbf{v}_i^T\mathbf{v}_i=1$ 。另外，半正定矩陣的特徵值不為負數，故可設 $\lambda_1\ge\cdots\ge\lambda_n\ge 0$ 。綜合以上結果， $A^{T}A$ 可正交對角化為

$A^{T}A=V\Lambda V^{T}$

其中 $\Lambda=\mathrm{diag}(\lambda_1,\ldots,\lambda_n)$ ， $V=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}$ 為正交矩陣， $V^{T}V=I$ 。接著我們利用變數變換來化簡二次型，令 $\mathbf{z}=V^{T}\mathbf{x}$ ，就有

$\Vert A\mathbf{x}\Vert^2=\mathbf{x}^{T}A^{T}A\mathbf{x}=\mathbf{x}^{T}V\Lambda V^{T}\mathbf{x}=\mathbf{z}^{T}\Lambda\mathbf{z}$

正交變換 $V^T$ 不改變向量長度，直接計算確認

$\Vert\mathbf{z}\Vert^2=\mathbf{z}^{T}\mathbf{z}=(V^{T}\mathbf{x})^{T}(V^{T}\mathbf{x})=\mathbf{x}^{T}VV^{T}\mathbf{x}=\mathbf{x}^{T}\mathbf{x}=\Vert\mathbf{x}\Vert^2=1$

原本問題等價於下面這個簡約問題：

$\displaystyle\max_{\Vert\mathbf{z}\Vert=1}\left(\mathbf{z}^{T}\Lambda\mathbf{z}\right)^{1/2}$

展開二次型並利用已知條件：

$\mathbf{z}^{T}\Lambda\mathbf{z}=\lambda_1 z_1^2+\cdots+\lambda_n z_n^2\le\lambda_1(z_1^2+\cdots+z_n^2)=\lambda_1$

於是解得

$\displaystyle\max_{\Vert\mathbf{x}\Vert=1}\Vert A\mathbf{x}\Vert=\max_{\Vert\mathbf{z}\Vert=1}\left(\mathbf{z}^{T}\Lambda\mathbf{z}\right)^{1/2}=\sqrt{\lambda_1}$

最大值發生於 $\mathbf{z}=(1,0,\ldots,0)$ ，亦即 $\mathbf{x}=\mathbf{v}_1$ 指向對應最大特徵值的特徵向量。

回答了第一個問題後，我們繼續往下深入探討。考慮單範正交向量集 $\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}$ 為 $\mathbb{R}^n$ 的一組基底。當 $\mathbf{x}=\mathbf{v}_i$ 時，

$\Vert A\mathbf{v}_i\Vert^2=\mathbf{v}_i^TA^TA\mathbf{v}_i=\mathbf{v}_i^{T}\lambda_i\mathbf{v}_i=\lambda_i$

假設 $A^{T}A$ 包含 $r$ 個非零特徵值，遞減排序如 $\lambda_1\ge\cdots\ge\lambda_r>0$ ， $\lambda_{r+1}=\cdots=\lambda_n=0$ 。當 $i=1,\ldots,r$ ， $\Vert A\mathbf{v}_i\Vert=\sqrt{\lambda_i}$ ，而當 $i>r$ ， $\Vert A\mathbf{v}_i\Vert=0$ 。這個結果極富啟發性，它提供了基底向量 $\mathbf{v}_i$ 經過線性變換 $A$ 之後的長度大小變化，我們定義矩陣 $A$ 的奇異值 (singular value) 為

$\displaystyle\sigma_i=\sqrt{\lambda_i}$

奇異值也按遞減方式排序， $\sigma_1\ge\cdots\ge\sigma_r>0$ 且 $\sigma_{r+1}=\cdots=\sigma_n=0$ 。在 $\mathbb{R}^m$ 空間，我們得到 $r$ 個不為零的基底映射 $A\mathbf{v}_i$ ， $i=1,\ldots,r$ 。若 $i\neq j$ ，

$(A\mathbf{v}_i)^{T}(A\mathbf{v}_j)=\mathbf{v}_i^{T}A^{T}A\mathbf{v}_j=\mathbf{v}_i^{T}\lambda_j\mathbf{v}_j=0$

推知 $\{A\mathbf{v}_1,\ldots,A\mathbf{v}_r\}$ 是一組正交向量集，可作為矩陣 $A$ 的行空間基底，因此 $\mathrm{rank}A=r$ 。對於 $i=1,\ldots,r$ ，將 $A\mathbf{v}_i$ 予以正規化，令

$\displaystyle\mathbf{u}_i=\frac{ A\mathbf{v}_i }{\Vert A\mathbf{v}_i\Vert}= \frac{1}{\sigma_i}A\mathbf{v}_i$

整理前述基底映射結果，就有

$A\mathbf{v}_i=\left\{\begin{matrix} \sigma_i\mathbf{u}_i & i=1,\ldots,r\\ \mathbf{0} & i=r+1,\ldots,n \end{matrix}\right.$

下圖表示 $\mathbb{R}^n$ 的基底向量 $\mathbf{v}_i$ 經線性變換 $A$ 後映至 $\mathbb{R}^{m}$ 的結果，有兩點值得特別注意：對於 $i=1,\ldots,r$ ， $\Vert A\mathbf{v}_i\Vert=\sigma_i$ ，而且 $A\mathbf{v}_i$ 彼此互為正交。

正交基底映射至正交基底

將上述二組方程式整理成矩陣形式，如下：

$\begin{aligned} A\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_r&\mathbf{v}_{r+1}&\cdots&\mathbf{v}_n \end{bmatrix}&=\begin{bmatrix} \sigma_1\mathbf{u}_1&\cdots&\sigma_r\mathbf{u}_r&\mathbf{0}&\cdots&\mathbf{0} \end{bmatrix}\\ &=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_r \end{bmatrix}\begin{bmatrix} \sigma_1&~&0&\cdots&0\\ ~&\ddots&~&\vdots&\vdots\\ 0&~&\sigma_r&\cdots&0 \end{bmatrix}\end{aligned}$

設 $m\times r$ 階矩陣 $U=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_r \end{bmatrix}$ ， $\Sigma=\begin{bmatrix} S&0 \end{bmatrix}$ 為 $r\times n$ 階矩陣， $S=\mathrm{diag}(\sigma_1,\ldots,\sigma_r)$ ，所以

$AV=U\Sigma$

上式等號兩邊同時右乘 $V^{T}$ 便得到 $A$ 的奇異值分解：

$A=U\Sigma V^{T}$

奇異值分解其實是一種矩陣對角化形式。操作 Gram-Schmidt 正交化程序可將向量集 $\{\mathbf{u}_1,\ldots,\mathbf{u}_r\}$ 擴充為 $\mathbb{R}^m$ 的一組單範正交基底 $\{\mathbf{u}_1,\ldots,\mathbf{u}_r,\mathbf{u}_{r+1},\ldots,\mathbf{u}_m\}$ ，對應的 $U$ 矩陣因此成為 $m$ 階正交矩陣， $U^{-1}=U^{T}$ ，同時又在 $\Sigma$ 底下增加 $(m-r)$ 列零元使成為 $m\times n$ 階矩陣， $\Sigma=\begin{bmatrix} S&0\\ 0&0 \end{bmatrix}$ 。令 $\mathbf{y}=A\mathbf{x}$ ，代入奇異值分解式， $\mathbf{y}=U\Sigma V^{T}\mathbf{x}$ ，等號兩邊左乘 $U^{T}$ 得到

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

令 $\mathbf{w}=U^{T}\mathbf{y}$ ， $\mathbf{w}$ 可以解釋為 $\mathbf{y}$ 參考 $\mathbb{R}^m$ 基底 $\mathfrak{U}=\{\mathbf{u}_1,\ldots,\mathbf{u}_m\}$ 的座標向量，表示為 $\mathbf{w}=[\mathbf{y}]_{\mathfrak{U}}$ 。同樣道理， $\mathbf{z}=V^{T}\mathbf{x}$ 也可以解讀為 $\mathbf{x}$ 參考 $\mathbb{R}^n$ 基底 $\mathfrak{V}=\{\mathbf{v}_1,\ldots,\mathbf{v}_n\}$ 的座標向量， $\mathbf{z}=[\mathbf{x}]_{\mathfrak{V}}$ 。經對角化後，以座標向量 $\mathbf{w}$ 和 $\mathbf{z}$ 表達的變換關係格外簡單： $\mathbf{w}=\Sigma\mathbf{z}$ 。

現在我們可以輕易解決輸出向量 $A\mathbf{x}$ 的範圍問題。設 $n\times m$ 階矩陣 $\Sigma^{+}$ 為

$\Sigma^{+}=\begin{bmatrix} S^{-1}&0\\ 0&0 \end{bmatrix}$

其中 $S^{-1}=\mathrm{diag}(1/\sigma_1,\ldots,1/\sigma_r)$ ， $\Sigma^{+}\Sigma=\begin{bmatrix} I_r&0\\ 0&0 \end{bmatrix}$ 為 $n$ 階方陣，因此，

$\Sigma^{+}\mathbf{w}=\Sigma^{+}\Sigma\mathbf{z}=\begin{bmatrix} I_r&0\\ 0&0 \end{bmatrix}\mathbf{z}$

上式等號兩側分別計算向量長度平方，左邊是

$\Vert \Sigma^{+}\mathbf{w}\Vert^2=\mathbf{w}^{T}(\Sigma^{+})^{T}\Sigma^{+}\mathbf{w}=\displaystyle\frac{w_1^2}{\sigma_1^2}+\cdots+\frac{w_r^2}{\sigma_r^2}$

右邊是

$\left\Vert\begin{bmatrix} I_r&0\\ 0&0 \end{bmatrix}\mathbf{z}\right\Vert^2=z_1^2+\cdots+z_r^2\le z_1^2+\cdots+z_r^2+z_{r+1}^2+\cdots+z_n^2=1$

合併二式得到不等式：

$\displaystyle\frac{w_1^2}{\sigma_1^2}+\cdots+\frac{w_r^2}{\sigma_r^2}\le 1$

當 $\Vert\mathbf{x}\Vert=1$ 時，輸出向量 $\mathbf{y}=A\mathbf{x}$ 的軌跡由一個 $r$ 維橢圓體所包覆， $\mathbf{u}_1$ 指向最長軸其軸半徑為 $\sigma_1$ ，而 $\mathbf{u}_r$ 則指向最短軸其軸半徑為 $\sigma_r$ 。

下面我們用一例說明，考慮

$A=\begin{bmatrix} 1&1&0\\ 0&2&1 \end{bmatrix}$

交互乘積為

$A^TA=\begin{bmatrix} 1&1&0\\ 1&5&2\\ 0&2&1 \end{bmatrix}$

奇異值分解的詳細計算步驟如下：

(1) 解出 $A^{T}A$ 的特徵值，奇異值與特徵向量： $\lambda_1=6$ ， $\lambda_2=1$ ， $\lambda_3=0$ ，可知 $\sigma_1=\sqrt{6}$ ， $\sigma_2=1$ ， $r=\mathrm{rank}A=2$ ，對應的特徵向量經正規化後分別為

$\displaystyle\mathbf{v}_1=\frac{1}{\sqrt{30}}\begin{bmatrix} 1\\5\\2 \end{bmatrix},~\mathbf{v}_2=\frac{1}{\sqrt{5}}\begin{bmatrix} -2\\ 0\\ 1\\ \end{bmatrix},~\mathbf{v}_3=\frac{1}{\sqrt{6}}\begin{bmatrix} 1\\-1\\2 \end{bmatrix}$

(2) 隨即得出正交矩陣 $V$ 和奇異值矩陣 $\Sigma$ ：

$V=\begin{bmatrix} 1/\sqrt{30}&-2/\sqrt{5}&1/\sqrt{6}\\ 5/\sqrt{30}&0&-1/\sqrt{6}\\ 2/\sqrt{30}&1/\sqrt{5}&2/\sqrt{6} \end{bmatrix},~\Sigma=\begin{bmatrix} \sqrt{6}&0&0\\ 0&1&0 \end{bmatrix}$

(3) 計算 $\mathbf{u}_i$ ， $i=1,2$ ：

$\begin{aligned} \mathbf{u}_1&=\displaystyle\frac{A\mathbf{v}_1}{\sigma_1}=\frac{1}{\sqrt{5}}\begin{bmatrix} 1\\2 \end{bmatrix}\\ \mathbf{u}_2&=\frac{A\mathbf{v}_2}{\sigma_2}=\frac{1}{\sqrt{5}}\begin{bmatrix} -2\\1 \end{bmatrix}\end{aligned}$

合併即得

$U=\displaystyle\frac{1}{\sqrt{5}}\begin{bmatrix} 1&-2\\ 2&1 \end{bmatrix}$

總結：線性變換 $A$ 的映射行為可從正交基底的關係解釋，見下圖。

(1) 當 $\mathbf{x}=\mathbf{v}_1$ ，輸出 $\mathbf{y}=A\mathbf{v}_1=\sigma_1\mathbf{u}_1=\frac{\sqrt{6}}{\sqrt{5}}\begin{bmatrix} 1\\2 \end{bmatrix}$ 對應橢圓長軸半徑。

(2) 當 $\mathbf{x}=\mathbf{v}_2$ ，輸出 $\mathbf{y}=A\mathbf{v}_2=\sigma_2\mathbf{u}_2=\frac{1}{\sqrt{5}}\begin{bmatrix} -2\\ 1 \end{bmatrix}$ 對應橢圓短軸半徑。

(3) 當 $\mathbf{x}=\mathbf{v}_3$ ，輸出為零向量。

單位正交基底的映射

11 Responses to 奇異值分解的幾何意義

張志瑋 (@jrweizhang) says:

04/05/2012 at 3:36 pm

http://s0.wp.com/latex.php?latex=%5Cbegin%7Baligned%7D++%5CVert+A%5Cmathbf%7Bv%7D_i%5CVert%5E2%26%3D%5Cmathbf%7Bv%7D_i%5ETA%5ETA%5Cmathbf%7Bv%7D_i%3D%5Cmathbf%7Bv%7D_i%5E%7BT%7D%5Clambda_i%5Cmathbf%7Bv%7D_i%3D%5Clambda_i%5Cend%7Baligned%7D&bg=ffffff&fg=333333&s=0

請問是怎麼推得當 x=v_i 時有這個等式的呢

- ccjou says:
  
  04/05/2012 at 4:59 pm
  
  最初推論就已經設 $v_i$ 是 $A^TA$ 的特徵向量對應特徵值 $\lambda_i$ ，即
  $A^TAv_i=\lambda_iv_i$
  所以
  $\Vert Av_i\Vert^2=(Av_i)^T(Av_i)=v_i^T(A^TAv_i)=v_i^T(\lambda_iv_i)=\lambda_i(v_i^Tv_i)=\lambda_i\Vert v_i\Vert^2=\lambda_i$
  
skysumbra (@skysumbra) says:

05/08/2015 at 10:42 am

你好
奇異値分解的三個矩陣，要怎麼用簡短的中文各自描述它們呢?

- ccjou says:
  
  05/08/2015 at 12:23 pm
  
  簡單講就是將給定的矩陣A「對角化」，將A看成線性變換 $A:\mathbb{R}^n\to\mathbb{R}^m$ ， $V$ 的行向量構成 $\mathbb{R}^n$ 的基底， $U$ 的行向量構成 $\mathbb{R}^m$ 的基底， $A$ 將 $\mathbf{v}_i$ 映射至 $\sigma_i\mathbf{u}_i$ 。請參閱下文：
  https://ccjou.wordpress.com/2013/01/17/%E7%B7%9A%E6%80%A7%E8%AE%8A%E6%8F%9B%E8%A7%80%E9%BB%9E%E4%B8%8B%E7%9A%84%E5%A5%87%E7%95%B0%E5%80%BC%E5%88%86%E8%A7%A3/
  
雲耕子 says:

04/18/2017 at 3:15 pm

教授您好，想要再請教您：
藉由m×n非方陣A的交乘矩陣A^TA所具備的對稱半正定性，我們一定可以得到對角化SVD，
那麼為什麼我們不乾脆同樣藉由n×n方陣A的交替矩陣A^TA(一樣會具備對稱半正定性)來求得diagonalization，而是轉而分析n×n方陣A的eigenspace、eigenvectors等等，而這甚至還不保證方陣可以diagonalization?

懇請教授賜教，謝謝~~~

- ccjou says:
  
  04/18/2017 at 4:45 pm
  
  SVD(對角化 $A^TA$ )與譜分解(對角化 $A$ )各自有不同的應用，
  https://ccjou.wordpress.com/%E5%B0%88%E9%A1%8C%E6%8E%A2%E7%A9%B6/%E7%9F%A9%E9%99%A3%E5%88%86%E8%A7%A3/
  
雲耕子 says:

04/18/2017 at 10:50 pm

教授您好，不知道我是否有問錯問題??
我的問題是指……任意m×n非方陣既然能藉由其交乘矩陣的”對稱半正定性”來得到對角化SVD
那怎麼會有一些n×n方陣無法diagonalization呢?
n×n方陣的交乘矩陣同樣會有對稱半正定性，照理來講似乎也可以SVD，
而方陣的SVD結果不就是diagonalization嗎??
為什麼會出現這樣的矛盾呢?
或者是我有什麼地方認知錯誤嗎?

懇請教授賜教，謝謝

雲耕子 says:

04/19/2017 at 1:17 am

教授您好，我猜想我誤解的點可能是在於，針對一個n×n方陣做SVD，分解式中的U和V也是兩組不同的orthonormal basis(雖然dimension一樣是n)，然而真正的diagonalization則是必須在同一組orthonormal basis中達成……n×n方陣的SVD只能說是看起來好像是diagonalization實則不然???

- ccjou says:
  
  04/19/2017 at 6:56 am
  
  是的，當你花90%的力氣弄清楚問題，只要10%的力氣就得到答案。
  
  對角化是來自 $Ax=\lambda x$ ，所有的 $x$ 組成完成整的線性獨立集。
  SVD來自 $Av=\sigma u$ ，我們總是能找到 orthonormal $u, v$ 。
  
  - 雲耕子 says:
    
    04/19/2017 at 9:35 am
    
    謝謝教授指導，我明白了~
    
unga says:

01/28/2022 at 12:27 am

半夜12:25看著這篇的我內心湧現許多熱血，醍醐灌頂，太感動了。

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