SVD 於矩陣近似的應用

本文的閱讀等級：高級

在一些涉及資料壓縮、特徵抽取或雜音消除的分析應用中，我們常希望得到一個矩陣的最佳近似矩陣，並透過設定矩陣的秩來控制近似誤差，這個問題稱為矩陣近似。詳細的問題陳述如下：若 $A$ 為一個 $m\times n$ 階實矩陣，求同尺寸矩陣 $\hat{A}$ 使最小化 $\Vert A-\hat{A}\Vert$ ，並滿足 $\mathrm{rank}\hat{A}=k$ 且 $k<\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^TA$ 和 $AA^T$ 的特徵值 (見“奇異值分解(SVD)”)，而矩陣譜為特徵值所成的集合，所以有些人稱此定義為「譜範數」(spectral norm)；又因為定義中的向量長度計算採用歐幾里得公式，所以也有人稱之為2-範數，並以 $\Vert A\Vert_2$ 表示。不論你採用 $\Vert A\Vert_F$ 或 $\Vert A\Vert_2$ ，最佳近似矩陣解都由 $A$ 的奇異值分解決定。

設 $A$ 的奇異值分解為

$A=U\Sigma V^T$ ，

其中 $U$ 和 $V$ 分別為 $m\times m$ 和 $n\times n$ 階正交矩陣， $U^{T}=U^{-1}$ ， $V^{T}=V^{-1}$ ， $\Sigma$ 為 $m\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}=k$ ， $D$ 恰有 $k$ 個不為零的主對角元。因為 $\sigma_i$ 按遞減排序，滿足誤差最小化的矩陣 $D$ 其各元必定是 $d_i=\sigma_i$ ， $i=1,\ldots,k$ ，且 $d_i=0$ ， $i=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-範數的最佳矩陣近似解需要引用下面這個性質：設 $A$ 和 $B$ 為 $m\times n$ 階矩陣，奇異值分解為 $A=U_1\Sigma_1 V_1^T$ ， $B=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}=V$ ， $d_i=\sigma_i$ ， $i=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.

1 Response to SVD 於矩陣近似的應用

VtripleV says:

01/14/2011 at 5:24 pm

看完老師的解釋,再看關聯的文章

Click to access svd.pdf

瞬間感覺,矩陣的近似,本質上也是類似正交投影
正交的基底是u(i)v(j)’,奇異值就是投影量

	陳倍恩 on 線性代數的第一堂課──矩陣乘法的定義
	輕鬆談如何教學二項式定理？… on 牛頓的二項式定理 (上)
	madhouse on 高斯消去法
	WishMobile on 翻轉 LU 分解
	周子傑 on Karush-Kuhn-Tucker (KKT) 條件
	Cloud Huang on 線性泛函與伴隨