矩阵的因子分解

1、矩阵的因子分解第1页，共100页，2022年，5月20日，9点20分，星期五 数据集中可能包含大量特征，维灾难使得数据分析很困难，1.维归约（降维）：利用旧属性的线性组合得到新属性，使得新属性相互正交，捕获到数据的最大变差（PCA：主成分分析(principle components analysis)和SVD）2.选择特征子集：嵌入（决策树分类其），过滤和包装（搜索，特征加权等）第2页，共100页，2022年，5月20日，9点20分，星期五 矩阵的各种分解在矩阵计算中也扮演相当重要的角色。由于变换即矩阵，所以各种分解从根本上看是各种变换，其目的是将矩阵变换成特殊的矩阵。第3页，共100页，2

2、022年，5月20日，9点20分，星期五 4.2 矩阵的满秩分解满秩分解定理：设 为任意矩阵，则存在 使得 A=BC,其中B为列满秩矩阵,C为行满秩矩阵.任一非（行或列）满秩的非零矩阵可表示为一列满秩矩阵和一行满秩矩阵的积；B的列可取为A的列的任一极大线性无关组；C可取为其行为A的行所生成的空间的基, 然后用定理确定矩阵B。应用于极小最小二乘解和极小范数最小二乘解的算法中。 第4页，共100页，2022年，5月20日，9点20分，星期五例1 求下面矩阵的满秩分解解 思路：对矩阵A实施初等行变换得简化阶梯形矩阵H（阶梯型的非零行的第一个非零元为1，其所在的列其它元素为0）,取A的r个使H阵满秩的

3、列为B，将H全为零的行去掉后即可构成行满秩矩阵C。第5页，共100页，2022年，5月20日，9点20分，星期五由此可知rank(A)=2，且该矩阵第一列、第三列是线性无关的。选取第6页，共100页，2022年，5月20日，9点20分，星期五同样，我们也可以选取 由上述例子可以看出矩阵的满秩分解形式并不唯一。但是不同的分解形式之间有如下联系：注：如果 均为矩阵A 的满秩分解，那么存在矩阵 满足第7页，共100页，2022年，5月20日，9点20分，星期五则称其为A的 LU 分解或三角分解。4.3 矩阵的三角分解定义1 如果方阵A可以分解成一个单位下三角矩阵L与一个上三角矩阵U的乘积第8页，共1

4、00页，2022年，5月20日，9点20分，星期五初等下三角矩阵第9页，共100页，2022年，5月20日，9点20分，星期五初等下三角矩阵性质(1)det(Li)=1, 第10页，共100页，2022年，5月20日，9点20分，星期五(2)用初等下三角矩阵左乘矩阵A，等于将A的第i行依次乘以-li+1i,-lni 分别加到第i+1行到第n行上去。(3)设A=(aij) nn,且a jj 0，并且取 则LiA在(i+1,j),(i+2,j)(n,j)的位置上为0第11页，共100页，2022年，5月20日，9点20分，星期五(4)第12页，共100页，2022年，5月20日，9点20分，星期五

5、定理1 ( LU分解定理 ) 设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵L（主对角线上元素全为1的下三角矩阵）与唯一的上三角矩阵U ，使得的充要条件是A的所有顺序主子式均非零，即矩阵的LU分解也称为Doolitte分解若L为下三角矩阵,U为单位上三角矩阵,称为Crout分解。第13页，共100页，2022年，5月20日，9点20分，星期五定理2 ( LDU分解定理 ) 设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵L，对角矩阵D=diag(d1,d2,dn)和单位上三角矩阵U ，使得 A=LDU的充要条件是A的所有顺序主子式均非零，即第14页，共100页，2022年，5月20日，9点2

6、0分，星期五矩阵的LU分解方法 矩阵的LU分解方法有很多种，这里主要介绍初等行变换消元法 步骤： 1. 通过初等行变换将A化为上三角矩阵U： （A，I）（U，L1） 2.取L= ：因为L1是一系列初等下三角矩阵乘积（对应初等行变换），所以L是单位下三角矩阵。第15页，共100页，2022年，5月20日，9点20分，星期五例 1 求下列矩阵的LU分解：第16页，共100页，2022年，5月20日，9点20分，星期五解：从而得 这里第17页，共100页，2022年，5月20日，9点20分，星期五因为所以第18页，共100页，2022年，5月20日，9点20分，星期五1. 即使矩阵A非奇异，如果A不

7、满足前n-1个顺序主子式非零，未必能做LU分解，2.适当改变非奇异矩阵的行的次序，可使改变后的矩阵做LU分解，引入排列阵的概念说明第19页，共100页，2022年，5月20日，9点20分，星期五定义1 设e1, e2, en是n阶单位矩阵I的n个列向量，矩阵P=(ei1, ei2, , ein )称为一个n阶排列阵，其中i1, i2, in是1,2n的一个排列.P是排列阵的充要条件是P为一系列形如P(i,j)的初等交换矩阵的乘积.第20页，共100页，2022年，5月20日，9点20分，星期五排列阵的性质：1. P是排列阵，则PT和P-1也是排列阵，且PT=P-12. P1 ，P2是排列阵，则

8、P1P2是排列阵3.即：用排列阵左乘矩阵A相当于将A的行按照排列阵的次序重排，右乘对A的列按排列阵的次序重排。第21页，共100页，2022年，5月20日，9点20分，星期五引理1 设A是n阶非奇异矩阵，则存在排列阵P，使得PA的所有顺序主子式要条件均非零。定理3 设A是n阶非奇异矩阵，则存在排列阵P，使得 PA=LDU所其中L是单位下三角矩阵，U是单位上三角矩阵，D是对角矩阵。第22页，共100页，2022年，5月20日，9点20分，星期五三角方程组易于求解矩阵LU分解的一个应用解线性方程组第23页，共100页，2022年，5月20日，9点20分，星期五定理 设矩阵A对称正定，则存在唯一的对

9、角元为正的下三角阵 L，使得 称为对称正定矩阵A的乔累斯基分解 利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法 MATLAB函数：Chol(A)；lu(A)是求矩阵的LU分解函数乔累斯基（Cholesky）分解第24页，共100页，2022年，5月20日，9点20分，星期五4.4 QR分解 QR分解在矩阵计算中占据相当重要的地位。利用QR分解，可以解决各种应用中（例如图像压缩处理、结构分析等）出现的最小二乘问题、特征值问题等矩阵计算中的核心问题。以初等变换为工具的三角分解无法消除病态矩阵的不稳定性，因此引入以正交变换为工具的QR分解方法第25页，共

10、100页，2022年，5月20日，9点20分，星期五定理1 ( QR分解定理 ) 设A是n阶非奇异实（复）矩阵，则存在正交（酉）矩阵Q与非奇异实（复）上三角矩阵R ，使得 A=QR且除去相差一个对角元绝对值全等于1的对角矩阵因子，分解式是唯一的。矩阵的QR分解也称为正交三角分解；若规定上三角矩阵R的对角元符号，则A的QR分解唯一。第26页，共100页，2022年，5月20日，9点20分，星期五证明：先证明分解的存在性。将矩阵A按列分块得到由于 ，所以 是线性无关的。利用Schmidt正交化与单位化方法，先得到一组正交向量组再单位化，这样得到一组标准正交向量组并且向量组之间有如下关系第27页，共

11、100页，2022年，5月20日，9点20分，星期五于是有第28页，共100页，2022年，5月20日，9点20分，星期五为正交矩阵。证毕第29页，共100页，2022年，5月20日，9点20分，星期五唯一性：设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证毕第30页，共100页，2022年，5月20日，9点20分，星期五定理2 设A是列满秩的mn实（复）矩阵，则存在m阶正交（酉）矩阵Q和

12、n阶非奇异实（复）上三角矩阵R，使得定理3 设A是mn矩阵，且rank(A)=r0,则存在m阶正交（酉）矩阵Q和r n阶行满秩矩阵R，使得非奇异矩阵的QR分解的推广：第31页，共100页，2022年，5月20日，9点20分，星期五推论 设A是mn矩阵，且rank(A)=r0,则存在mr列正交规范矩阵Q1和rn行满秩矩阵R，使得 A=Q1R，列正交规范矩阵指的是mr矩阵Q1满足 。矩阵Q1是列正交规范矩阵的充要条件是Q1的列向量组是标准正交向量组第32页，共100页，2022年，5月20日，9点20分，星期五一、Schmidt 方法步骤：1.将矩阵A的列向量1， 2 ， n施以Schmidt标准

13、正交化,得到1， 2 ， n 标准正交组：2.取Q=(1， 2 ， n )，则Q为正交矩阵 3. 取R=QTA矩阵的QR分解方法第33页，共100页，2022年，5月20日，9点20分，星期五例1 利用Schmidt 方法将下列矩阵进行QR分解：第34页，共100页，2022年，5月20日，9点20分，星期五解 先将A= 1， 2 ， 3 的三个列向量正交化与单位化：第35页，共100页，2022年，5月20日，9点20分，星期五所以A的QR分解为：A=QR第36页，共100页，2022年，5月20日，9点20分，星期五从而1. 取A的列向量1， 2 ， n，对1，由Householder矩阵

14、性质知存在Householder 矩阵H1，使得（为方便说明，不妨取负号）二、Householder 变换法步骤：第37页，共100页，2022年，5月20日，9点20分，星期五从而2.对 ，当 时，存在Householder 矩阵H2，使得第38页，共100页，2022年，5月20日，9点20分，星期五则得取如果 ，则 ，直接进行下一步。第39页，共100页，2022年，5月20日，9点20分，星期五使得3.对An-2 继续类似的变换，如此最多n-1步，也即至多可以找到n-1个矩阵令Q=Hn-1H2H1，则Q为正交矩阵，从而得到QR分解第40页，共100页，2022年，5月20日，9点20分

15、，星期五例2 利用Householder变换将下列矩阵进行QR分解第41页，共100页，2022年，5月20日，9点20分，星期五对向量 ，令解：从而得Householder 矩阵第42页，共100页，2022年，5月20日，9点20分，星期五使得 注意 ，即 被 反射到对向量 ，令可得Householder 矩阵第43页，共100页，2022年，5月20日，9点20分，星期五因此取从而有第44页，共100页，2022年，5月20日，9点20分，星期五所求的QR分解为第45页，共100页，2022年，5月20日，9点20分，星期五定义1 设A，B Rnn (Cnn),若存在n阶正交（酉）矩阵U

16、使得 UTAU=U-1AU=B（UHAU=U-1AU=B），称A正交（酉）相似B。4.5 Schur 定理和正规矩阵 (Schur theory and Normal Matrices)定理1（Schur定理） 任何一个n阶复矩阵A都酉相似于一个上三角矩阵，即存在一个n阶酉矩阵U和一个n阶上三角矩阵R使得 UHAU=R其中R的对角元是A的特征值，可以按要求的顺序排列第46页，共100页，2022年，5月20日，9点20分，星期五定义2 设ACnn，若AHA=AAH，称A为正规矩阵。常见的正规矩阵：对角矩阵;对称和反对称矩阵：AT=A，AT=A。Hermite矩阵和反Hermite矩阵：AH=A

17、，AH=A正交矩阵和酉矩阵：ATA=AAT=I，AHA=AAH=I。正规矩阵第47页，共100页，2022年，5月20日，9点20分，星期五正规矩阵的性质：1.正规矩阵有n个线性无关的特征向量；2.正规矩阵属于不同特征值的特征向量是正交的；3.与正规矩阵酉相似的矩阵都是正规矩阵。第48页，共100页，2022年，5月20日，9点20分，星期五由定理2 若A是n阶正规矩阵，则A酉相似于一个对角阵，即存在一个n阶酉矩阵U使得 UHAU=，其中=diag(1 , n),i(i=1,2,n)是A的特征值。该式称为正规矩阵的谱分解式.正规是酉相似的不变性质定理2 n阶矩阵A酉相似于一个对角阵的充要条件是

18、A是正规矩阵。第49页，共100页，2022年，5月20日，9点20分，星期五即i是矩阵 A的特征值i所对应的单位特征向量。设U=(1, 2, n),则由定理2知 UHAU=diag(1 , n),可得即Ai= i i（1,2,n）求谱分解式的步骤第50页，共100页，2022年，5月20日，9点20分，星期五例1 ：求正规矩阵的谱分解表达式。解：首先求出矩阵A 的特征值与特征向量。容易计算第51页，共100页，2022年，5月20日，9点20分，星期五从而A的特征值为 1=2= 3=1, 4=-3当=1时，求得三个线性无关的特征向量为 1=1,1,0,0T 2=1,0,1,0T 3=-1,0

19、,0,1T第52页，共100页，2022年，5月20日，9点20分，星期五当=-3时，求得一个线性无关的特征向量为 4=1,-1,-1,1T将 1,2,3正交化与单位化可得第53页，共100页，2022年，5月20日，9点20分，星期五将4单位化可得：于是有这样可得其谱分解表达式为A=UUH第54页，共100页，2022年，5月20日，9点20分，星期五推论1 设A是n阶Hermite矩阵，则A必酉相似于对角矩阵，即存在一个n阶酉矩阵U使得 UHAU=，其中=diag(1 , n),i(i=1,2,n)是A的实特征值。该分解式称为Hermite矩阵A的谱分解式。第55页，共100页，2022年

20、，5月20日，9点20分，星期五是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后续计算的复杂度，在“预处理”阶段通常要先对原始数据进行降维。原则：降维后的数据不能失真，也就是说，被PCA降掉的那些维度只能是那些噪声或是冗余的 目的就是“降噪”和“去冗余”。“降噪”的目的就是使保留下来的维度间的相关性尽可能小，“去冗余”的目的就是使保留下来的维度含有的“能量”尽可能大。著名的PCA（Principal Component Analysis）第56页，共100页，2022年，5月20日，9点20分，星期五形成样本矩阵S Nd，假设我们有一个样本集X，里面有N个样本，每个样本的维度为d。

21、即：即每行为一个样本，每一列为一个维度，得到样本矩阵S著名的PCA（Principal Component Analysis）第57页，共100页，2022年，5月20日，9点20分，星期五2. 计算样本矩阵的协方差矩阵；协方差矩阵度量的是维度与维度之间的关系，主对角线上的元素是各个维度上的方差(即能量)，其他元素是两两维度间的协方差(即相关性)。著名的PCA（Principal Component Analysis）第58页，共100页，2022年，5月20日，9点20分，星期五3. （1）去噪对协方差矩阵S进行谱分解，去不同维度的相关性（非对角元素化为0）找到一个正交矩阵P，满足（2）降维

22、 选取中最大的p个特征值对应的特征向量组成投影矩阵P1： 取最大的前p(p0,称i为A的正奇异值。另一种定义：第65页，共100页，2022年，5月20日，9点20分，星期五定理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| #第66页，共100页，2022年，5月20日，9点20分，星期五定理2 （奇异值分解定理） 设AC mn，秩（A）=r，则存在m阶酉矩阵V和n阶酉矩阵U使得

23、 其中=diag(1, r),且1 r0.第67页，共100页，2022年，5月20日，9点20分，星期五1.U的列向量是AHA的标准正交特征向量；（也称为悬挂矩阵）2.U的前r列向量是AHA对应于r个非零特征值12，r2的标准正交特征向量；3.V的列向量是AAH的标准正交特征向量；（也称为对准矩阵）4.V的前r列向量是AHA对应于特征值12，r2的标准正交特征向量；注记：第68页，共100页，2022年，5月20日，9点20分，星期五第二步： 令 U1=(u1 ur), 计算求矩阵SVD的算法第一步： 计算 ，并计算特征值1 n和对应的标准正交特征向量u1 un，取U=(u1 un)注：根据

24、这样的取法得AAHV1=A(AHAU1)-1=A(U12)-1=AU1=V12即：V1对应于特征值12，r2的标准正交特征向量第69页，共100页，2022年，5月20日，9点20分，星期五第三步： 求解线性方程组 的标准正交基础解系vr+1 vm，令V=(v1,vr,vr+1,. vm)则U和V即为所求。第70页，共100页，2022年，5月20日，9点20分，星期五例 1 求下列矩阵的SVD分解：解：第一步第71页，共100页，2022年，5月20日，9点20分，星期五矩阵AHA的特征值为3,1,0，对应的特征向量为标准正交化得第72页，共100页，2022年，5月20日，9点20分，星期

25、五第二步 令：计算：其中第73页，共100页，2022年，5月20日，9点20分，星期五第三步 解 ，得其基础解系为从而第74页，共100页，2022年，5月20日，9点20分，星期五因此所求SVD为第75页，共100页，2022年，5月20日，9点20分，星期五例2 ：求下列矩阵的奇异值分解表达式第76页，共100页，2022年，5月20日，9点20分，星期五解:（1）计算AHA的特征值分别为5,0。 对应的两个标准正交特征向量由这两个标准正交特征向量组成矩阵U第77页，共100页，2022年，5月20日，9点20分，星期五（2）计算AAH 的特征值为5，0，0，所以A的奇异值为 。下面计算

26、AAH的标准正交特征向量，解得分别与5，0，0对应的三个标准正交特征向量由这三个标准正交特征向量组成矩阵V，所以有第78页，共100页，2022年，5月20日，9点20分，星期五于是可得奇异值分解式为第79页，共100页，2022年，5月20日，9点20分，星期五注：使用第二种方法时选取的U和V不唯一，他们的对应列之间相差一个符号，因此当分解式不成立时，需要调整相应的特征向量符号。第80页，共100页，2022年，5月20日，9点20分，星期五SVD的几何意义: 圆S经过变换A，变成椭圆AS。圆的正交方向u1,u2 变成椭圆的长、短轴方向 , 。设矩阵A的奇异值分解为A=VUT，考虑A对应的线

27、性变换Au1u21v12v22u21u1SAS1v12v2第81页，共100页，2022年，5月20日，9点20分，星期五 从变换的角度理解SVD，酉变换U保持球面不变，对角矩阵 将球面拉伸到一个有标准基的椭圆(1，2是A的两个奇异值，对应椭圆的长半轴和短半轴)，最后酉变换V旋转或镜射这个椭圆，但不改变它的形状。第82页，共100页，2022年，5月20日，9点20分，星期五矩阵奇异值分解的特点：1. 数据压缩：矩阵Amn的奇异值分解为：A=VUT，其展开式：A有nm个数据，分解后为(m+n+1)r个数据，若A的秩r远远小于m和n,则通过奇异值分解可以大大降低A的维数,可以达到降维的目的,同时

28、可以降低计算机对存贮器的要求，常用于图像压缩。奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前k个大的奇异值来近似描述矩阵。第83页，共100页，2022年，5月20日，9点20分，星期五图像的数字化技术与矩阵的奇异值分解 计算机处理图像技术的第一步是图像的数字化存储技术，即将图像转换成矩阵来存储。转换的原理是将图形分解成象素（pixels）的一个矩形的数阵，其中的信息就可以用一个矩阵A=(aij)mn来存储。矩阵A的元素aij 是一个正的数，它相应于象素的灰度水平（gray level） 的度量值。由于一般来讲，相

29、邻的象素会产生相近的灰度水平值，因此有可能在满足图像清晰度要求的条件下，将存储一个mn阶矩阵需要存储的mn个数减少到n+m+1的一个倍数。第84页，共100页，2022年，5月20日，9点20分，星期五压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的逼近。如果图象的数字矩阵A的奇异值分解为：A=UVT，其展开式：压缩矩阵A的方法是取一个秩为k(kr)的矩阵Ak 来逼近矩阵A。Ak按如下方法选取：这是矩阵A的秩1分解式。第85页，共100页，2022年，5月20日，9点20分，星期五在秩为k(kn)的所有矩阵中，矩阵Ak所对应的图象和矩阵A所对应的图象最相近。一般的，k越大图象

30、就越清晰。压缩比：=(m+n+1)/mn;经典的方法是选取接近k，使Ak的存储量比A的存储量减少20%。 第86页，共100页，2022年，5月20日，9点20分，星期五第87页，共100页，2022年，5月20日，9点20分，星期五第88页，共100页，2022年，5月20日，9点20分，星期五第89页，共100页，2022年，5月20日，9点20分，星期五第90页，共100页，2022年，5月20日，9点20分，星期五矩阵奇异值分解的特点：2.奇异值对矩阵的扰动不敏感,而特征值对矩阵的扰动敏感。3.奇异值的比例不变性。即kA的奇异值是A的奇异值的|k|倍。4.奇异值的旋转不变性。即若P是正

31、交阵,PA的奇异值与A的奇异值相同。奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放大、缩小等几何变化方面有很好的应用。第91页，共100页，2022年，5月20日，9点20分，星期五5.容易得到矩阵A的秩为k(kr)（低秩）的一个最佳逼近矩阵。奇异值的这个特征可以应用于信号的分解和重构,提取有用信息,消除信号噪声等6.若A、B都有相同的奇异向量,则|A B|2 = , 即,我们可以通过控制奇异值的大小来控制两个矩阵空间的距离。第92页，共100页，2022年，5月20日，9点20分，星期五存储矩阵Ak只需要存储k个奇异值，k个m维向量ui和n维向量vj的所有分量，共计k（m+n+1）个元素。如果m=n=1000，存储原矩阵A需要存储10001000个元素。取k=100时，图象已经非常清晰了，这时的存储量是100（2000+1）=200100个数。和矩阵A比较，存储量减少了80%。第93页，共100页，2022年，5月20日，9点20分，星期五SVD用于文本分类 用一个大矩阵A来描述一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文 章，每一列对应一个词。M=1