SVD分解

**奇異值分解**（singular value decomposition）是線性代數中一種重要的矩陣分解，在信號處理、統計學等領域有重要應用。奇異值分解在某些方面與對稱矩陣或厄米矩陣基於特徵向量的對角化類似。然而這兩種矩陣分解儘管有其相關性，但還是有明顯的不同。對稱陣特徵向量分解的基礎是譜分析，而奇異值分解則是譜分析理論在任意矩陣上的推廣。

## 理論描述

假設 _M_ 是一個 _m×n_ 階矩陣，其中的元素全部屬於域 _K_，也就是實數域或複數域。如此則存在一個分解使得

　
: $M=U\Sigma V^{*},\,$

其中 _U_ 是 _m×m_ 階酉矩陣；Σ 是 _m×n_ 階非負實數對角矩陣；而 _V\*_，即 _V_ 的共軛轉置，是 _n×n_ 階酉矩陣。這樣的分解就稱作 _M_ 的**奇異值分解**。Σ 對角線上的元素 Σi,_i_ 即為 _M_ 的**奇異值**。

常見的做法是將奇異值由大而小排列。如此 Σ 便能由 _M_ 唯一確定了。（雖然 _U_ 和 _V_ 仍然不能確定。）

### 直觀的解釋

在矩陣 _M_ 的奇異值分解中

　
: $M=U\Sigma V^{*},\,$

* _V_ 的列（columns）組成一套對 $M\,$ 的正交 "輸入" 或 "分析" 的基向量。這些向量是 $M^{*}\,M$ 的特徵向量。
* _U_ 的列（columns）組成一套對 $M\,$ 的正交 "輸出" 的基向量。這些向量是 $MM^{*}\,$ 的特徵向量。
* Σ 對角線上的元素是奇異值，可視為是在輸入與輸出間進行的純量的 "膨脹控制"。這些是 $MM^{*}\,$ 及 $M^{*}\,M$ 的特徵值的非負平方根，並與 _U_ 和 _V_ 的行向量相對應。

## 奇異值和奇異向量，以及他們與奇異值分解的關係

一個非負實數 σ 是 _M_ 的一個奇異值僅當存在 _K_m 的單位向量 _u_ 和 _K_n 的單位向量 _v_ 如下：

　
: $Mv=\sigma u\,{\text{ and }}M^{*}u=\sigma v.\,\!$

其中向量 _u_ 和 _v_ 分別為 σ 的左奇異向量和右奇異向量。

對於任意的奇異值分解

　
: $M=U\Sigma V^{*}\,\!$

矩陣 Σ 的對角線上的元素等於 _M_ 的奇異值. _U_ 和 _V_ 的列分別是奇異值中的左、右奇異向量。因此，上述定理表明：

* 一個 m×n 的矩陣至多有 _p_ = min(_m_,_n_) 個不同的奇異值；
* 總能在 _K_m 中找到由 _M_ 的左奇異向量組成的一組正交基 _U_，；
* 總能在 _K_n 找到由 _M_ 的右奇異向量組成的一組正交基 _V_，。

如果對於一個奇異值，可以找到兩組線性無關的左（右）奇異向量，則該奇異值稱為簡併的（或退化的）。

非退化的奇異值在最多相差一個相位因子 $\exp(i\phi )$ （若討論限定在實數域內，則最多相差一個正負號）的意義下具有唯一的左、右奇異向量。因此，如果 _M_ 的所有奇異值都是非退化且非零，則除去一個可以同時乘在 $U,V$ 上的任意的相位因子外， $M$ 的奇異值分解唯一。

根據定義，退化的奇異值具有不唯一的奇異向量。因為，如果 _u_1 和 _u_2 為奇異值 σ 的兩個左奇異向量，則它們的任意歸一化線性組合也是奇異值 σ 一個左奇異向量，右奇異向量也具有類似的性質。因此，如果 _M_ 具有退化的奇異值，則它的奇異值分解是不唯一的。

## 例子

觀察一個 4×5 的矩陣

　
: $M={\begin{bmatrix}1&0&0&0&2\\0&0&3&0&0\\0&0&0&0&0\\0&4&0&0&0\end{bmatrix}}$

M 矩陣的奇異值分解如下 $U\Sigma V^{*}$

　
: $U={\begin{bmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{bmatrix}},\;\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&1&0&0&0\\0&0&1&0&0\\{\sqrt {0.2}}&0&0&0&{\sqrt {0.8}}\\0&0&0&1&0\\{\sqrt {0.8}}&0&0&0&-{\sqrt {0.2}}\end{bmatrix}}$

注意矩陣 $\Sigma $ 的所有非對角元為 0。矩陣 $U$ 和 $V^{*}$ 都是酉矩陣，它們乘上各自的共軛轉置都得到單位矩陣。如下所示。在這個例子中，由於 $U$ 和 $V^{*}$ 都是實矩陣，故它們都是正交矩陣。

　
: $UU^{*}={\begin{bmatrix}0&0&1&0\\0&1&0&0\\0&0&0&1\\1&0&0&0\end{bmatrix}}\cdot {\begin{bmatrix}0&0&0&1\\0&1&0&0\\1&0&0&0\\0&0&1&0\end{bmatrix}}={\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\end{bmatrix}}\equiv I_{4}$

　
: $VV^{*}={\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}}\cdot {\begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\{\sqrt {0.2}}&0&0&0&{\sqrt {0.8}}\\0&0&0&1&0\\{\sqrt {0.8}}&0&0&0&-{\sqrt {0.2}}\end{bmatrix}}={\begin{bmatrix}1&0&0&0&0\\0&1&0&0&0\\0&0&1&0&0\\0&0&0&1&0\\0&0&0&0&1\end{bmatrix}}\equiv I_{5}$

由於 $\Sigma $ 有一個對角元是零，故這個奇異值分解值不是唯一的。例如，選擇 $V$ 使得

　
: $V^{*}={\begin{bmatrix}0&1&0&0&0\\0&0&1&0&0\\{\sqrt {0.2}}&0&0&0&{\sqrt {0.8}}\\{\sqrt {0.4}}&0&0&{\sqrt {0.5}}&-{\sqrt {0.1}}\\-{\sqrt {0.4}}&0&0&{\sqrt {0.5}}&{\sqrt {0.1}}\end{bmatrix}}$

能得到 $M$ 的另一個奇異值分解。

## 與特徵值分解的聯繫

奇異值分解能夠用於任意 $m\times n$ 矩陣，而特徵分解只能適用於特定類型的方陣，故奇異值分解的適用範圍更廣。不過，這兩個分解之間是有關聯的。給定一個 _M_ 的奇異值分解，根據上面的論述，兩者的關係式如下：

　
: $M^{*}M=V\Sigma ^{*}U^{*}\,U\Sigma V^{*}=V(\Sigma ^{*}\Sigma )V^{*}\,$

　
: $MM^{*}=U\Sigma V^{*}\,V\Sigma ^{*}U^{*}=U(\Sigma \Sigma ^{*})U^{*}\,$

關係式的右邊描述了關係式左邊的特徵值分解。於是：

 * $V$ 的列向量（右奇異向量）是 $M^{*}M$ 的特徵向量。
* $U$ 的列向量（左奇異向量）是 $MM^{*}$ 的特徵向量。
* $\Sigma $ 的非零對角元（非零奇異值）是 $M^{*}M$ 或者 $MM^{*}$ 的非零特徵值的平方根。

特殊情況下，當 _M_ 是一個正規矩陣（因而必須是方陣）根據譜定理，_M_ 可以被一組特徵向量酉對角化，所以它可以表為：

　
: $M=UDU^{*}$

其中 _U_ 為一個酉矩陣，_D_ 為一個對角陣。如果 _M_ 是半正定的， $M=UDU^{*}$ 的分解也是一個奇異值分解。

然而，一般矩陣的特徵分解跟奇異值分解不同。特徵分解如下：

　
: $M=UDU^{-1}$

其中 _U_ 是不需要是酉的，_D_ 也不需要是半正定的。而奇異值分解如下：

　
: $M=U\Sigma V^{*}$

其中 $\Sigma $ 是對角半正定矩陣，_U_ 和 _V_ 是酉矩陣，兩者除了通過矩陣 _M_ 沒有必然的聯繫。

## 幾何意義

因為 _U_ 和 _V_ 都是酉的，我們知道 _U_ 的列向量 _u_1,...,_um_ 組成了 _K_m 空間的一組標準正交基。同樣，_V_ 的列向量 _v_1,...,_vn_ 也組成了 _K_n 空間的一組標準正交基（根據向量空間的標準點積法則）。

矩陣 $M$ 代表從 $K^{n}$ 到 $K^{m}$ 的一個線性映射 ${\mathcal {T}}$ ： $x\rightarrow Mx$ 。通過這些標準正交基，這個變換可以用很簡單的方式進行描述： ${\mathcal {T}}(v_{i})=\sigma _{i}u_{i},i=1,\ldots ,\min(m,n)$ ，其中 $\sigma _{i}$ 是 $\Sigma $ 中的第 _i_ 個對角元。當 $i>\min(m,n)$ 時， ${\mathcal {T}}(v_{i})=0$ 。

這樣，SVD 分解的幾何意義就可以做如下的歸納：對於每一個線性映射 ${\mathcal {T}}:K^{n}\rightarrow K^{m}$ ， ${\mathcal {T}}$ 的奇異值分解在原空間與像空間中分別找到一組標準正交基，使得 ${\mathcal {T}}$ 把 $K^{n}$ 的第 $i$ 個基向量映射為 $K^{m}$ 的第 $i$ 個基向量的非負倍數，並將 $K^{n}$ 中餘下的基向量映射為零向量。換句話說，線性變換 ${\mathcal {T}}$ 在這兩組選定的基上的矩陣表示為所有對角元均為非負數的對角矩陣。

## 應用

### 求廣義逆陣（偽逆）

奇異值分解可以被用來計算矩陣的廣義逆陣（偽逆）。若矩陣 _M_ 的奇異值分解為 $M=U\Sigma V^{*}$ ，那麼 _M_ 的偽逆為

　
: $M^{+}=V\Sigma ^{+}U^{*},\,$

其中 $\Sigma ^{+}$ 是 $\Sigma $ 的偽逆，是將 $\Sigma $ 主對角線上每個非零元素都求倒數之後再轉置得到的。求偽逆通常可以用來求解最小二乘法問題。

### 列空間、零空間和秩

奇異值分解的另一個應用是給出矩陣的列空間、零空間和秩的表示。對角矩陣 $\Sigma $ 的非零對角元素的個數對應於矩陣 $M$ 的秩。與零奇異值對應的右奇異向量生成矩陣 $M$ 的零空間，與非零奇異值對應的左奇異向量則生成矩陣 $M$ 的列空間。在線性代數數值計算中奇異值分解一般用於確定矩陣的有效秩，這是因為，由於捨入誤差，秩虧矩陣的零奇異值可能會表現為很接近零的非零值。

### 矩陣近似值

奇異值分解在統計中的主要應用為主成分分析（PCA）。數據集的特徵值（在 SVD 中用奇異值表徵）按照重要性排列，降維的過程就是捨棄不重要的特徵向量的過程，而剩下的特徵向量張成空間為降維後的空間。

## 幾種程式語言中計算 SVD 的函式範例

* Mathematica:

　
: `{U, Σ, V}=SingularValueDecomposition[a]`

`* MATLAB：``` : `[b c d]=svd(x)` ```* OpenCV:``` : `void cvSVD( CvArr* A, CvArr* W, CvArr* U=NULL, CvArr* V=NULL, int flags=0 )` ```* Python（使用SciPy（頁面存檔備份，存於網際網路檔案館）庫）` `` : `U,s,Vh = scipy.linalg.svd(A)` ```* R:``` : `S=svd(x)` ```## 歷史``## 參見``## 外部連結``* LAPACK users manual （頁面存檔備份，存於網際網路檔案館） gives details of subroutines to calculate the SVD (see also [1]（頁面存檔備份，存於網際網路檔案館）).
* Applications of SVD on PC Hansen's web site.
* Introduction to the Singular Value Decomposition by Todd Will of the University of Wisconsin--La Crosse.
* Los Alamos group's book chapter（頁面存檔備份，存於網際網路檔案館） has helpful gene data analysis examples.
* MIT Lecture（頁面存檔備份，存於網際網路檔案館） series by Gilbert Strang. See Lecture #29 on the SVD.
* Java SVD library routine.
* Java applet demonstrating the SVD.
* Java script （頁面存檔備份，存於網際網路檔案館） demonstrating the SVD more extensively, paste your data from a spreadsheet.
* Chapter from "Numerical Recipes in C"（頁面存檔備份，存於網際網路檔案館） gives more information about implementation and applications of SVD.
* Online Matrix Calculator Performs singular value decomposition of matrices.``## 參考文獻``* Demmel, J. and Kahan, W. (1990). Computing Small Singular Values of Bidiagonal Matrices With Guaranteed High Relative Accuracy. _SIAM J. Sci. Statist. Comput._, **11** (5), 873-912.
* Golub, G. H. and Van Loan, C. F. (1996). "Matrix Computations". 3rd ed., Johns Hopkins University Press, Baltimore. ISBN 0-8018-5414-8.
* Halldor, Bjornsson and Venegas, Silvia A. (1997). "A manual for EOF and SVD analyses of climate data"（頁面存檔備份，存於網際網路檔案館）. McGill University, CCGCR Report No. 97-1, Montréal, Québec, 52pp.
* Hansen, P. C. (1987). The truncated SVD as a method for regularization. _BIT_, **27**, 534-553.
* Horn, Roger A. and Johnson, Charles R (1985). "Matrix Analysis". Section 7.3. Cambridge University Press. ISBN 0-521-38632-2.
* Horn, Roger A. and Johnson, Charles R (1991). Topics in Matrix Analysis, Chapter 3. Cambridge University Press. ISBN 0-521-46713-6.
* Strang G (1998). "Introduction to Linear Algebra". Section 6.7. 3rd ed., Wellesley-Cambridge Press. ISBN 0-9614088-5-5.`