第四章矩阵的因子分解

第4章矩阵的因子分解（MatrixFactorizationandDecomposition）教学要求掌握矩阵的满秩分解；掌握矩阵的三角分解；掌握矩阵的正交分解；掌握Schur定理和正规矩阵的定义；熟练掌握矩阵的奇异值分解；,数据集中可能包含大量特征，维灾难使得数据分析很困难，1.维归约（降维）：利用旧属性的线性组合得到新属性，使得新属性相互正交，捕获到数据的最大变差（PCA：主成分分析(principlecomponentsanalysis)和SVD）2.选择特征子集：嵌入（决策树分类其），过滤和包装（搜索，特征加权等）,矩阵的各种分解在矩阵计算中也扮演相当重要的角色。由于变换即矩阵，所以各种分解从根本上看是各种变换，其目的是将矩阵变换成特殊的矩阵。,4.2矩阵的满秩分解满秩分解定理：设为任意矩阵，则存在使得A=BC,其中B为列满秩矩阵,C为行满秩矩阵.,任一非（行或列）满秩的非零矩阵可表示为一列满秩矩阵和一行满秩矩阵的积；B的列可取为A的列的任一极大线性无关组；C可取为其行为A的行所生成的空间的基,然后用定理确定矩阵B。应用于极小最小二乘解和极小范数最小二乘解的算法中。,例1求下面矩阵的满秩分解,解思路：对矩阵A实施初等行变换得简化阶梯形矩阵H（阶梯型的非零行的第一个非零元为1，其所在的列其它元素为0）,取A的r个使H阵满秩的列为B，将H全为零的行去掉后即可构成行满秩矩阵C。,由此可知rank(A)=2，且该矩阵第一列、第三列是线性无关的。选取,同样，我们也可以选取,由上述例子可以看出矩阵的满秩分解形式并不唯一。但是不同的分解形式之间有如下联系：注：如果均为矩阵A的满秩分解，那么存在矩阵满足,则称其为A的LU分解或三角分解。,4.3矩阵的三角分解,定义1如果方阵A可以分解成一个单位下三角矩阵L与一个上三角矩阵U的乘积,初等下三角矩阵,初等下三角矩阵性质,(1)det(Li)=1,(2)用初等下三角矩阵左乘矩阵A，等于将A的第i行依次乘以-li+1i,-lni分别加到第i+1行到第n行上去。(3)设A=(aij)nn,且ajj0，并且取,则LiA在(i+1,j),(i+2,j)(n,j)的位置上为0,(4),定理1(LU分解定理)设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵L（主对角线上元素全为1的下三角矩阵）与唯一的上三角矩阵U，使得的充要条件是A的所有顺序主子式均非零，即,矩阵的LU分解也称为Doolitte分解若L为下三角矩阵,U为单位上三角矩阵,称为Crout分解。,定理2(LDU分解定理)设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵L，对角矩阵D=diag(d1,d2,dn)和单位上三角矩阵U，使得A=LDU的充要条件是A的所有顺序主子式均非零，即,矩阵的LU分解方法,矩阵的LU分解方法有很多种，这里主要介绍初等行变换消元法步骤：1.通过初等行变换将A化为上三角矩阵U：（A，I）（U，L1）2.取L=：因为L1是一系列初等下三角矩阵乘积（对应初等行变换），所以L是单位下三角矩阵。,例1求下列矩阵的LU分解：,解：,从而得这里,因为,所以,1.即使矩阵A非奇异，如果A不满足前n-1个顺序主子式非零，未必能做LU分解，2.适当改变非奇异矩阵的行的次序，可使改变后的矩阵做LU分解，引入排列阵的概念,说明,定义1设e1,e2,en是n阶单位矩阵I的n个列向量，矩阵P=(ei1,ei2,ein)称为一个n阶排列阵，其中i1,i2,in是1,2n的一个排列.P是排列阵的充要条件是P为一系列形如P(i,j)的初等交换矩阵的乘积.,排列阵的性质：1.P是排列阵，则PT和P-1也是排列阵，且PT=P-12.P1，P2是排列阵，则P1P2是排列阵3.,即：用排列阵左乘矩阵A相当于将A的行按照排列阵的次序重排，右乘对A的列按排列阵的次序重排。,引理1设A是n阶非奇异矩阵，则存在排列阵P，使得PA的所有顺序主子式要条件均非零。定理3设A是n阶非奇异矩阵，则存在排列阵P，使得PA=LDU所其中L是单位下三角矩阵，U是单位上三角矩阵，D是对角矩阵。,三角方程组易于求解,矩阵LU分解的一个应用解线性方程组,定理,设矩阵A对称正定，则存在唯一的对角元为正的下三角阵L，使得,称为对称正定矩阵A的乔累斯基分解,利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法MATLAB函数：Chol(A)；lu(A)是求矩阵的LU分解函数,乔累斯基（Cholesky）分解,4.4QR分解,QR分解在矩阵计算中占据相当重要的地位。利用QR分解，可以解决各种应用中（例如图像压缩处理、结构分析等）出现的最小二乘问题、特征值问题等矩阵计算中的核心问题。,以初等变换为工具的三角分解无法消除病态矩阵的不稳定性，因此引入以正交变换为工具的QR分解方法,定理1(QR分解定理)设A是n阶非奇异实（复）矩阵，则存在正交（酉）矩阵Q与非奇异实（复）上三角矩阵R，使得A=QR且除去相差一个对角元绝对值全等于1的对角矩阵因子，分解式是唯一的。,矩阵的QR分解也称为正交三角分解；若规定上三角矩阵R的对角元符号，则A的QR分解唯一。,证明：先证明分解的存在性。将矩阵A按列分块得到由于，所以是线性无关的。利用Schmidt正交化与单位化方法，先得到一组正交向量组,再单位化，这样得到一组标准正交向量组,并且向量组之间有如下关系,于是有,为正交矩阵。,证毕,唯一性：设A=QR=Q1R1,则Q=Q1R1R-1=Q1D，其中D=R1R-1为非奇异上三角矩阵，于是I=QHQ=(Q1D)H(Q1D)=DHD所以D为酉矩阵，比较DHD=DDH=I的对角元，可得D为对角矩阵，且对角元的模为1，于是R1=DR,Q1=QD-1,证毕,定理2设A是列满秩的mn实（复）矩阵，则存在m阶正交（酉）矩阵Q和n阶非奇异实（复）上三角矩阵R，使得定理3设A是mn矩阵，且rank(A)=r0,则存在m阶正交（酉）矩阵Q和rn阶行满秩矩阵R，使得,非奇异矩阵的QR分解的推广：,推论设A是mn矩阵，且rank(A)=r0,则存在mr列正交规范矩阵Q1和rn行满秩矩阵R，使得A=Q1R，列正交规范矩阵指的是mr矩阵Q1满足。矩阵Q1是列正交规范矩阵的充要条件是Q1的列向量组是标准正交向量组,一、Schmidt方法步骤：1.将矩阵A的列向量1，2，n施以Schmidt标准正交化,得到1，2，n标准正交组：2.取Q=(1，2，n)，则Q为正交矩阵3.取R=QTA,矩阵的QR分解方法,例1利用Schmidt方法将下列矩阵进行QR分解：,解先将A=1，2，3的三个列向量正交化与单位化：,所以A的QR分解为：A=QR,从而,1.取A的列向量1，2，n，对1，由Householder矩阵性质知存在Householder矩阵H1，使得（为方便说明，不妨取负号）,二、Householder变换法,步骤：,从而,2.对，当时，存在Householder矩阵H2，使得,则得,取,如果，则，直接进行下一步。,使得,3.对An-2继续类似的变换，如此最多n-1步，也即至多可以找到n-1个矩阵,令Q=Hn-1H2H1，则Q为正交矩阵，从而得到QR分解,例2利用Householder变换将下列矩阵进行QR分解,对向量，令,解：,从而得Householder矩阵,使得,注意，即被反射到,对向量，令,可得Householder矩阵,因此取,从而有,所求的QR分解为,定义1设A，BRnn(Cnn),若存在n阶正交（酉）矩阵U使得UTAU=U-1AU=B（UHAU=U-1AU=B），称A正交（酉）相似B。,4.5Schur定理和正规矩阵(SchurtheoryandNormalMatrices),定理1（Schur定理）任何一个n阶复矩阵A都酉相似于一个上三角矩阵，即存在一个n阶酉矩阵U和一个n阶上三角矩阵R使得UHAU=R其中R的对角元是A的特征值，可以按要求的顺序排列,定义2设ACnn，若AHA=AAH，称A为正规矩阵。常见的正规矩阵：对角矩阵;对称和反对称矩阵：AT=A，AT=A。Hermite矩阵和反Hermite矩阵：AH=A，AH=A正交矩阵和酉矩阵：ATA=AAT=I，AHA=AAH=I。,正规矩阵,正规矩阵的性质：,1.正规矩阵有n个线性无关的特征向量；,2.正规矩阵属于不同特征值的特征向量是正交的；,3.与正规矩阵酉相似的矩阵都是正规矩阵。,由定理2若A是n阶正规矩阵，则A酉相似于一个对角阵，即存在一个n阶酉矩阵U使得UHAU=，其中=diag(1,n),i(i=1,2,n)是A的特征值。该式称为正规矩阵的谱分解式.,正规是酉相似的不变性质,定理2n阶矩阵A酉相似于一个对角阵的充要条件是A是正规矩阵。,即i是矩阵A的特征值i所对应的单位特征向量。,设U=(1,2,n),则由定理2知UHAU=diag(1,n),可得,即Ai=ii（1,2,n）,求谱分解式的步骤,例1：求正规矩阵,的谱分解表达式。,解：首先求出矩阵A的特征值与特征向量。容易计算,从而A的特征值为1=2=3=1,4=-3当=1时，求得三个线性无关的特征向量为1=1,1,0,0T2=1,0,1,0T3=-1,0,0,1T,当=-3时，求得一个线性无关的特征向量为4=1,-1,-1,1T将1,2,3正交化与单位化可得,将4单位化可得：于是有,这样可得其谱分解表达式为A=UUH,推论1设A是n阶Hermite矩阵，则A必酉相似于对角矩阵，即存在一个n阶酉矩阵U使得UHAU=，其中=diag(1,n),i(i=1,2,n)是A的实特征值。该分解式称为Hermite矩阵A的谱分解式。,是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后续计算的复杂度，在“预处理”阶段通常要先对原始数据进行降维。原则：降维后的数据不能失真，也就是说，被PCA降掉的那些维度只能是那些噪声或是冗余的目的就是“降噪”和“去冗余”。“降噪”的目的就是使保留下来的维度间的相关性尽可能小，“去冗余”的目的就是使保留下来的维度含有的“能量”尽可能大。,著名的PCA（PrincipalComponentAnalysis）,形成样本矩阵SNd，假设我们有一个样本集X，里面有N个样本，每个样本的维度为d。即：即每行为一个样本，每一列为一个维度，得到样本矩阵S,著名的PCA（PrincipalComponentAnalysis）,2.计算样本矩阵的协方差矩阵；协方差矩阵度量的是维度与维度之间的关系，主对角线上的元素是各个维度上的方差(即能量)，其他元素是两两维度间的协方差(即相关性)。,著名的PCA（PrincipalComponentAnalysis）,3.（1）去噪对协方差矩阵S进行谱分解，去不同维度的相关性（非对角元素化为0）找到一个正交矩阵P，满足（2）降维选取中最大的p个特征值对应的特征向量组成投影矩阵P1：取最大的前p(p0,称i为A的正奇异值。,另一种定义：,定理1：正规矩阵A的奇异值等于A的特征值的模长。证：根据正规矩阵的性质，知存在酉矩阵U使得A=Udiag(1,2,n)UH,其中1,2,n是A的特征值，所以AHA=Udiag(|1|2,|2|2,|n|2)UH所以A的奇异值为|1|,|2|,|n|#,定理2（奇异值分解定理）设ACmn，秩（A）=r，则存在m阶酉矩阵V和n阶酉矩阵U使得其中=diag(1,r),且1r0.,1.U的列向量是AHA的标准正交特征向量；（也称为悬挂矩阵）2.U的前r列向量是AHA对应于r个非零特征值12，r2的标准正交特征向量；3.V的列向量是AAH的标准正交特征向量；（也称为对准矩阵）4.V的前r列向量是AHA对应于特征值12，r2的标准正交特征向量；,注记：,第二步：令U1=(u1ur),计算,求矩阵SVD的算法,第一步：计算，并计算特征值1n和对应的标准正交特征向量u1un，取U=(u1un),注：根据这样的取法得AAHV1=A(AHAU1)-1=A(U12)-1=AU1=V12即：V1对应于特征值12，r2的标准正交特征向量,第三步：求解线性方程组的标准正交基础解系vr+1vm，令V=(v1,vr,vr+1,.vm)则U和V即为所求。,例1求下列矩阵的SVD分解：,解：第一步,矩阵AHA的特征值为3,1,0，对应的特征向量为,标准正交化得,第二步令：计算：,其中,第三步解，得其基础解系为,从而,因此所求SVD为,例2：求下列矩阵的奇异值分解表达式,解:（1）计算AHA的特征值分别为5,0。对应的两个标准正交特征向量,由这两个标准正交特征向量组成矩阵U,（2）计算AAH的特征值为5，0，0，所以A的奇异值为。下面计算AAH的标准正交特征向量，解得分别与5，0，0对应的三个标准正交特征向量,由这三个标准正交特征向量组成矩阵V，所以有,于是可得奇异值分解式为,注：使用第二种方法时选取的U和V不唯一，他们的对应列之间相差一个符号，因此当分解式不成立时，需要调整相应的特征向量符号。,SVD的几何意义:,圆S经过变换A，变成椭圆AS。圆的正交方向u1,u2变成椭圆的长、短轴方向,。,设矩阵A的奇异值分解为A=VUT，考虑A对应的线性变换A,u1,u2,1v1,2v2,AS,1v1,2v2,从变换的角度理解SVD，酉变换U保持球面不变，对角矩阵将球面拉伸到一个有标准基的椭圆(1，2是A的两个奇异值，对应椭圆的长半轴和短半轴)，最后酉变换V旋转或镜射这个椭圆，但不改变它的形状。,矩阵奇异值分解的特点：,1.数据压缩：矩阵Amn的奇异值分解为：A=VUT，其展开式：A有nm个数据，分解后为(m+n+1)r个数据，若A的秩r远远小于m和n,则通过奇异值分解可以大大降低A的维数,可以达到降维的目的,同时可以降低计算机对存贮器的要求，常用于图像压缩。奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前k个大的奇异值来近似描述矩阵。,图像的数字化技术与矩阵的奇异值分解,计算机处理图像技术的第一步是图像的数字化存储技术，即将图像转换成矩阵来存储。转换的原理是将图形分解成象素（pixels）的一个矩形的数阵，其中的信息就可以用一个矩阵A=(aij)mn来存储。矩阵A的元素aij是一个正的数，它相应于象素的灰度水平（graylevel）的度量值。由于一般来讲，相邻的象素会产生相近的灰度水平值，因此有可能在满足图像清晰度要求的条件下，将存储一个mn阶矩阵需要存储的mn个数减少到n+m+1的一个倍数。,压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的逼近。如果图象的数字矩阵A的奇异值分解为：A=UVT，其展开式：,压缩矩阵A的方法是取一个秩为k(kr)的矩阵Ak来逼近矩阵A。Ak按如下方法选取：,这是矩阵A的秩1分解式。,在秩为k(kn)的所有矩阵中，矩阵Ak所对应的图象和矩阵A所对应的图象最相近。一般的，k越大图象就越清晰。压缩比：=(m+n+1)/mn;经典的方法是选取接近k，使Ak的存储量比A的存储量减少20%。,矩阵奇异值分解的特点：,2.奇异值对矩阵的扰动不敏感,而特征值对矩阵的扰动敏感。3.奇异值的比例不变性。即kA的奇异值是A的奇异值的|k|倍。4.奇异值的旋转不变性。即若P是正交阵,PA的奇异值与A的奇异值相同。,奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放大、缩小等几何变化方面有很好的应用。,5.容易得到矩阵A的秩为k(kr)（低秩）的一个最佳逼近矩阵。奇异值的这个特征可以应用于信号的分解和重构,提取有用信息,消除信号噪声等6.若A、B都有相同的奇异向量,则|AB|2=,即,我们可以通过控制奇异值的大小来控制两个矩阵空间的距离。,存储矩阵Ak只需要存储k个奇异值，k个m维向量ui和n维向量vj的所有分量，共计k（m+n+1）个元素。如果m=n=1000，存储原矩阵A需要存储10001000个元素。取k=100时，图象已经非常清晰了，这时的存储量是100（2000+1）=200100个数。和矩阵A比较，存储量减少了80%。,SVD用于文本分类,用一个大矩阵A来描述一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文章，每一列对应一个词。M=1,000,000，N=500,000。第i行第j列的元素，是字典中第j个词在第i篇文章中出现的加权词频（这个矩阵一般称为关联矩阵）。这个矩阵非常大，有一