矩阵的因子分解

第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)n

n,且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,2…n的一个排列.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.4

QR分解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)=r>0,那么存在m阶正交〔酉〕矩阵Q和rn阶行满秩矩阵R，使得非奇异矩阵的QR分解的推广：整理课件推论设A是mn矩阵，且rank(A)=r>0,那么存在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-1…H2H1，那么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的特征值。该式称为正规矩阵的谱分解式.正规是酉相似的不变性质定理2

n阶矩阵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,0]T

α2=[1,0,1,0]T

α3=[-1,0,0,1]T整理课件当λ=-3时，求得一个线性无关的特征向量为

α4=[1,-1,-1,1]T将α1,α2,α3正交化与单位化可得整理课件将α4单位化可得：于是有这样可得其谱分解表达式为A=U

UH整理课件推论1设A是n阶Hermite矩阵，那么A必酉相似于对角矩阵，即存在一个n阶酉矩阵U使得UHAU=，其中=diag(1,…,n),i(i=1,2,…n)是A的实特征值。该分解式称为Hermite矩阵A的谱分解式。整理课件是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后续计算的复杂度，在“预处理〞阶段通常要先对原始数据进行降维。原那么：降维后的数据不能失真，也就是说，被PCA降掉的那些维度只能是那些噪声或是冗余的目的就是“降噪〞和“去冗余〞。“降噪〞的目的就是使保存下来的维度间的相关性尽可能小，“去冗余〞的目的就是使保存下来的维度含有的“能量〞尽可能大。著名的PCA〔PrincipalComponentAnalysis〕整理课件形成样本矩阵S

N

d，假设我们有一个样本集X，里面有N个样本，每个样本的维度为d。即：即每行为一个样本，每一列为一个维度，得到样本矩阵S著名的PCA〔PrincipalComponentAnalysis〕整理课件2.计算样本矩阵的协方差矩阵；协方差矩阵度量的是维度与维度之间的关系，主对角线上的元素是各个维度上的方差(即能量)，其他元素是两两维度间的协方差(即相关性)。著名的PCA〔PrincipalComponentAnalysis〕整理课件3.〔1〕去噪对协方差矩阵S进行谱分解，去不同维度的相关性〔非对角元素化为0〕找到一个正交矩阵P，满足〔2〕降维选取中最大的p个特征值对应的特征向量组成投影矩阵P1：取最大的前p(p<d)个特征值对应的维度，对应的p个特征向量组成了新的特征向量矩阵P1，该P1就是投影矩阵。著名的PCA〔PrincipalComponentAnalysis〕整理课件4.对原始样本矩阵S进行投影，得到降维后的新样本矩阵S1：即S1=SP1；理由：假设PCA降维后的样本矩阵为S1，显然，根据PCA的目的，S1中的各个维度间的协方差根本为零，也就是说S1的协方差矩阵应该为对角矩阵。即满足：著名的PCA〔PrincipalComponentAnalysis〕由〔3〕整理课件著名的PCA〔PrincipalComponentAnalysis〕由于样本矩阵的每一行是一个样本，特征向量矩阵的每一列是一个特征向量。右乘相当于以每个样本的特征向量为基进行线性变换，得到的新样本矩阵中每个样本的维数变为了p，完成了降维操作。实际上，P1中的特征向量就是低维空间新的坐标系，称之为“主成分〞。这就是“主成分分析〞的名称由来。整理课件从Beltrami〔1873〕和Jordan〔1874〕提出奇异值分解〔SVD：SingularValueDecomposition〕至今，SVD已经成为矩阵计算中最有用和最有效的工具之一，由于奇异值良好的数学特征,奇异值分解不仅仅应用在主成分分析、图像压缩、数字水印和文章分类中,而且在信号分解、信号重构、信号降躁、数据融合、目标识别、目标跟踪、故障检测和神经网络等方面有很好的应用。§4.6奇异值分解(SVD)〔SingularValueDecomposition〕整理课件引理1设ACm×n，那么AHACn×n，AAHCm×m，且〔1〕Rank(AHA)=Rank(AAH)=Rank(A)〔2〕AHA与AAH的特征值均为非负实数；〔3〕AHA与AAH的非零特征值相同，并且非零特征值的个数〔重特征值按重数计算〕等于rank〔A〕；〔4〕AHA=0A=0整理课件定义1设ACm×n，假设存在非负实数和非零向量uCn，vCm，使得Au=v,AHv=u〔*〕称为矩阵A的奇异值。相应地，u和v分别称为A对应于奇异值的右奇异向量和左奇异向量。说明：由〔*〕式得(AHA)u=AHv=2u，(AAH)v=Au=2v所以2是AHA的特征值也是AAH的特征值,而u和v分别是对应于2的特征向量。所以有整理课件设ACm×n，rank(A)=r，设AHA的特征值12r0，r+1=r+2==n=0，称为矩阵A的奇异值。假设i>0,称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〔奇异值分解定理〕设ACm×n，秩〔A〕=r，那么存在m阶酉矩阵V和n阶酉矩阵U使得其中=diag(1,…,r),且1r>0.整理课件1.U的列向量是AHA的标准正交特征向量；〔也称为悬挂矩阵〕2.U的前r列向量是AHA对应于r个非零特征值12，r2的标准正交特征向量；3.V的列向量是AAH的标准正交特征向量；〔也称为对准矩阵〕4.V的前r列向量是AHA对应于特征值12，r2的标准正交特征向量；注记：整理课件第二步：令U1=(u1…ur),计算求矩阵SVD的算法第一步：计算，并计算特征值

1…

n和对应的标准正交特征向量u1…un，取U=(u1…un)注：根据这样的取法得AAHV1=A(AHAU1)

-1=A(U1

2)-1=AU1=V1

2即：V1对应于特征值

12，

r2的标准正交特征向量整理课件第三步：求解线性方程组的标准正交根底解系vr+1…vm，令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=V

UT，考虑A对应的线性变换Au1u2

1v1

2v2

2u2

1u1SAS

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)m×n来存储。矩阵A的元素aij是一个正的数，它相应于象素的灰度水平〔graylevel〕的度量值。由于一般来讲，相邻的象素会产生相近的灰度水平值，因此有可能在满足图像清晰度要求的条件下，将存储一个m×n阶矩阵需要存储的m×n个数减少到n+m+1的一个倍数。整理课件压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的逼近。如果图象的数字矩阵A的奇异值分解为：A=U

VT，其展开式：压缩矩阵A的方法是取一个秩为k(k

r)的矩阵Ak来逼近矩阵A。Ak按如下方法选取：这是矩阵A的秩1分解式。整理课件在秩为k(k

n)的所有矩阵中，矩阵Ak所对应的图象和矩阵A所对应的图象最相近。一般的，k越大图象就越清晰。压缩比：

=(m+n+1)/mn;经典的方法是选取接近k，使Ak的存储量比A的存储量减少20%。整理课件整理课件整理课件整理课件整理课件矩阵奇异值分解的特点：2.奇异值对矩阵的扰动不敏感,而特征值对矩阵的扰动敏感。3.奇异值的比例不变性。即kA的奇异值是A的奇异值的|k|倍。4.奇异值的旋转不变性。即假设P是正交阵,PA的奇异值与A的奇异值相同。奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放大、缩小等几何变化方面有很好的应用。整理课件5.容易得到矩阵A的秩为k(k≤r)〔低秩〕的一个最正确逼近矩阵。奇异值的这个特征可以应用于信号的分解和重构,提取有用信息,消除信号噪声等6.假设A、B都有相同的奇异向量,那么||A–B||2=,即,我们可以通过控制奇异值的大小来控制两个矩阵空间的距离。整理课件存储矩阵Ak只需要存储k个奇异值，k个m维向量ui和n维向量vj的所有分量，共计k〔m+n+1〕个元素。如果m=n=1000