答cwj──關於奇異值分解背後的涵義

網友cwj留言:

周老師,您好!我是大陸的學生,幾乎每週都到您的“線代啟示錄”上光顧至少2次 (我是翻牆過來的,大陸這邊網路把控得很嚴)。您學問廣博,同時嚴謹而認真,真是我學習的榜樣!今天給您寫信是有一個問題要問您,我在看文獻時碰到這樣的一段描述:

Given a matrix W_{2f\times p}, decompose W into U_{2f\times K}, D_{K\times K} and V_{K\times p}^T by SVD, assuming \text{rank}(W) is K. Normalize each column of V^T . Each column unit vector \mathbf{v}_i (i=1,\ldots,p) becomes the new representation of the corresponding \mathbf{w}_i (i=1,\ldots,p) (\mathbf{w}_i is the ith column of W). This transformation is an operator that projects a \mathbb{R}^{2f} vector \mathbf{w}_i onto the \mathbb{R}^K unit sphere which preserves the subspace property, which is that any subset of \mathbf{w}_i (i=1,\ldots,p) spans a subspace of the same rank of the corresponding subset of \mathbf{v}_i (i=1,\ldots,p).

我想問的問題是:

  1. 為什麼說 \mathbf{v}_i (i=1,\ldots,p)\mathbf{w}_i (i=1,\ldots,p) 的新的表示,幾何意義我想不明白。
  2. Any subset of \mathbf{w}_i (i=1,\ldots,p) spans a subspace of the same rank of the corresponding subset of \mathbf{v}_i (i=1,\ldots,p),這個性質怎麼推導出來?

最後再次謝謝周老師!

 
答曰:

我們先整理出「瘦」奇異值分解 W=UDV^T 所揭露的訊息 (奇異值分解有「胖」和「瘦」兩種表達,見“奇異值分解 (SVD)”):

  1. W 是一個給定的 2f\times p 階數據矩陣,以行向量 (column vector) 表示為 W=\begin{bmatrix}  \mathbf{w}_1&\cdots&\mathbf{w}_p  \end{bmatrix},其中 \mathbf{w}_i\in\mathbb{R}^{2f}i=1,\ldots,p。在許多實際應用中,W 經常包含冗餘的信息,因此 2fp 遠大於 \text{rank}W=K。(為便利分析,我們甚至會以一個同階近似矩陣 \tilde{W} 來取代 W,詳見“SVD 在矩陣近似的應用”。)
  2. U 是一 2f\times K 階矩陣,以行向量表示為 U=\begin{bmatrix}  \mathbf{u}_1&\cdots&\mathbf{u}_K  \end{bmatrix},其中 \mathbf{u}_j\in\mathbb{R}^{2f}j=1,\ldots, K,稱為左奇異向量,滿足 \mathbf{u}_i^T\mathbf{u}_j=\delta_{ij},這裡 \delta_{ij}=1i=j,且 \delta_{ij}=0i\neq j。換句話說,\{\mathbf{u}_1,\ldots,\mathbf{u}_K\} 是一個單範正交集 (orthonormal set),也就有 U^TU=I_K (但 UU^T 未必是單位矩陣,除非 U 是方陣)。我們將 W 的行空間 (column space,即值域) 記為 C(W)=\text{span}\{\mathbf{w}_1,\ldots,\mathbf{w}_p\}U 的行空間記為 C(U)=\text{span}\{\mathbf{u}_1,\ldots,\mathbf{u}_K\}。因為 C(W)=C(UDV^T)\subseteq C(U) (見“矩陣乘積的子空間分析”,性質一),\dim C(W)=\text{rank}W=K,且 \dim C(U)=K (矩陣 UK 個行向量組成一線性獨立集),可知 C(W)=C(U)
  3. D 是一 K\times K 階對角矩陣,記為 D=\text{diag}(d_1,\ldots,d_K),其中 d_1\ge\cdots\ge d_K>0 稱為奇異值。
  4. V^T 是一 K\times p 階矩陣,以行向量表示為 V^T=\begin{bmatrix}  \alpha_1\mathbf{v}_1&\cdots&\alpha_p\mathbf{v}_p  \end{bmatrix},其中每一 \alpha_i>0\mathbf{v}_i\in\mathbb{R}^K 為單位向量 (unit vector),即 \Vert\mathbf{v}_i\Vert=1。不過,對於任意給定的 W\alpha_i>0 未必總是成立,例如,

    \displaystyle  \left[\!\!\begin{array}{rcr}  2&0&1\\  2&0&-1\\  -2&0&1\\  -2&0&-1  \end{array}\!\!\right]=\frac{1}{2}\left[\!\!\begin{array}{rr}  1&1\\  1&-1\\  -1&1\\  -1&-1  \end{array}\!\!\right]\begin{bmatrix}  4&0\\  0&2  \end{bmatrix}\begin{bmatrix}  1&0&0\\  0&0&1  \end{bmatrix}

    這個例子說明 \alpha_i>0 的條件是 \mathbf{w}_i\neq\mathbf{0},以下假設每一 \mathbf{w}_i 是非零向量。另外,V^T 的列向量 (row vector) 稱為右奇異向量,請勿與行向量 \alpha_i\mathbf{v}_i 混淆。

 
第一個問題:為甚麼說 \mathbf{v}_i\in\mathbb{R}^K\mathbf{w}_i\in\mathbb{R}^{2f}i=1,\ldots,p,的新的表示?純粹就數學而言,這個陳述並不正確,應該說 \alpha_i\mathbf{v}_i\in\mathbb{R}^K\mathbf{w}_i\in\mathbb{R}^{2f}i=1,\ldots,p,的新的表示。由於 2f 通常遠大於 K,這提示我們 \alpha_i\mathbf{v}_i 是原始向量 \mathbf{w}_i 的一種降維表示。為了深入理解 \alpha_i\mathbf{v}_i\mathbf{w}_i 的關係,下面我從三個不同的觀點來解釋奇異值分解背後的涵義。

 
信號產生模型

奇異值分解 W=UDV^T 表明 \mathbf{w}_i\alpha_i\mathbf{v}_i 的關係如下:

\displaystyle  \mathbf{w}_i=UD\alpha_i\mathbf{v}_i,~~~i=1,\ldots,p

暫時不考慮下標 i,則有 \mathbf{w}=UD(\alpha \mathbf{v})。設想我們有一組 K 個獨立的信號源 \alpha v_1,\ldots,\alpha v_K,記為 \alpha\mathbf{v}=\alpha(v_1,\ldots,v_K)^T,其中 \Vert\mathbf{v}\Vert^2=v_1^2+\cdots+v_K^2=1,故 \alpha>0 代表這些信號的總能量。發射信號 \alpha v_1,\ldots,\alpha v_K 產生後,等化器 (equalizer) D=\text{diag}(d_1,\ldots,d_K) 將第 j 個信號 \alpha v_j 伸縮 d_j>0 倍,1\le j\le K;再把經過等化處理過的 K 個信號送入 2f 個通道,以線性變換 U=[u_{ij}] 表示 K 個信號的組合方式,最後的接收信號為 \mathbf{w}=(w_1,\ldots,w_{2f})^T。下圖顯示信號產生模型:

\displaystyle  \begin{matrix}  \alpha v_1\\  \alpha v_2\\  \vdots\\  \alpha v_K  \end{matrix}\begin{array}{c}  \xrightarrow[]{~~d_1~~}\\  \xrightarrow[]{~~d_2~~}\\  \vdots\\  \xrightarrow[]{~~d_K~~}  \end{array}\begin{matrix}  d_1\alpha v_1\\  d_2\alpha v_2\\  \vdots\\  d_K\alpha v_K  \end{matrix}\xrightarrow[]{~~U=[u_{ij}]~~}\begin{matrix}  w_1=\sum_{j=1}^Ku_{1j}d_j\alpha v_j\\[0.5em]  w_2=\sum_{j=1}^Ku_{2j}d_j\alpha v_j\\  \vdots\\  w_{2f}=\sum_{j=1}^Ku_{2f,j}d_j\alpha v_j  \end{matrix}

發射信號 \alpha\mathbf{v}=\alpha(v_1,\ldots,v_K)^T 是否可表示接收信號 \mathbf{w}=(w_1,\ldots,w_{2f})^T ?這個思維成立的前提是不同的發射信號 \alpha\mathbf{v}\alpha'\mathbf{v}' 必須產生相異的接收信號 \mathbf{w}\mathbf{w}'。以線性代數的術語來說,信號傳輸過程 UD 是一對一的線性變換,也就是說,UD 的零空間 (nullspace,或稱核) N(UD) 不含非零向量。因為 D 是可逆矩陣且 U 有線性獨立的行向量,推知 \text{rank}(UD)=\text{rank}U=K。根據秩─零度定理,2f\times K 階矩陣 UD 的零空間維數是 \dim N(UD)=K-\text{rank}(UD)=0 (見“線性代數基本定理 (一)”),證明 UD 確實是一對一。令 \alpha_i\mathbf{v}_i\mathbf{w}_ii=1,\ldots,p,分別代表 p 組發射信號和對應的接收信號使得 \displaystyle  \mathbf{w}_i=UD(\alpha_i\mathbf{v}_i)。以上討論說明我們可以用 \alpha_i\mathbf{v}_i 表示 \mathbf{w}_ii=1,\ldots,p。然而,歸一化的 (normalized) 發射信號 \mathbf{v}_i 卻不能表示 \mathbf{w}_i,原因在於不同的 \mathbf{w}_i 可能對應相同的 \mathbf{v}_i。寫出 \mathbf{w}_i/\alpha_i=UD\mathbf{v}_i,即知 \mathbf{v}_i 決定 \mathbf{w}_i 的指向,\alpha_i 決定 \mathbf{w}_i 的長度。

 
基底變換

第二個觀點將 \mathbf{w}=UD\alpha \mathbf{v} 乘開,如下:

\displaystyle\begin{aligned}  \mathbf{w}&=\begin{bmatrix}  \mathbf{u}_1&\cdots&\mathbf{u}_K  \end{bmatrix}\begin{bmatrix}  d_1&&\\  &\ddots&\\  &&d_K  \end{bmatrix}\begin{bmatrix}  \alpha v_1\\  \vdots\\  \alpha v_K  \end{bmatrix}\\  &=(\alpha v_1)(d_1\mathbf{u}_1)+\cdots+(\alpha v_K)(d_K\mathbf{u}_K).  \end{aligned}

向量 \alpha\mathbf{v}=(\alpha v_1,\ldots,\alpha v_K)^T 指出 \mathbf{w} 所包含 d_1\mathbf{u}_1,\ldots,d_K\mathbf{u}_K 的分量 (權重)。令 \boldsymbol{\beta}=\{d_1\mathbf{u}_1,\ldots,d_K\mathbf{u}_K\}C(W) (也是 C(U)) 的一組基底。任一 \mathbf{w}\in C(W) 參考基底 \boldsymbol{\beta} 的座標向量即為 [\mathbf{w}]_{\boldsymbol{\beta}}=(\alpha v_1,\ldots,\alpha v_K)^T=\alpha\mathbf{v},圖示如下:

\displaystyle  \mathbf{w}=\begin{bmatrix}  w_1\\  \vdots\\  w_{2f}  \end{bmatrix}\rightleftharpoons\alpha\mathbf{v}=\begin{bmatrix}  \alpha v_1\\  \vdots\\  \alpha v_K  \end{bmatrix}

通過基底 \boldsymbol{\beta}\mathbf{w}\in C(W)\alpha\mathbf{v}\in\mathbb{R}^K 有一對一的對應關係,換句話說,C(W) 同構於 (isomorphic) \mathbb{R}^K (見“同構的向量空間”)。所以,座標向量 \alpha_i\mathbf{v}_i=[\mathbf{w}_i]_{\boldsymbol{\beta}} 可以表示 \mathbf{w}_ii=1,\ldots,p

 
投影算子

根據奇異值分解 \mathbf{w}_i=UD\alpha_i\mathbf{v}_ii=1,\ldots,p,我們得以從 \mathbf{w}_i 推算出 \alpha_i\mathbf{v}_i。左乘 D^{-1}U^T,可得

\displaystyle  D^{-1}U^T\mathbf{w}_i=D^{-1}U^TUD\alpha_i\mathbf{v}_i=D^{-1}D\alpha_i\mathbf{v}_i=\alpha_i\mathbf{v}_i,~~i=1,\ldots,p

在線性代數中,D^{-1}U^T 並不是一個投影算子 (projector),因為所有的投影算子 P 都是冪等 (idempotent) 矩陣,滿足 P^2=P (見“直和與投影”)。不過,科學與工程社群習慣把高維向量空間至低維向量空間的映射稱作「投影」。按照這個講法,「投影算子」D^{-1}U^T2f 維向量 \mathbf{w}_i「投影」至維數較小的 K 維向量 \alpha_i\mathbf{v}_i。如果我們要用「投影」量 \alpha_i\mathbf{v}_i 來表示 \mathbf{w}_i,定義於 C(W) 的「投影算子」D^{-1}U^T 必須是一對一的線性變換,也就是說,零空間 C(W)\cap N(D^{-1}U^T) 不含非零向量。證明於下:由於 C(W)=C(U)N(D^{-1}U^T)=N(U^T)C(U)\cap N(U^T)=\{\mathbf{0}\} (見“線性代數基本定理 (二)”),推得 C(W)\cap N(D^{-1}U^T)=\{\mathbf{0}\}。從這個角度來說,「投影算子」D^{-1}U^T\mathbf{w}_i2\mathbf{w}_i 分別「投影」至 \alpha_i \mathbf{v}_i2\alpha_i\mathbf{v}_i,故不能以 \mathbf{v}_i 表示 \mathbf{w}_i

 
第二個問題:任何 \{\mathbf{w}_1,\ldots,\mathbf{w}_p\} 的子集合生成的子空間之維數等於 \{\mathbf{v}_1,\ldots,\mathbf{v}_p\} 的對應子集合生成的子空間之維數,這個性質怎麼推導出來?

 
我們可以從前述「投影算子」觀點來回答這個問題。令 S=\{i_1,\ldots,i_m\}\{1,2,\ldots,p\} 的一個非空子集合,1\le m\le p。令 W_S 代表由 \{\mathbf{w}_i,i\in S\} 所形成的 2f\times m 階矩陣,即 W_S=\begin{bmatrix}  \mathbf{w}_{i_1}&\cdots&\mathbf{w}_{i_m}  \end{bmatrix}。同樣地,令 V^T_S 是由 \{\alpha_i\mathbf{v}_i,i\in S\} 所形成的 K\times m 階矩陣,即 V^T_S=\begin{bmatrix}  \alpha_{i_1}\mathbf{v}_{i_1}&\cdots&\alpha_{i_m}\mathbf{v}_{i_m}  \end{bmatrix}。因為

\displaystyle  C(V^T_S)=\text{span}\{\alpha_{i_1}\mathbf{v}_{i_1},\ldots,\alpha_{i_m}\mathbf{v}_{i_m}\}=\text{span}\{\mathbf{v}_{i_1},\ldots,\mathbf{v}_{i_m}\}

我們只要證明 \dim C(W_S)=\dim C(V_S^T) 即可。假設「投影算子」D^{-1}U^T 的定義域為 C(W_S)。因為 V_S^T=D^{-1}U^TW_S,可知 D^{-1}U^T 的值域為 C(V_S^T),圖示如下:

\displaystyle  C(W_S)\longrightarrow\boxed{~~{D^{-1}U^T}~~}\longrightarrow ~C(V_S^T)

利用「維數守恆定律」,也就是秩─零度定理 (見“運用輸入輸出模型活化秩─零度定理”),

\displaystyle\begin{aligned}  \dim C(W_S)&=\dim C(V_S^T)+\dim\left( C(W_S)\cap N(D^{-1}U^T)\right)\\  &=\dim C(V_S^T)+\dim \left(C(W_S)\cap N(U^T)\right).  \end{aligned}

C(W_S)\subseteq C(W)=C(U)C(U)\cap N(U^T)=\{\mathbf{0}\},推得 C(W_S)\cap N(U^T)=\{\mathbf{0}\},故 \dim C(W_S)=\dim C(V_S^T)

 
最後解釋何以文獻用單位向量 \mathbf{v}_i 來表示 \mathbf{w}_ii=1,\ldots,p。舉例來說,資訊 (信息) 檢索是奇異值分解的一個經典應用,\mathbf{w}_i 代表文件 i 的量測值 (例如,特定字詞出現的頻率),\mathbf{v}_i 代表主題的本徵 (見“SVD 於資訊檢索與文本搜尋的應用”)。文件 i 和文件 j 的相似性反映在 \mathbf{v}_i\mathbf{v}_j 之間,而非 \mathbf{w}_i\mathbf{w}_j 之間,因為後者引入等化效應,即奇異值矩陣 D。在比較文件相似性的過程中,我們僅關心 \mathbf{v}_i\mathbf{v}_j 的方向是否一致,並不在乎它們的長度大小 (即 \alpha_i\alpha_j)。這時候,餘弦相似性 (cosine similarity)──兩個向量在內積空間的夾角的餘弦值──可用來度量 \mathbf{v}_i\mathbf{v}_j 之間的相似性,即單位向量 \mathbf{v}_i\mathbf{v}_j 的內積。我們無法從數學上證明餘弦相似性的正確性,而是應用領域本身決定了它的適用性。所以,即便以 \mathbf{v}_i 表示 \mathbf{w}_ii=1,\ldots,p,不滿足數學所要求的一對一性質,但因為不考慮向量的規模大小,應用科學研究者一般是不會在意這一丁點瑕疵。數學與現實應用總是有一步之遙。

Advertisements
本篇發表於 答讀者問, 二次型 並標籤為 , , 。將永久鏈結加入書籤。

1 則回應給 答cwj──關於奇異值分解背後的涵義

  1. CWJ 說道:

    謝謝周老師,我剛讀完您的解釋,系統而又詳盡,使我對SVD的理解,以及對從純數學表示到實際工程應用之間的“神似而貌不一定合的淵源關係”有了更為深刻的理解!非常感謝周老師!

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s