奇異值分解

維基百科,自由的百科全書
跳至導覽 跳至搜尋
線性代數

向量 · 向量空間  · 行列式  · 矩陣

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

理論描述[編輯]

假設M是一個m×n矩陣,其中的元素全部屬於K,也就是實數域或複數域。如此則存在一個分解使得

其中Um×m酉矩陣;Σ是m×n階非負實數對角矩陣;而V*,即V共軛轉置,是n×n階酉矩陣。這樣的分解就稱作M奇異值分解。Σ對角線上的元素Σi,i即為M奇異值

常見的做法是將奇異值由大而小排列。如此Σ便能由M唯一確定了。(雖然UV仍然不能確定。)

直觀的解釋[編輯]

在矩陣M的奇異值分解中

  • V的列(columns)組成一套對正交"輸入"或"分析"的基向量。這些向量是特徵向量
  • U的列(columns)組成一套對正交"輸出"的基向量。這些向量是特徵向量
  • Σ對角線上的元素是奇異值,可視為是在輸入與輸出間進行的純量的"膨脹控制"。這些是特徵值的非負平方根,並與UV的行向量相對應。

奇異值和奇異向量,以及他們與奇異值分解的關係[編輯]

一個非負實數σ是M的一個奇異值僅當存在Km的單位向量uKn的單位向量v如下:

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

對於任意的奇異值分解

矩陣Σ的對角線上的元素等於M的奇異值. UV的列分別是奇異值中的左、右奇異向量。因此,上述定理表明:

  • 一個m×n的矩陣至多有p = min(m,n)個不同的奇異值;
  • 總能在Km中找到由M的左奇異向量組成的一組正交基U,;
  • 總能在Kn找到由M的右奇異向量組成的一組正交基V,。

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

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

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

例子[編輯]

觀察一個4×5的矩陣

M矩陣的奇異值分解如下

注意矩陣的所有非對角元為0。矩陣都是酉矩陣,它們乘上各自的共軛轉置都得到單位矩陣。如下所示。在這個例子中,由於都是實矩陣,故它們都是正交矩陣

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

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

與特徵值分解的聯繫[編輯]

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

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

  • 的列向量(右奇異向量)是特徵向量
  • 的列向量(左奇異向量)是的特徵向量。
  • 的非零對角元(非零奇異值)是或者的非零特徵值的平方根。

特殊情況下,當M是一個正規矩陣(因而必須是方陣)根據譜定理M可以被一組特徵向量酉對角化,所以它可以表為:

其中U為一個酉矩陣,D為一個對角陣。如果M半正定的,的分解也是一個奇異值分解。

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

其中U是不需要是酉的,D也不需要是半正定的。而奇異值分解如下:

其中是對角半正定矩陣,UV是酉矩陣,兩者除了通過矩陣M沒有必然的聯繫。

幾何意義[編輯]

因為UV都是酉的,我們知道U的列向量u1,...,um組成了Km空間的一組標準正交基。同樣,V的列向量v1,...,vn也組成了Kn空間的一組標準正交基(根據向量空間的標準點積法則)。

矩陣代表從的一個線性映射。通過這些標準正交基,這個變換可以用很簡單的方式進行描述:,其中中的第i個對角元。當時,

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

應用[編輯]

求廣義逆陣(偽逆)[編輯]

奇異值分解可以被用來計算矩陣的廣義逆陣(偽逆)。若矩陣M的奇異值分解為,那麼M的偽逆為

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

列空間、零空間和秩[編輯]

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

矩陣近似值[編輯]

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

幾種程式語言中計算SVD的函式範例[編輯]

  • 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)

歷史[編輯]

參見[編輯]

外部連結[編輯]

參考文獻[編輯]

  • 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.