奇異值分解的幾何意義

本文的閱讀等級:高級

理解線性變換 T:\mathcal{V}\rightarrow\mathcal{W} 的一個有效途徑是透過解釋其幾何意義來呈現向量從空間 \mathcal{V} 經過 T 映射至空間 \mathcal{W} 的變化性質。實際作法可由兩方面著手,一是在輸入空間 \mathcal{V} 和輸出空間 \mathcal{W} 中分別挑選出適當的基底,藉由基底之間的映射關係解析線性變換,這個結果稱為對角化;二是固定輸入向量 \mathbf{x} 的某些幾何性質,從觀察輸出向量 \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}\VertA^{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=0i\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}_ii=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=1r=\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}_ii=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,輸出為零向量。

單位正交基底的映射

廣告
本篇發表於 線性代數專欄, 二次型 並標籤為 , , , , , , 。將永久鏈結加入書籤。

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

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

  2. 雲耕子 說道:

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

    懇請教授賜教,謝謝~~~

  3. 雲耕子 說道:

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

    懇請教授賜教,謝謝

  4. 雲耕子 說道:

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

    • ccjou 說道:

      是的,當你花90%的力氣弄清楚問題,只要10%的力氣就得到答案。

      對角化是來自 Ax=\lambda x,所有的 x 組成完成整的線性獨立集。
      SVD來自 Av=\sigma u,我們總是能找到 orthonormal u, v

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s