線代膠囊──奇異值分解

本文的閱讀等級:中級

A 為一個 m\times n 階複矩陣。下式稱為 A 的奇異值分解 (singular value decomposition,簡稱 SVD):

\displaystyle  A=U\Sigma V^\ast

其中

  • U=\begin{bmatrix}  \mathbf{u}_1&\cdots&\mathbf{u}_m  \end{bmatrix} 是一個 m\times m 階么正矩陣 (unitary matrix),滿足 U^\ast=U^{-1}\mathbf{u}_1,\ldots,\mathbf{u}_m 稱為左奇異向量;
  • V=\begin{bmatrix}  \mathbf{v}_1&\cdots&\mathbf{v}_n  \end{bmatrix} 是一個 n\times n 階么正矩陣,滿足 V^\ast=V^{-1}\mathbf{v}_1,\ldots,\mathbf{v}_n 稱為右奇異向量;
  • \Sigma=\begin{bmatrix}  D&0\\  0&0  \end{bmatrix} 是一個 m\times n 階矩陣,D=\text{diag}(\sigma_1,\ldots,\sigma_r)\sigma_1\ge\cdots\ge\sigma_r> 0\sigma_{r+1}=\cdots=\sigma_{q}=0q=\min\{m,n\},稱為奇異值。

A 是實矩陣,只要將 (\cdot)^\ast 改為 (\cdot)^T 即可,這時 UV 稱為正交矩陣 (orthogonal matrix)。下面介紹一個簡短的奇異值分解推導法。

  1. Hermitian 矩陣可么正對角化 (unitarily diagonalizable) (見“特殊矩陣 (9):Hermitian 矩陣”)。寫出 A^\ast A 的特徵方程式

    \displaystyle  A^\ast A\mathbf{v}_i=\lambda_i\mathbf{v}_i,~~1\le i\le n

    其中右奇異向量 \{\mathbf{v}_1,\ldots,\mathbf{v}_n\} 組成一個完整的單範正交集 (complete orthonormal set),也就是說,\mathbf{v}_i^\ast\mathbf{v}_j=1i=j\mathbf{v}_i^\ast\mathbf{v}_j=0i\neq j

  2. 使用 (1),計算 A\mathbf{v}_i 的向量範數,

    \displaystyle  \Vert A\mathbf{v}_i\Vert^2=\mathbf{v}_i^{\ast}A^{\ast} A\mathbf{v}_i=\mathbf{v}_i^\ast(\lambda_i\mathbf{v}_i)=\lambda_i(\mathbf{v}_i^\ast\mathbf{v}_i)=\lambda_i\ge 0

    假設 \lambda_1\ge\cdots\ge\lambda_r>0\lambda_{r+1}=\cdots=\lambda_n=0

  3. 對於 1\le i\le r,令 \sigma_i=\sqrt{\lambda_i},且

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

    對於 i > rA\mathbf{v}_i=\mathbf{0},設 \mathbf{u}_{r+1},\ldots,\mathbf{u}_m 為任意單位向量 (\Vert\mathbf{u}_i\Vert=1) 使得左奇異向量 \{\mathbf{u}_1,\ldots,\mathbf{u}_m\} 組成一個完整地單範正交集[1]

  4. U=\begin{bmatrix}  \mathbf{u}_1&\cdots&\mathbf{u}_m  \end{bmatrix}V=\begin{bmatrix}  \mathbf{v}_1&\cdots&\mathbf{v}_n  \end{bmatrix}。因為 UV 由單範正交的行向量 (column vector) 構成,U^\ast U=I_mV^\ast V=I_n。使用 (3) A\mathbf{v}_i=\sigma_i\mathbf{u}_i1\le i\le r,且 A\mathbf{v}_i=\mathbf{0}r < i\le n,可得

    \displaystyle\begin{aligned}  AV&=A\begin{bmatrix}  \mathbf{v}_1&\cdots&\mathbf{v}_n  \end{bmatrix}\\  &=\begin{bmatrix}  A\mathbf{v}_1&\cdots&A\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}_m  \end{bmatrix}\begin{bmatrix}  \sigma_1&&&\vline&\\  &\ddots&&\vline&0\\  &&\sigma_r&\vline&\\\hline  &0&&\vline&0  \end{bmatrix}\\  &=U\Sigma.\end{aligned}

    右乘 V^\ast,即得奇異值分解 A=U\Sigma V^\ast (補充說明見[2])。

 
註解:
[1] 若 1\le i,j\le r

\displaystyle  \mathbf{u}_i^\ast\mathbf{u}_j=\left(\frac{A\mathbf{v}_i}{\sigma_i}\right)^\ast\left(\frac{A\mathbf{v}_j}{\sigma_j}\right)=\frac{\mathbf{v}_i^{\ast}A^\ast A\mathbf{v}_j}{\sigma_i\sigma_j}=\frac{\lambda_j\mathbf{v}_i^\ast\mathbf{v}_j}{\sigma_i\sigma_j}=\left\{\begin{array}{ll}  1&\text{if~}i=j\\  0&\text{if~}i\neq j,  \end{array}\right.

\{\mathbf{u}_1,\ldots,\mathbf{u}_r\} 為一個單範正交集。
[2] 若 1\le i\le r,式 \mathbf{u}_i=\sigma_i^{-1}A\mathbf{v}_i 左乘 A^\ast,可得

\displaystyle  A^\ast\mathbf{u}_i=\frac{A^\ast A\mathbf{v}_i}{\sigma_i}=\frac{\lambda_i\mathbf{v}_i}{\sigma_i}=\sigma_i\mathbf{v}_i

再左乘 A

\displaystyle  AA^\ast\mathbf{u}_i=\sigma_iA\mathbf{v}_i=\sigma_i^2\mathbf{u}_i=\lambda_i\mathbf{u}_i

奇異值分解式 AV=U\Sigma 表明 A 的行空間 (column space,即值域) 為 C(A)=\text{span}\{\mathbf{u}_1,\ldots,\mathbf{u}_r\},故 \mathbf{u}_{r+1},\ldots,\mathbf{u}_m 屬於 C(A) 的正交補餘 N(A^\ast) (見“正交補餘與投影定理”)。換句話說,A^\ast\mathbf{u}_i=\mathbf{0}AA^\ast\mathbf{u}_i=\mathbf{0}r<i\le m

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

2 Responses to 線代膠囊──奇異值分解

  1. AB 說道:

    您好
    想請問下,將一個矩陣進行奇異值分解後,又得出幾個矩陣,為何要這樣做?
    是不是有什麼特殊的用途?物理意義之類的?

發表迴響

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

WordPress.com Logo

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

Twitter picture

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

Facebook照片

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

Google+ photo

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

連結到 %s