奇异值分解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有很好的近似。