奇異值分解

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

理論描述

假設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ⁿ的單位向量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ⁿ找到由M的右奇異向量組成的一組正交基V，。

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

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

根據定義，退化的奇異值具有不唯一的奇異向量。因為，如果u₁和u₂為奇異值σ的兩個左奇異向量，則它們的任意歸一化線性組合也是奇異值σ一個左奇異向量，右奇異向量也具有類似的性質。因此，如果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₁,...,u_m 組成了K^m空間的一組標準正交基。同樣，V的列向量v₁,...,v_n也組成了Kⁿ空間的一組標準正交基（根據向量空間的標準點積法則）。

矩陣$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}}$在這兩組選定的基上的矩陣表示為所有對角元均為非負數的對角矩陣。

SVD方法種類

GRSVD

GRSVD為其中一種SVD分解方法。他利用豪斯霍爾德轉換將目標矩陣轉換成雙斜對角矩陣，再利用QR algorithm追蹤其特徵值。 此演算法的限制為，難以估計出真正的準確值。根據下圖所示可觀察出，誤差會隨着迭代次數增加而減小，最終達到飽和。

Jacobi SVD

一種SVD方法為Jacobi SVD，此種方法的複雜度較GRSVD高，但是精確度也較高。Jacobi SVD使用多次的平面旋轉使得矩陣上非對角軸上的數值趨近於0。 於此，運用演算法可將矩陣轉換成我們所需的型式:

將A0轉換成A，成為只有對角線有值的矩陣。 下圖為誤差模擬圖，可觀察出迭代次數增加，可以相對增加其精準度。

應用

求廣義逆陣（偽逆）

奇異值分解可以被用來計算矩陣的廣義逆陣（偽逆）。若矩陣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.