奇异值分解

类似于特征分解将矩阵分解成特征向量和特征值,奇异值分解(singular value decomposition, SVD)将矩阵分解为奇异向量(singular vector)和奇异值(singular value)。通过分解矩阵,我们可以发现矩阵表示成数组元素时不明显的函数性质。而相比较特征分解,奇异值分解有着更为广泛的应用,这是因为每个实数矩阵都有一个奇异值分解,但未必都有特征分解。例如,非方阵型矩阵没有特征分解,这时只能使用奇异值分解。

简介

类似于特征分解将矩阵分解成特征向量和特征值,奇异值分解(singular value decomposition, SVD)将矩阵分解为奇异向量(singular vector)和奇异值(singular value)。通过分解矩阵,我们可以发现矩阵表示成数组元素时不明显的函数性质。而相比较特征分解,奇异值分解有着更为广泛的应用,这是因为每个实数矩阵都有一个奇异值分解,但未必都有特征分解。例如,非方阵型矩阵没有特征分解,这时只能使用奇异值分解。

定义:

对于一个实数 $m \times n$ 矩阵 A,奇异值分解可将其分解成三个矩阵的乘积:

$A = U \Sigma V^T = \sum^{\min{m,n}}_{i=1} \delta_i u_i v_i^T$

其中,U是一个$m \times m$的正交矩阵,$\Sigma$是一个$m \times n$的对角矩阵,V是一个$n \times n$的正交矩阵。注意,矩阵$\Sigma$不一定是方阵。

矩阵$\Sigma$中的非零元素(即对角线上的元素)被称为矩阵A的奇异值,矩阵U和矩阵V的列向量分别被称为左奇异向量以及右奇异向量。

事实上,A的相关特征分解可以帮助我们解释A的奇异值分解,A的左奇异向量是$AA^T$的特征向量,A的右奇异向量是$A^TA$的特征向量。A 的非零奇异值是 $A^TA$ 特征值的平方根,同时也是 $AA^T$特征值的平方根。

举例:低秩矩阵(该理论在计算机视觉中应用广泛)

对于某个矩阵A,我们试图找到他的一个低秩矩阵B,使得B的矩阵特性近似于A,即:

$$B = \sum^{k}_{i=1}x_i y_i^T$$

我们可以通过弗洛贝尼乌斯范数(Frobenius norm)来衡量矩阵AB之间的相似程度:

$$||A-B||_F = \sqrt{\sum^{m}_{i=1}\sum^{n}_{j=1}(a_{ij}-b_{ij})^2}$$

因为弗洛贝尼乌斯范数(Frobenius norm)满足正交恒定,因此上述公式具有以下性质:

$$||A||_F = ||U^TAV||_F = ||\Sigma||_F = \sqrt{\sum^{\min{m,n}}_{i=1} \delta_i^2}$$

低秩矩阵估算定理(Low-rank matrix approximation theorem by Schmidt, 1908):

对于秩为k的矩阵B,且使得$||A_B||_F$最小化,则该矩阵B为:

$$B_k = U_k \Sigma_k V_k^T = \sum^{k}_{i=1} \delta_i u_i v_i^T$$

其中,

$U_k$为$m \times k$矩阵,由矩阵U的前k个列向量组成;

$\Sigma_k$为一个对角矩阵,由前k个奇异值组成;

$V_k$为$n \times k$矩阵,由矩阵V的前k个列向量组成。

$B_k$实质上是一个被缩减的奇异值分解(truncated SVD)。

(描述来源:Deep Learning - An MIT Press book by Ian Goodfellow and Yoshua Bengio and Aaron Courville http://www.deeplearningbook.org; Trevor Hastie, Robert Tibshirani and Jerome Friedman (2nd ed., 2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction; Christopher M. Bishop (2006). Pattern Recognition and Machine Learning.)

发展历史

描述(300字)

奇异值分解主要由19世纪末至20世纪初五位数学家先后建立、证明并完善:Eugenio Beltrami (1835-1899), Camille Jordan (1838-1921), James Joseph Sylvester (1814-1897), Erhard Schmidt (1876-1959), Hermann Weyl (1885-1955),目前作为线性代数基础及多维数据降维手段在机器学习及大数据领域应用广泛。

(描述来源:On the Early History of Singular Value Decomposition by S.W. Stewart

主要事件

年份

事件

相关论文

1873

意大利数学家Beltrami首次提出SVD

论文发表于意大利数学杂志《Journal of Mathematics for the use of students of the Italian Universities》

1873

数学家Camille Jordan被证实为SVD的共同发现者

n.a

1889

数学家Sylvester为SVD做了补充说明

相关论文发表于《The Messenger of Mathematics》

1907

Schmidt将SVD引入无限维空间

n.a.

1912

Weyl完善了低秩矩阵估算定理,为其引入误差体制

n.a.

(描述来源:On the Early History of Singular Value Decomposition by S.W. Stewart https://www.math.ucdavis.edu/~saito/courses/229A/stewart-svd.pdf)

发展分析

未来发展方向

SVD可以将高维空间内的矩阵在保证具有相似信息条件的情况下进行降维处理,为解决高维数据复杂度提供了有效手段。SVD在大数据分析领域有着很多应用:例如解决伪逆矩阵,最小二乘法问题,多变量控制,矩阵估算等。

Contributor: Han Zhang

相关人物
Erhard Schmidt (1876-1959)
Erhard Schmidt (1876-1959)
Eugenio Beltrami(1835-1899)
Eugenio Beltrami(1835-1899)
卡米尔乔丹
卡米尔乔丹
James Joseph Sylvester (1814-1897)
James Joseph Sylvester (1814-1897)
Hermann Weyl (1885-1955)
Hermann Weyl (1885-1955)
简介
相关人物