SVD 於矩陣近似的應用

本文的閱讀等級:高級

在一些涉及資料壓縮、特徵抽取或雜音消除的分析應用中,我們常希望得到一個矩陣的最佳近似矩陣,並透過設定矩陣的秩來控制近似誤差,這個問題稱為矩陣近似。詳細的問題陳述如下:若 A 為一個 m\times n 階實矩陣,求同尺寸矩陣 \hat{A} 使最小化 \Vert A-\hat{A}\Vert,並滿足 \mathrm{rank}\hat{A}=kk<\mathrm{rank}A。奇異值分解 (singular value decomposition) 提供了最佳矩陣近似的答案,由於具備這個特性再加上優異的數值穩定性,奇異值分解已逐漸成為應用最廣泛的矩陣計算法之一。

 
矩陣的大小度量稱為矩陣範數 (norm),目前存在兩種常用的定義 (見“矩陣範數”)。第一個是由幾何向量長度推廣而得的 Frobenius 範數,定義為矩陣各元平方和的開方,計算如下:

\Vert{A}\Vert_F=\displaystyle\sqrt{\sum_{i=1}^m\sum_{j=1}^n\vert{a}_{ij}\vert^2}=\sqrt{\mathrm{trace}(A^TA)}=\sqrt{\mathrm{trace}(AA^T)}

另一個是從線性變換 A 對向量 \mathbf{x} 的長度改變誘生的比值定義,稱為2-範數 (2-norm,參閱“Hermitian 矩陣特徵值的變化界定”):

\Vert{A}\Vert_2=\displaystyle\max_{\mathbf{x}\neq\mathbf{0}}\frac{\Vert A\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}=\max_{\Vert\mathbf{x}\Vert=1}\Vert A\mathbf{x}\Vert=\sigma_{\max}

其中 \sigma_{\max} 表示 A 的最大奇異值。矩陣 A 的奇異值平方即為 A^TAAA^T 的特徵值 (見“奇異值分解(SVD)”),而矩陣譜為特徵值所成的集合,所以有些人稱此定義為「譜範數」(spectral norm);又因為定義中的向量長度計算採用歐幾里得公式,所以也有人稱之為2-範數,並以 \Vert A\Vert_2 表示。不論你採用 \Vert A\Vert_F\Vert A\Vert_2,最佳近似矩陣解都由 A 的奇異值分解決定。

 
A 的奇異值分解為

A=U\Sigma V^T

其中 UV 分別為 m\times mn\times n 階正交矩陣,U^{T}=U^{-1}V^{T}=V^{-1}\Sigmam\times n 階奇異值矩陣,\Sigma=\begin{bmatrix}    S&0\\    0&0    \end{bmatrix},其中 S=\mathrm{diag}(\sigma_1,\ldots,\sigma_r)\sigma_1\ge\cdots\ge\sigma_r>0,因此得知 \mathrm{rank}A=r。最佳矩陣近似問題要解出 \mathrm{min}_{\hat{A}}\Vert A-\hat{A}\Vert,且 \mathrm{rank}\hat{A}=k<r

 
首先我們要知道正交變換 (即正交矩陣乘法) 不改變 Frobenius 範數,因為

\Vert QA\Vert_F^2=\mathrm{trace}((QA)^T(QA))=\mathrm{trace}(A^TQ^TQA)=\mathrm{trace}(A^TA)=\Vert A\Vert_F^2

\Vert AQ\Vert_F^2=\mathrm{trace}((AQ)(AQ)^T)=\mathrm{trace}(AQQ^TA^T)=\mathrm{trace}(AA^T)=\Vert A\Vert_F^2

上式中 Q 是任意可相乘的正交矩陣。利用矩陣範數具有正交變換不變性,可得到 Frobenius 範數的奇異值表達式:

\Vert A\Vert_F=\displaystyle\Vert\Sigma\Vert_F=\sqrt{\sum_{i=1}^r\sigma_i^2}

從奇異值表達式可以清楚說明 Frobenius 範數與2-範數的差異。

 
將目標函數以 Frobenius 範數計算並改寫為

\displaystyle\min_{\hat{A}}\Vert A-\hat{A}\Vert_F=\min_{\hat{A}}\Vert U\Sigma V^T-\hat{A}\Vert_F=\min_{\hat{A}}\Vert\Sigma-U^T\hat{A}V\Vert_F

Frobenius 範數由各元平方和計算而得,既然 \Sigma 是對角矩陣,U^T\hat{A}V 也應為對角矩陣方能最小化 Frobenius 範數,亦即

U^T\hat{A}V=\begin{bmatrix}    D&0\\    0&0    \end{bmatrix}

其中 D=\mathrm{diag}(d_1,\ldots,d_r)。因此,

\hat{A}=U\begin{bmatrix}    D&0\\    0&0    \end{bmatrix}V^T

原問題等價於

\displaystyle\min_{D}\Vert S-D\Vert_F=\min_{D}\sqrt{\sum_{i=1}^r(\sigma_i-d_i)^2}

\mathrm{rank}\hat{A}=kD 恰有 k 個不為零的主對角元。因為 \sigma_i 按遞減排序,滿足誤差最小化的矩陣 D 其各元必定是 d_i=\sigma_ii=1,\ldots,k,且 d_i=0i=k+1,\ldots,r。換句話說,最佳近似矩陣 \hat{A} 保留最大的 k 個奇異值,並以零取代最小的 r-k 個奇異值。

 
同樣地,正交矩陣乘法也不改變2-範數。若 \mathbf{x}\neq\mathbf{0}

\Vert QA\mathbf{x}\Vert^2=(QA\mathbf{x})^T(QA\mathbf{x})=\mathbf{x}^TA^TQ^TQA\mathbf{x}=\mathbf{x}^TA^TA\mathbf{x}=\Vert A\mathbf{x}\Vert^2

\Vert AQ\mathbf{x}\Vert^2=(AQ\mathbf{x})^T(AQ\mathbf{x})=\mathbf{x}^TQ^TA^TAQ\mathbf{x}=\mathbf{y}^TA^TA\mathbf{y}=\Vert A\mathbf{y}\Vert^2

上式中我們令 \mathbf{y}=Q\mathbf{x}。正交變換不改變向量長度,因為

\Vert\mathbf{y}\Vert^2=\mathbf{y}^T\mathbf{y}=\mathbf{x}^TQ^TQ\mathbf{x}=\mathbf{x}^T\mathbf{x}=\Vert\mathbf{x}\Vert^2

 
採用2-範數的最佳矩陣近似解需要引用下面這個性質:設 ABm\times n 階矩陣,奇異值分解為 A=U_1\Sigma_1 V_1^TB=U_2\Sigma_2 V_2^T,奇異值矩陣 \Sigma_1\Sigma_2 的主對角元皆按遞減排序,則 \Vert A-B\Vert_2\ge\Vert\Sigma_1-\Sigma_2\Vert_2。此定理的證明過程相當冗長繁複,故在此省略。假設 \hat{A}=\hat{U}\begin{bmatrix}    D&0\\    0&0    \end{bmatrix}\hat{V}^T,其中 D=\mathrm{diag}(d_1,\ldots,d_k,0,\ldots,0)d_1\ge\cdots\ge d_k>0=d_{k+1}=\cdots=d_r,也就有

\Vert A-\hat{A}\Vert_2\ge\Vert S-D\Vert_2=\displaystyle\max_{i=1,\ldots,r}\{\vert\sigma_i-d_i\vert\}\ge\sigma_{k+1}

不難驗證等號發生於 \hat{U}=U\hat{V}=Vd_i=\sigma_ii=1,\ldots,k。這證明2-範數與 Frobenius 範數具有相同的最佳近似矩陣 \hat{A},最小誤差分別為

\Vert A-\hat{A}\Vert_F=\sqrt{\sigma_{k+1}^2+\cdots+\sigma_r^2}

\Vert A-\hat{A}\Vert_2=\sigma_{k+1}

 
參考來源:
Roger A. Horn 和 Charles R. Johnson 合著的 Matrix Analysis, 1985.

This entry was posted in 線性代數專欄, 應用之道 and tagged , , , , , , . Bookmark the permalink.

1 則回應給 SVD 於矩陣近似的應用

  1. VtripleV 說:

    看完老師的解釋,再看關聯的文章
    http://www1.math.american.edu/People/kalman/pdffiles/svd.pdf
    瞬間感覺,矩陣的近似,本質上也是類似正交投影
    正交的基底是u(i)v(j)’,奇異值就是投影量

發表迴響

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

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s