奇異值分解 (SVD)

本文的閱讀等級:中級

奇異值分解 (singular value decomposition,以下簡稱 SVD) 被譽為矩陣分解的「瑞士刀」和「勞斯萊斯」[1],前者說明它的用途非常廣泛,後者意味它是值得珍藏的精品。在“線性代數基本定理 (四)”一文,我們介紹了 SVD 的推導,並於矩陣的四個子空間分析平台解釋其幾何涵義,本文簡述 SVD 重點並舉一例說明分解式的計算步驟。

美國史丹佛大學教授格魯布 (Gene Golub) 於矩陣運算的貢獻造就 SVD 成為今日最重要的線性代數應用 From http://www.cs.nyu.edu/overton/genearoundtheworld/gene.jpg

 
A 為一個 m\times n 階實矩陣,r=\mathrm{rank}A,SVD 具有以下形式:

A=U\Sigma V^T

其中 Um\times m 階,Vn\times n 階,\Sigmam\times n 階。特別的是,方陣 UV 都是實正交矩陣 (orthogonal matrix),也就是說,U^T=U^{-1}V^T=V^{-1}\Sigma 是 (類) 對角矩陣,如下:

\Sigma=\begin{bmatrix}    \sigma_{1} & 0 & 0 & 0 &\cdots &0\\    0 & \ddots & 0 & \vdots & \cdots & 0\\    0 & 0 & \sigma_{r} & 0 &\cdots & 0\\    0 & \cdots & 0 & 0 & \cdots &0\\  \vdots&\ddots&\vdots&\vdots&\ddots&\vdots\\    0 & \cdots & 0 & 0 & \cdots & 0    \end{bmatrix}

主對角元 \sigma_i>0i=1,2,\ldots,r,且 \sigma_{r+1}=\cdots\sigma_{p}=0p=\min\{m,n\},稱為奇異值 (singular values)。注意,SVD 的分解不具有唯一性。為了便利應用,我們習慣將奇異值由大至小排序:\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r>0

 
利用圖示可以幫助我們了解 SVD 的矩陣結構。SVD 最特別的地方是 \Sigma 的多數元為零,圖一的白色區塊以及黃色區塊的非對角元皆為零。

svd1

圖一 奇異值分解結構

 
U 的行向量 (column vector)為 \mathbf{u}_ii=1,\ldots,mV 的行向量為 \mathbf{v}_jj=1,\ldots,nA=U\Sigma V^T 可以表示為 r 個秩-1 (rank-one) 矩陣之和:

\begin{aligned}  A&=\begin{bmatrix}  \mathbf{u}_1&\mathbf{u}_2&\cdots&\mathbf{u}_m  \end{bmatrix}  \begin{bmatrix}  \sigma_1&&&&\\  &\sigma_2&&&\\  &&\ddots&&\\  &&&\sigma_r&\\  &&&&\ddots  \end{bmatrix}\begin{bmatrix}  \mathbf{v}_1^T\\  \mathbf{v}_2^T\\  \vdots\\  \mathbf{v}_n^T  \end{bmatrix}\\  &=\begin{bmatrix}  \sigma_1\mathbf{u}_1&\sigma_2\mathbf{u}_2&\cdots&\sigma_r\mathbf{u}_r&\mathbf{0}&\cdots&\mathbf{0}  \end{bmatrix}  \begin{bmatrix}  \mathbf{v}_1^T\\  \mathbf{v}_2^T\\  \vdots\\  \mathbf{v}_n^T  \end{bmatrix}\\  &=\sigma_1\mathbf{u}_1\mathbf{v}_1^T+\sigma_2\mathbf{u}_2\mathbf{v}_2^T+\cdots+\sigma_r\mathbf{u}_r\mathbf{v}_r^T.\end{aligned}

上式指出 A 僅由 U 的前 r 個行向量 (以 U_r 表示),V^T 的前 r 個列向量 (以 V_r^T 表示),以及 \Sigma 的左上 r\times r 分塊決定 (以 \Sigma_r 表示),稱為「瘦」奇異值分解,如圖二所示。這個結果看似不起眼,其實它有重大的意義。矩陣 A 總共有 m\times n 個元,U_rm\times r 個元,V_r^Tr\times n 個元,\Sigma_r 則只需儲存主對角的 r 個非零元。若以 SVD 形式儲存,總計有 (m+n+1)\times r 個元。當 r 遠小於 mn 時,利用矩陣的 SVD 可以大幅減少儲存量。

svd2

圖二 瘦奇異值分解

 
我們可以將 SVD 視為變換矩陣 A 的三個分解步驟:旋轉 V^T,伸縮 \Sigma,再旋轉 U,圖三顯示 2\times 2 階矩陣的分解變換。另一方面,\Sigma 也可以視為變換矩陣 A 參考了基底 \{\mathbf{v}_1,\ldots,\mathbf{v}_n\}\{\mathbf{u}_1,\ldots,\mathbf{u}_m\} 的主對角變換矩陣 (見“線性變換觀點下的奇異值分解”)。

svd32

圖三 奇異值分解映射表達

 
SVD 的計算主要是利用下面幾個性質:

(1) A^TAAA^T 的非零特徵值為 \sigma_i^2i=1,2,\ldots,rr=\mathrm{rank}A。注意,A^TAAA^T 是半正定 (positive semidefinite) 矩陣,其特徵值必定不為負數。

(2) A^TA 的單位特徵向量為 \mathbf{v}_j

A^TA\mathbf{v}_j=\sigma_j^2\mathbf{v}_j,~~j=1,2,\ldots,n

(3) AA^T 的單位特徵向量為 \mathbf{u}_j

AA^T\mathbf{u}_j=\sigma_j^2\mathbf{u}_j,~~j=1,2,\ldots,m

(4) 對於 j=1,2,\ldots,r\mathbf{u}_j\mathbf{v}_j 具有以下關係:

A\mathbf{v}_j=\sigma_j\mathbf{u}_j

A^T\mathbf{u}_j=\sigma_j\mathbf{v}_j.

對應奇異值 \sigma_j\mathbf{u}_j 稱為左奇異向量,\mathbf{v}_j 稱為右奇異向量。

 
底下舉一個例說明奇異值分解計算程序。考慮 4\times 5 階矩陣[2]

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

步驟 1:計算交互乘積矩陣 A^TA

A^TA=\begin{bmatrix}    1&0&0&0&2\\    0&16&0&0&0\\    0&0&9&0&0\\    0&0&0&0&0\\    2&0&0&0&4    \end{bmatrix}

步驟 2:求 A^TA 的特徵值與對應的特徵向量,將特徵值大至小排序:

\lambda_1=16,~\lambda_2=9,~\lambda_3=5,~\lambda_4=0,~\lambda_5=0

對應的單位特徵向量依序為

\mathbf{v}_1=\begin{bmatrix}    0\\    1\\    0\\    0\\    0    \end{bmatrix},~\mathbf{v}_2=\begin{bmatrix}    0\\    0\\    1\\    0\\    0    \end{bmatrix},~\mathbf{v}_3=\begin{bmatrix}    \sqrt{0.2}\\    0\\    0\\    0\\    \sqrt{0.8}    \end{bmatrix},~\mathbf{v}_4=\begin{bmatrix}    0\\    0\\    0\\    1\\    0    \end{bmatrix},~\mathbf{v}_5=\begin{bmatrix}    -\sqrt{0.8}\\    0\\    0\\    0\\    \sqrt{0.2}    \end{bmatrix}

非零奇異值為 \sigma_1=\sqrt{\lambda_1}=4\sigma_2=\sqrt{\lambda_2}=3\sigma_3=\sqrt{\lambda_3}=\sqrt{5}

步驟 3:設定 \SigmaV

\Sigma=\begin{bmatrix}    4&0&0&0&0\\    0&3&0&0&0\\    0&0&\sqrt{5}&0&0\\    0&0&0&0&0    \end{bmatrix}

V=\begin{bmatrix}    0&0&\sqrt{0.2}&0&-\sqrt{0.8}\\    1&0&0&0&0\\    0&1&0&0&0\\    0&0&0&1&0\\    0&0&\sqrt{0.8}&0&\sqrt{0.2}    \end{bmatrix}

步驟 4:最後計算 U。對於 j=1,2,\ldots,r,此例 r=3,可直接計算 \mathbf{u}_j=\frac{1}{\sigma_j}A\mathbf{v}_j,結果如下:

\mathbf{u}_1=\begin{bmatrix}    0\\    0\\    0\\    1    \end{bmatrix},~\mathbf{u}_2=\begin{bmatrix}    0\\    1\\    0\\    0    \end{bmatrix},~\mathbf{u}_3=\begin{bmatrix}    1\\    0\\    0\\    0    \end{bmatrix}

\mathbf{u}_4 則由 Gram-Schmidt 正交化程序求出 (“Gram-Schmidt 正交化與 QR 分解”):

\mathbf{u}_4=\begin{bmatrix}    0\\    0\\    1\\    0    \end{bmatrix}

合併上面結果,

U=\begin{bmatrix}    0&0&1&0\\    0&1&0&0\\    0&0&0&1\\    1&0&0&0    \end{bmatrix}

 
在“通過推導偽逆矩陣認識線性代數的深層結構”一文,我曾經介紹 SVD 於最小平方近似解的應用並一路推導出偽逆矩陣 (pseudo-inverse),從而徹底解決了線性方程的求解問題。了解該篇專欄內容需要相當的耐心與毅力,但付出絕對值得,因為這個主題是線性代數的聖母峰。

 
註解
[1] Gene H. Golub, Michacel W. Mahoney, Petros Drineas, and Lek-Heng Lim, Bridging the Gap Between Numerical Linear Algebra, Theoretical Computer Science, and Data Applications, SIAM News, Vol. 39, No. 8, 2006.
[2] 取自 維基百科:Singular value decomposition

相關閱讀:
Advertisements
This entry was posted in 線性代數專欄, 二次型 and tagged , , , , , . Bookmark the permalink.

35 則回應給 奇異值分解 (SVD)

  1. 言下 說:

    u4算錯了,是[0;0;-1;0]
    u4正交化是對哪個矩陣正交化?

  2. ccjou 說:

    \mathbf{u}_4\mathbf{u}_ii=1,2,3 都正交,因此為 (0,0,1,0)(0,0,-1,0), 兩者皆可。
    Gram-Schmidt 正交化程序是說隨便挑一個向量不在 \mathbf{u}_ii=1,2,3,所擴張的子空間內,例如 \mathbf{x}=(1,2,3,4),計算如下:
    \mathbf{u}_4=\mathbf{x}-(\mathbf{x}^T\mathbf{u}_1)\mathbf{u}_1-(\mathbf{x}^T\mathbf{u}_2)\mathbf{u}_2-(\mathbf{x}^T\mathbf{u}_3)\mathbf{u}_3=(0,0,3,0),然後再正規化即可。

  3. Edman 說:

    請問為何步驟2中, A^TA的特徵值是16,9,5,0,0, 而不是16,9,4,1,0
    (1 -x)(16 -x)(9 -x)( -x)(4 -x) =
    = (1 -x)*(16 -x)*(9 -x)*( -x)*(4 -x)
    = -576*x +820*x^2 -273*x^3 +30*x^4 -x^5
    = -x*(x -1)*(x -4)*(x -9)*(x -16)

  4. Edman 說:

    (1 -x)(16 -x)(9 -x)( -x)(4 -x) =
    = (1 -x)*(16 -x)*(9 -x)*( -x)*(4 -x)
    = -576*x +820*x^2 -273*x^3 +30*x^4 -x^5
    = -x*(x -1)*(x -4)*(x -9)*(x -16)

  5. ccjou 說:

    TO Edman,

    A^TA 的特徵值確實是 16, 9, 5, 0, 0

    你的算式十分複雜,我相信應該還有更好的計算方法。

  6. levinc 說:

    今天讀了SVD一系列文章,真是太棒了! 有醍醐灌頂的感覺!XD 而且深感線性代數這門基礎學問,像是拼拼圖一樣,有趣極了!

  7. ccjou 說:

    有同學問如何快速計算上面 A^TA 的特徵值?
    重新置換行列,A^TA 相似於
    \begin{bmatrix} 16&0&0&&\\ 0&9&0&&\\ 0&0&0&&\\ &&&1&2\\ &&&2&4 \end{bmatrix}
    可知 A^TA 的特徵值為16, 9, 0 和 B=\begin{bmatrix} 1&2\\ 2&4 \end{bmatrix} 的特徵值。因為 B 不可逆,故有一特徵值0,另一個特徵值即為 \mathrm{trace}B=1+4=5

  8. Watt Lin 說:

    老師抱歉,請允許我談個「題外話」:
    「禪」字,可分解為「示」與「單」,聯想到「簡單表示法」。
    「單」可再分解為「口」、「口」、「田」、「十」。
    「口」、「口」、「田」這三個字,看起來有點像矩陣的外廓。
    「十」讓我想到分隔線,左上區為對角矩陣,右上、左下、右下區域皆為0。
    老師說,SVD這個主題是線性代數的聖母峰。
    如果說,SVD具有甚深禪意,是否可行?
    (假如老師覺得這篇回應不妥,可以刪去,我不會在意。)

    • ccjou 說:

      你的解文說字令人嘆為觀止,中文字裡面也有超乎部首的分解意涵。太有趣了!

      確實我在教學光碟的最後一(或二)堂課也說過:SVD是線性代數的聖母峰。原因有二:(1)SVD幾乎涵蓋所有線性代數的核心概念(big idea),(2)「奇異值分解(SVD)」,即上面的這篇文章,總是霸佔本站“近期最多人點閱”的榜首(當然這是後話)。如果「禪」是“最高境界”的一種暗喻,那麼毫不猶豫地,我同意SVD深具禪意。

      PS:系統管理員和我從未刪去讀者的任何迴響。少數迴響可能莫名其妙地不見了,那是因為以前的系統曾遭到病毒攻擊,不得已重灌系統造成部分資料流失。

  9. 說:

    AA^t 和 A^tA 做SVD有差嗎???@@
    當看到題目給的矩陣不知道要怎麼判斷怎麼分解!

    • ccjou 說:

      A^tA或AA^t都可求出SVD。你可以挑選其中階數較小或數值較簡單的,如果選擇AA^t,這時要使用上述性質(3),先解出奇異值和左奇異向量u,再計算右奇異向量v。你可以試試。

  10. SVD 方法是否可判斷相依 說:

    老師請問一下SVD方法可以判斷相依嗎??

    • ccjou 說:

      可以。上文提及 m\times n 矩陣 A 的矩陣秩 r=\mathrm{rank}A 即為 A 的非零奇異值總數,r\le mr\le n。若 r<m,則 A 有線性相依的列向量。若 r<n,則 A 有線性相依的行向量。

  11. SVD 方法是否可判斷相依 說:

    謝謝老師,那當矩陣相依,可以找出相依的係數嗎??
    感激老師,現在非常需要判斷相依並且找出相依的係數

  12. 說:

    當一個非方陣矩陣 A 經 PseudoInverse 方法並乘上自己本身 A 的矩陣,如果不為單位矩陣代表矩陣式中有相依,想請問能有效直接判斷矩陣中哪一列為相依嗎??

    感激老師不辭辛勞的解答

  13. 說:

    SVD 方法能判斷 非線性獨立或相依嗎??
    如果不行,想請問原因是因為??
    謝謝老師…

  14. eastone 說:

    有个问题想请教下,就是如何由性质(1)(2)(3)推导出性质(4)呢,
    就是这个(4)对于j=1,2,\ldots,r\mathbf{u}_j\mathbf{v}_j具有以下关系:

    A\mathbf{v}_j=\sigma_j\mathbf{u}_j

    A^T\mathbf{u}_j=\sigma_j\mathbf{v}_j

  15. leehwi 說:

    Reblogged this on leehwi and commented:
    现代启示录

  16. Joshawen 說:

    以前念書時一直感到疑惑,課本在教奇異值分解只舉實矩陣為例,若要推廣到複矩陣,莫非只要把運算過程中的轉置矩陣皆推廣成Hermitian即可?另外,算過幾次複矩陣,似乎奇異值分解過程中的對角化矩陣恆為實矩陣,這是因為(A^H)A(個人Hermitian符號習慣用H)為正定矩陣緣故?
    寫到這裡,其實我最大的疑惑還是,不知為何線代授課時不在一開始便開宗明義定義複矩陣,由此建構整套系統?在面對複矩陣時,個人有時會有一知半解,知識建構不完整之感,需要上網查閱相關資料確認,不是不好,畢竟人的求知並不限於學校,但這也是否一方面意味著所學其實不甚完整,某些部分流於破碎?瀏覽過一些教科書,但目前發現課程章節的安排上大同小異,大都將複矩陣壓縮成一小節或甚至未獨立成篇,連帶影響了課程規劃,但我想這是編寫教材者本身授課理念以及如何詮釋一門學問核心價值的問題,這方面還有賴教授根據多年教學經驗,不吝分享想法,這樣的課程安排是否為普遍受現今學界認同,或者只是因為教材沒得選擇?

    寫得有點囉嗦,謝謝教授不必勞苦的回覆訪客的問題

  17. Jason 說:

    老師您好 感覺瘦svd分解與資料探勘中的技術有關?! 若對資料(table m*n)做SVD分解 至於中間的矩陣所儲存下來的奇異值是主成份囉? 有沒有什麼理解方法,不知道怎麼串在一起

  18. cjfuture 說:

    令 U 的行向量為 \mathbf{u}_j,V 的行向量為 \mathbf{v}_j,A=U\Sigma V^T 可以表示為 r 個秩-1(rank-one)矩陣之和
    应该是U的列向量吧

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s