奇异值分解SVD

发表于 | 更新于: | 分类于 | | 阅读量: 次

奇异值分解(SVD)是一种矩阵因子分解方法，是线性代数的概念。

任意一个mxn矩阵，都可以表示为三个矩阵的乘积(因子分解)形式，分别是m阶正交矩阵、由降序排列的非负的对角线元素组成的mxn矩形对角矩阵和n阶正交矩阵，称为该矩阵的奇异值分解。

矩阵的奇异值分解一定存在，但不唯一。奇异值分解可以看作是矩阵数据压缩的一种方法，即用因子分解的方式近似的表示原始矩阵，这种近似是在平方损失意义下的最优近似。

奇异值分解的定义与性质

定义与定理

定义15.1(奇异值分解)矩阵的奇异值分解是指，将一个非零的mxn实矩阵A,，表示为以下三个实矩阵乘积形式的运算，即进行矩阵的因子分解:

其中U是m阶正交矩阵，V是n阶正交矩阵，是由降序排列的非负的对角线元素组成的mxn矩形对角矩阵，满足：

其中，称为矩阵A的奇异值分解(SVD)，称为矩阵A的奇异值，U的列向量称为左奇异向量，V的列向量称为右奇异向量。

注意：奇异值分解不要求矩阵A是方阵，事实上矩阵的奇异值分解可以看作是方阵的对角化的推广。

任意给定一个实矩阵，其奇异值分解是否一定存在呢？答案是肯定的，下面的奇异值分解的基本定理给予保证。

定理15.1(奇异值分解基本定理) 若A为一mxn实矩阵，，则A的奇异值分解存在：

其中U是m阶正交矩阵，V是n阶正交矩阵，是mxn矩阵对角矩阵，其对角线元素非负，且按降序排列。

证明：(构造性证明)，对给定的矩阵A，构造出其奇异值分解的各个矩阵。为了方便，不妨假设，如果证明仍然成立。证明分三步完整：

  1. 确定V和

    首先，构造n阶正交实矩阵V和mxn矩形对角实矩阵。矩阵A是mxn实矩阵，则矩阵是n阶实对称矩阵。因而的特征值都是实数，并且存在一个n阶正交实矩阵V实现的对角化，使得成立，其中是n阶对角矩阵，其对角线元素由的特征值组成。而且，的特征值都是非负的。

    事实上，令 是的一个特征值，x是对应的特征向量，则：

    于是，

    可以假设正交矩阵V的列的排列使得对应的特征值形成降序排列：

    计算特征值的平方根(实际就是矩阵A的奇异值)

    设矩阵A的秩是r，rank(A)=r，则矩阵的秩也是r。由于是对称矩阵，它的秩等于正的特征值的个数，所以：

    对应地有:

    令：

    其中，为的正特征值对应的特征向量，为0特征值对应的特征向量，则：

    令

    则是一个r阶对角矩阵，其对角线元素为按降序排列的正的，于是mxn矩阵对角矩阵可以表示为：

    这就是矩阵A的奇异值分解中的mxn矩形对角矩阵。

    在式(15.6)中，的列向量是对应于特征值为0的特征向量。因此

    于是，的列向量构成了的零空间，而。所以的列向量构成A的零空间的一组标准正交基。因此，

    由于V是正交矩阵，由式(15.6)可得：

  2. 确定U

    构造m阶正交矩阵U。

    令

    则有

    对于的列向量构成了一组标准正交基，因为：

    由式(15-12)和式(15-15)可知，构成A的列空间的一组标准正交基，列空间的维数为r。

    如果将A看作是从到的线性变换，则A的列空间和A的值域是相同的。因此也是R(A)的一组标准正交基。

    若表示R(A)的正交补，则有R(A)的维数为r，的维数为m-r，两者的维数之和等于m。而且有成立。

    令为的一组标准正交基，并令

    则构成了的一组标准正交基。因此，U是m阶正交矩阵，这就是矩阵A的奇异值分解中的m阶正交矩阵。

  3. 证明

    由式(15-6)、式(15-7)、式(15-11)、式(15-14)和式(15-16)得

至此，证明了矩阵A存在奇异值分解。

紧奇异值分解与截断奇异值分解

定理15.1给出的奇异值分解 又称为矩阵的完全奇异值分解。实际常用的是奇异值分解的紧凑形式和截断形式。

紧奇异值分解是与原始矩阵等秩的奇异值分解。

截断奇异值分解是比原始矩阵低秩的奇异值分解。

紧奇异值分解

定义15.2 设有mxn实矩阵A，其秩为rank(A)=r，，则称为A的紧奇异值分解，即

其中是mxr矩阵，，是r阶对角矩阵；矩阵由完全奇异值分解中U的前r列、矩阵由V的前r列、矩阵由的前r个对角线元素得到。紧奇异值分解的对角矩阵的秩与原始矩阵A的秩相等。

截断奇异值分解

在矩阵的奇异值分解中，只取最大的k个奇异值(k<r,r为矩阵的秩)对应的部分，就得到矩阵的阶段奇异值分解。实际应用中提到矩阵的奇异值分解时，通常指截断奇异值分解。

定义15.3 设 A为mxn实矩阵，其秩rank(A) = r, 且0<k<r，则称为矩阵A的截断奇异值分解：

其中 是mxk矩阵，是nxk矩阵，是k阶对角矩阵；矩阵由完全奇异值分解中U的前k列，矩阵由V的前k列、矩阵 由的前k个对角线元素得到。对角矩阵的秩比原始矩阵A的秩低。

几何解释

从线性变换的角度理解奇异值分解，mxn矩阵A表示从n维空间到m维空间的一个线性变换，

其中，，x和Ax分别是各自空间的向量。

线性变换可以分解为三个简单的变换：

  • 一个坐标系的旋转或反射变换
  • 一个坐标轴的缩放变换
  • 另一个坐标系的旋转和反射变换

对矩阵A进行奇异值分解，得到，V和U都是正交矩阵，所以：

V的列向量构成空间的一组标准正交基，表示中的正交坐标系的旋转或反射变换；

U的列向量构成空间的一组标准正交基，表示中的正交坐标系的旋转或反射变换；

其中，的对角元素是一组非负实数，表示中的原始正交坐标系坐标轴的倍的缩放变换。

任意一个向量，经过基于的线性变换，等价于经过坐标系的旋转或反射变换，坐标轴的缩放变换，以及坐标系的旋转或反射变换U，，得到向量，如下图所示：

15-1

上图中，原始空间的标准正交基(红色和黄色)，经过坐标系的旋转变换、坐标轴的缩放变换 (黑色)、坐标系的旋转变换U，得到和经过线性变换A等价的结果。

主要性质

  1. 设矩阵A的奇异值分解为，则以下关系成立：

    也就是说，矩阵和的特征分解存在，且可以由矩阵A的奇异值分解的矩阵表示。V的列向量是的特征向量，U的列向量是的特征向量，的奇异值是和的特征值的平方根。

  2. 在矩阵A的奇异值分解中，奇异值、左奇异向量和右奇异向量之间存在对应关系。

    由易知：

    比较这一等式的两端的第j列，得到：

    这是矩阵A的右奇异向量和奇异值、左奇异向量的关系。

    类似地，由

    得到

    这是矩阵A的左奇异向量和奇异值、左奇异向量的关系。

  3. 矩阵A的奇异分解中，奇异值是唯一的，而矩阵U和V 不是唯一的。

  4. 矩阵A和的秩相等，等于正奇异值的个数r(包括重复的奇异值)。

  5. 矩阵A的r个右奇异向量构成的值域的一组标准正交基。

    因为矩阵是从映射到的线性变换，则的值域和的列空间是相同的， 是的一组标准正交基，因而也是的一组标准正交基。

  6. 矩阵A的n-r个右奇异向量构成A的零空间N(A)的一组标准正交基。

  7. 矩阵A的r个左奇异向量构成值域R(A)的一组标准正交基。

  8. 矩阵A的m-r个左奇异向量构成的零空间的i一组标准正交基。

奇异值分解的计算

矩阵A的奇异值分解可以通过求对称矩阵的特征值和特征向量得到。的特征向量构成正交矩阵V的列；的特征值的平方根为奇异值，即

对其由大到小排列作为对角线元素，构成对角矩阵；求正奇异值对应的左奇异向量，再求扩充的的标准正交基，构成正交矩阵U的列。从而得到A的奇异值分解。

给定mxn矩阵A，可以按照上面的叙述写出矩阵奇异值分解的计算过程：

  1. 首先，求的特征值和特征向量

    计算对称矩阵

    求解特征方程

    得到特征值，并将特征值由大到小排列：

    将特征值代入特征方程求得对应的特征向量。

  2. 求n阶正交矩阵V

    将特征向量单位化，得到单位特征向量，构成n阶正交矩阵V:

  3. 求mxn对角矩阵

    计算A的奇异值

    构造mxn矩形对角矩阵，主对角线元素是奇异值，其余元素是零，

  4. 求m阶正交矩阵U

    对A的前r个正奇异值，令

    得到

    求的零空间的一组标准正交基，令

    并令

  5. 得到奇异值分解

奇异值分解与矩阵近似

弗罗贝尼乌斯范数

奇异值分解也是一种矩阵近似的方法，这个近似是在弗罗贝尼乌斯范数(Frobenius norm)意义下的近似。矩阵的佛罗贝尼乌斯范数是向量的范数的直接推广，对应着机器学习中的平方损失函数。

定义 15.4(弗罗贝尼乌斯范数) 设矩阵，，定义矩阵A的弗罗贝尼乌斯范数为：

引理15-1 设矩阵， A的奇异值分解为，其中，则

证明：一般的，若Q是m阶正交矩阵，则有

因为

同样，若P是n阶正交矩阵，则有：

故

即

矩阵的最优近似

奇异值分解是在平方损失(佛罗贝尼乌斯范数)意义下对矩阵的最优近似，即数据压缩？

定理15.2 设矩阵，矩阵的秩rank(A) = r，并设为中所有秩不超过k的矩阵集合，0<k<r，则存在一个秩为k的矩阵 ，使得

称矩阵X为矩阵A在范数意义下的最优近似。

定理15.3 设矩阵，矩阵的秩rank(A)=r, 有奇异值分解，并设 为中所有秩不超过k的矩阵的集合，0<k<r，若秩为k的矩阵满足：

则

特别地，若，其中

则，

证明：令为满足式(15-32)的一个矩阵。由于

下面证明：

于是式(15-33)成立。

设X的奇异值分解为,其中

令矩阵，则。因此得到

用分块方法对B分块，

其中是kxk子矩阵，是kx(n-k)子矩阵，是(m-k)xk子矩阵，是(m-k)x(n-k)子矩阵。可得：

现证。

反证法：若，令

则，且：

这与X的定义式(15-35)矛盾，证明了。同样可证，于是

再证。

令

则，且

由式(15-35)知，，即。

最后看。

若(m-k)x(n-k)子矩阵有奇异值分解，则

证明的对角线元素为A的奇异值。

为此，令

其中是k阶单位矩阵，的分块与B的分块一致。注意到B及的奇异值分解，即得

由此可知的对角线元素为A的奇异值。故有

于是证明了：

定理15.3表明，在秩不超过k的mxn矩阵的集合中，存在矩阵A的范数意义下的最优近似矩阵X。是达到最优值的一个矩阵。

事实上，紧奇异值分解式在范数意义下的无损压缩；

截断奇异值分解是有损压缩。截断奇异值分解得到的矩阵的秩为k，通常远小于原始矩阵的秩r，所以是由低秩矩阵实现了对原始矩阵的压缩。

矩阵的外积展开式

利用外积展开式对矩阵A进行近似。矩阵A的奇异值分解也可以由外积形式表示。

事实上，若将A的奇异值分解看成矩阵和的乘积，将按列向量分块，将按行向量分块，即得：

则

式(15-45)称为矩阵A的外积展开式，其中为mxn矩阵，是列向量和行向量的外积，其第i行第j列元素为的第i个元素与的第j个元素的乘积，即

A的外积展开式也可以写成下面的形式：

其中是mxn矩阵。式(15-46)将矩阵A分解为矩阵的有序加权和。

由矩阵A的外积展开式知，若A的秩为n，则

设矩阵

则的秩为n-1，并且是秩为n-1矩阵在范数意义下A的最优近似矩阵。

以此类推，一般的，设矩阵：

则的秩为k，并且是秩为k的矩阵在范数意义下A的最优近似矩阵。矩阵就是A的截断奇异值分解。

由于通常奇异值递减很快，所以k取值很小时，也可以对A有很好的近似。