矩阵的因子分解PPT讲稿.ppt

《矩阵的因子分解PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《矩阵的因子分解PPT讲稿.ppt（100页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、种变换，其目的是将矩阵变其目的是将矩阵变换成特殊的矩阵。换成特殊的矩阵。第3页，共100页，编辑于2022年，星期日 4.2 矩阵的满秩分解矩阵的满秩分解满秩分解定理：满秩分解定理：设设 为任意矩阵，则存在为任意矩阵，则存在 使得使得 A=BC,其中其中B为列满秩矩阵为列满秩矩阵,C为行满秩矩阵为行满秩矩阵.v任一非（行或列）满秩的非零矩阵可表示为一列满秩矩阵和一行满秩矩阵的积；vB的列可取为A的列的任一极大线性无关组；vC可取为其行为A的行所生成的空间的基,然后用定理确定矩阵B。v应用于极小最小二乘解和极小范数最小二乘解的算法中。应用于极小最小二乘解和极小范数最小二乘解的算法中。第4页，共1

3、00页，编辑于2022年，星期日例例1 求下面矩阵的满秩分解求下面矩阵的满秩分解解解 思路：思路：对矩阵对矩阵A实施初等行变换得实施初等行变换得简化阶梯简化阶梯形矩阵形矩阵H（阶梯型（阶梯型的非零行的第一个非零元为的非零行的第一个非零元为1，其所在的列其它元素为，其所在的列其它元素为0）,取取A的的r个个使使H阵满秩的列为阵满秩的列为B，将，将H全为零的行去掉后即可构成行满秩矩阵全为零的行去掉后即可构成行满秩矩阵C。第5页，共100页，编辑于2022年，星期日由此可知由此可知rank(A)=2，且该矩阵第一列、第三列是线性无关的。选，且该矩阵第一列、第三列是线性无关的。选取取第6页，共100页

4、，编辑于2022年，星期日同样，我们也可以选取同样，我们也可以选取 由上述例子可以看出矩阵的满秩分解形式并不唯一。但由上述例子可以看出矩阵的满秩分解形式并不唯一。但是不同的分解形式之间有如下联系：是不同的分解形式之间有如下联系：注：注：如果如果 均为矩阵均为矩阵A 的满秩分解，那么存在矩阵的满秩分解，那么存在矩阵 满足满足第7页，共100页，编辑于2022年，星期日则称其为则称其为A的的 LU 分解或三角分解分解或三角分解。4.3 矩阵的三角分解矩阵的三角分解定义定义1 如果方阵如果方阵A可以分解成一个可以分解成一个单位下三角矩阵单位下三角矩阵L与一个与一个上三角矩上三角矩阵阵U的乘积的乘积第

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

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

7、分解定理)设设A是是n阶非奇异矩阵，则存在唯一的单位下三角矩阵阶非奇异矩阵，则存在唯一的单位下三角矩阵L，对角，对角矩阵矩阵D=diag(d1,d2,dn)和单位上三角矩阵和单位上三角矩阵U，使得，使得 A=LDU的充要条件是的充要条件是A的所有顺序主子式均非零，即的所有顺序主子式均非零，即第14页，共100页，编辑于2022年，星期日矩阵的矩阵的LU分解方法分解方法 矩阵的矩阵的LU分解方法有很多种，这里主要介绍初等行变换消元法分解方法有很多种，这里主要介绍初等行变换消元法 步骤：步骤：1.通过初等行变换将通过初等行变换将A化为上三角矩阵化为上三角矩阵U：（A，I）（U，L1）2.取取L=：

8、因为：因为L1是一系列是一系列初等下三角矩阵初等下三角矩阵乘积（对应初等行乘积（对应初等行变换），所以变换），所以L是单位下三角矩阵。是单位下三角矩阵。第15页，共100页，编辑于2022年，星期日例 1 求下列矩阵的求下列矩阵的LU分解：分解：第16页，共100页，编辑于2022年，星期日解：解：从而得从而得 这里这里第17页，共100页，编辑于2022年，星期日因为因为所以所以第18页，共100页，编辑于2022年，星期日1.即使矩阵即使矩阵A非奇异，如果非奇异，如果A不满足前不满足前n-1个顺序主子式非零，个顺序主子式非零，未必能未必能做做LU分解，分解，2.适当改变非奇异矩阵的行的次序

9、，可使改变后的矩阵做适当改变非奇异矩阵的行的次序，可使改变后的矩阵做LU分解，分解，引入排列阵的概念引入排列阵的概念说明说明第19页，共100页，编辑于2022年，星期日定义定义1 设设e1,e2,en是是n阶单位矩阵阶单位矩阵I的的n个列向量，矩阵个列向量，矩阵P=(ei1,ei2,ein)称为一个称为一个n阶排列阵阶排列阵，其中，其中i1,i2,in是是1,2n的一的一个排列个排列.vP是排列阵的充要条件是是排列阵的充要条件是P为为一系列一系列形如形如P(i,j)的初等交换矩阵的初等交换矩阵的乘积的乘积.第20页，共100页，编辑于2022年，星期日排列阵的性质：排列阵的性质：1.P是排列

10、阵，则是排列阵，则PT和和P-1也是排列阵，且也是排列阵，且PT=P-12.P1，P2是排列阵，则是排列阵，则P1P2是排列阵是排列阵3.即：用排列阵左乘矩阵即：用排列阵左乘矩阵A相当于将相当于将A的行按照排列阵的次序重排，的行按照排列阵的次序重排，右乘对右乘对A的列按排列阵的次序重排。的列按排列阵的次序重排。第21页，共100页，编辑于2022年，星期日引理引理1 设设A是是n阶非奇异矩阵，则存在排列阵阶非奇异矩阵，则存在排列阵P，使得，使得PA的的所有顺序主子式要条件均非零。所有顺序主子式要条件均非零。定理定理3 设设A是是n阶非奇异矩阵，则存在排列阵阶非奇异矩阵，则存在排列阵P，使得，使

11、得 PA=LDU所其中所其中L是单位下三角矩阵，是单位下三角矩阵，U是单位上三角矩阵，是单位上三角矩阵，D是对角矩阵。是对角矩阵。第22页，共100页，编辑于2022年，星期日三角方程组易于求解矩阵LU分解的一个应用解线性方程组第23页，共100页，编辑于2022年，星期日定理 设矩阵A对称正定，则存在唯一的对角元为正的下三角阵 L，使得 称为对称正定矩阵A的乔累斯基分解 利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法v MATLAB函数：Chol(A)；lu(A)是求矩阵的是求矩阵的LU分解函数分解函数乔累斯基（Cholesky）分解第24页，共

12、100页，编辑于2022年，星期日4.4 QR分解分解 QR分解在矩阵计算中占据相当重要的地位。利用分解在矩阵计算中占据相当重要的地位。利用QR分解，可以分解，可以解决各种应用中（例如图像压缩处理、结构分析等）出现的最小二乘问解决各种应用中（例如图像压缩处理、结构分析等）出现的最小二乘问题、特征值问题等矩阵计算中的核心问题。题、特征值问题等矩阵计算中的核心问题。以以初等变换初等变换为工具的三角分解无法消除病态矩阵的不稳定性，因此为工具的三角分解无法消除病态矩阵的不稳定性，因此引入以引入以正交变换正交变换为工具的为工具的QR分解方法分解方法第25页，共100页，编辑于2022年，星期日定理定理1

13、(QR分解定理分解定理)设设A是是n阶阶非奇异非奇异实（复）矩阵，则存在实（复）矩阵，则存在正交（酉）矩阵正交（酉）矩阵Q与非奇异与非奇异实（复）上三角矩阵实（复）上三角矩阵R，使得，使得 A=QR且除去相差一个对角元绝对值全等于且除去相差一个对角元绝对值全等于1的对角矩阵因子，分解式是的对角矩阵因子，分解式是唯一的。唯一的。v矩阵的矩阵的QR分解也称为正交三角分解；分解也称为正交三角分解；v若规定上三角矩阵若规定上三角矩阵R的对角元符号，则的对角元符号，则A的的QR分解唯一。分解唯一。第26页，共100页，编辑于2022年，星期日证明：证明：先证明分解的存在性。将矩阵先证明分解的存在性。将矩

14、阵A按列分块得到按列分块得到由于由于 ，所以，所以 是线性无关的。利用是线性无关的。利用Schmidt正正交化与单位化方法，先得到一组正交向量组交化与单位化方法，先得到一组正交向量组再单位化，这样得到一组标准正交向量组再单位化，这样得到一组标准正交向量组并且向量组之间有如下关系并且向量组之间有如下关系第27页，共100页，编辑于2022年，星期日于是有于是有第28页，共100页，编辑于2022年，星期日为正交矩阵。为正交矩阵。证毕证毕第29页，共100页，编辑于2022年，星期日唯一性：设唯一性：设A=QR=Q1R1,则则 Q=Q1R1R-1=Q1D，其中其中D=R1R-1为非奇异上三角矩阵，

15、于是为非奇异上三角矩阵，于是I=QHQ=(Q1D)H(Q1D)=DHD所以所以D为酉矩阵，比较为酉矩阵，比较DHD=DDH=I的对角元，可得的对角元，可得D为对为对角矩阵，且对角元的模为角矩阵，且对角元的模为1，于是，于是R1=DR,Q1=QD-1证毕证毕第30页，共100页，编辑于2022年，星期日定理定理2 设设A是是列满秩列满秩的的m n实（复）矩阵，则存在实（复）矩阵，则存在m阶正交阶正交（酉）矩阵（酉）矩阵Q和和n阶非奇异实（复）上三角矩阵阶非奇异实（复）上三角矩阵R，使得，使得定理定理3 设设A是是m n矩阵矩阵，且，且rank(A)=r0,则存在则存在m阶正交阶正交（酉）矩阵（酉

16、）矩阵Q和和r n阶行满秩矩阵阶行满秩矩阵R，使得，使得非奇异矩阵的非奇异矩阵的QR分解的推广：分解的推广：第31页，共100页，编辑于2022年，星期日推论推论 设设A是是m n矩阵，且矩阵，且rank(A)=r0,则存在则存在m r列正交规范矩阵列正交规范矩阵Q1和和r n行满秩矩阵行满秩矩阵R，使得，使得 A=Q1R，v列正交规范矩阵指的是列正交规范矩阵指的是m r矩阵矩阵Q1满足满足 。矩阵矩阵Q1是列正交规范矩阵的是列正交规范矩阵的充要条件充要条件是是Q1的列向量组是标准正交向的列向量组是标准正交向量组量组第32页，共100页，编辑于2022年，星期日一、一、Schmidt 方法方法

17、步骤：步骤：1.将矩阵将矩阵A的列向量的列向量 1，2，n施以施以Schmidt标准标准正交化正交化,得得到到 1，2，n 标准正交组标准正交组：2.取取Q=(1，2，n)，则则Q为正交矩阵为正交矩阵 3.取取R=QTA矩阵的矩阵的QR分解方法分解方法第33页，共100页，编辑于2022年，星期日例1 利用利用Schmidt 方法将下列矩阵进行方法将下列矩阵进行QR分解：分解：第34页，共100页，编辑于2022年，星期日解解 先将先将A=1，2，3 的三个列向量正交化与单位化：的三个列向量正交化与单位化：第35页，共100页，编辑于2022年，星期日所以所以A的的QR分解为：分解为：A=QR

18、第36页，共100页，编辑于2022年，星期日从而从而1.取取A的列向量的列向量 1，2，n，对对 1，由由Householder矩阵性质知存矩阵性质知存在在Householder 矩阵矩阵H1，使得（为方便说明，不妨取负号）使得（为方便说明，不妨取负号）二、二、Householder 变换法变换法步骤：步骤：第37页，共100页，编辑于2022年，星期日从而从而2.对对 ，当当 时时，存在存在Householder 矩阵矩阵H2，使使得得第38页，共100页，编辑于2022年，星期日则得则得取取如果如果 ，则则 ，直接进行下一步。直接进行下一步。第39页，共100页，编辑于2022年，星期日

19、使得使得3.对对An-2 继续类似的变换继续类似的变换，如此最多如此最多n-1步，也即至多可以找到步，也即至多可以找到n-1个矩阵个矩阵令令Q=Hn-1H2H1，则则Q为正交矩阵，从而得到为正交矩阵，从而得到QR分解分解第40页，共100页，编辑于2022年，星期日例2 利用利用Householder变换将下列矩阵进行变换将下列矩阵进行QR分解分解第41页，共100页，编辑于2022年，星期日对向量对向量 ，令，令解：从而得从而得Householder 矩阵矩阵第42页，共100页，编辑于2022年，星期日使得使得 注意注意 ，即，即 被被 反射到反射到对向量对向量 ，令，令可得可得House

20、holder 矩阵矩阵第43页，共100页，编辑于2022年，星期日因此取因此取从而有从而有第44页，共100页，编辑于2022年，星期日所求的所求的QR分解为分解为第45页，共100页，编辑于2022年，星期日定义定义1 设设A，B Rn n(Cn n),若存在若存在n阶正交（酉）矩阵阶正交（酉）矩阵U使得使得 UTAU=U-1AU=B（UHAU=U-1AU=B），称称A正交（酉）相似正交（酉）相似B。4.5 Schur 定理和正规矩阵定理和正规矩阵 (SchurSchur theory and Normal Matrices theory and Normal Matrices)定理定理1

21、（Schur定理）定理）任何一个任何一个n阶复矩阵阶复矩阵A都酉相似于一个上三角矩都酉相似于一个上三角矩阵阵，即存在一个即存在一个n阶酉矩阵阶酉矩阵U和一个和一个n阶上三角矩阵阶上三角矩阵R使得使得 UHAU=R其中其中R的对角元是的对角元是A的特征值，可以按要求的顺序排列的特征值，可以按要求的顺序排列第46页，共100页，编辑于2022年，星期日定义定义2 设设A Cn n，若，若AHA=AAH，称，称A为为正规矩阵。正规矩阵。常见的正规矩阵：常见的正规矩阵：对角矩阵对角矩阵对角矩阵对角矩阵;对称和反对称矩阵：对称和反对称矩阵：对称和反对称矩阵：对称和反对称矩阵：A AT T=A A，A A

22、T T=A A。HermiteHermite矩阵和反矩阵和反矩阵和反矩阵和反HermiteHermite矩阵：矩阵：矩阵：矩阵：A AHH=A A，A AHH=A A正交矩阵和酉矩阵：正交矩阵和酉矩阵：正交矩阵和酉矩阵：正交矩阵和酉矩阵：A AT TA=AAA=AAT T=I I，A AHHA A=AAAAHH=I I。正规矩阵正规矩阵第47页，共100页，编辑于2022年，星期日正规矩阵的性质：1.1.正规矩阵有n个线性无关的特征向量；2.正规矩阵属于不同特征值的特征向量是正交的；正规矩阵属于不同特征值的特征向量是正交的；3.与正规矩阵酉相似的矩阵都是正规矩阵。与正规矩阵酉相似的矩阵都是正规

23、矩阵。第48页，共100页，编辑于2022年，星期日由定理由定理由定理由定理2 2 若若若若A A是是是是n n阶正规矩阵，则阶正规矩阵，则阶正规矩阵，则阶正规矩阵，则A A酉相似于一个对角阵，酉相似于一个对角阵，酉相似于一个对角阵，酉相似于一个对角阵，即存在即存在一个一个n阶酉矩阵阶酉矩阵U使得使得 UHAU=，其中其中=diag(1,n),i(i=1,2,n)是是A的特征值。的特征值。该式称为该式称为正规矩阵的谱分解式正规矩阵的谱分解式.正规是酉相似的不变性质正规是酉相似的不变性质定理定理2 n n阶矩阵阶矩阵阶矩阵阶矩阵A A酉相似于一个酉相似于一个酉相似于一个酉相似于一个对角阵对角阵的

24、充要条件是的充要条件是的充要条件是的充要条件是A A是是是是正规矩正规矩阵。阵。第49页，共100页，编辑于2022年，星期日即即 i是矩阵是矩阵 A的特征值的特征值 i所对应的所对应的单位特征向量单位特征向量。设设U=(1,2,n),则由定理则由定理2知知 UHAU=diag(1,n),可得可得即即A i=i i（1,2,n）求谱分解式的步骤第50页，共100页，编辑于2022年，星期日例例1：求正规矩阵求正规矩阵的谱分解表达式。的谱分解表达式。解：解：首先求出矩阵首先求出矩阵A 的特征值与特征向量。容易计算的特征值与特征向量。容易计算第51页，共100页，编辑于2022年，星期日从而从而A

25、的特征值为的特征值为 1=2=3=1,4=-3当当=1时，求得三个线性无关的特征向量为时，求得三个线性无关的特征向量为 1=1,1,0,0T 2=1,0,1,0T 3=-1,0,0,1T第52页，共100页，编辑于2022年，星期日当当=-3时，求得一个线性无关的特征向量为时，求得一个线性无关的特征向量为 4=1,-1,-1,1T将将 1,2,3正交化与单位化可得正交化与单位化可得第53页，共100页，编辑于2022年，星期日将将4单位化可得：单位化可得：于是有于是有这样可得其谱分解表达式为这样可得其谱分解表达式为A=U UH第54页，共100页，编辑于2022年，星期日推论推论1 设设A是是

26、n n阶阶阶阶HermiteHermite矩阵，则矩阵，则矩阵，则矩阵，则A必酉相似于对角矩阵，即存在必酉相似于对角矩阵，即存在一个一个n阶酉矩阵阶酉矩阵U使得使得 UHAU=，其中其中=diag(1,n),i(i=1,2,n)是是A的的实特征值实特征值。该分解式该分解式称为称为Hermite矩阵矩阵A的谱分解式的谱分解式。第55页，共100页，编辑于2022年，星期日是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后续计算的复杂度，在续计算的复杂度，在“预处理预处理”阶段通常要先对原始数据进行降维阶段通常要先对原始数据进行

27、降维。原则：原则：降维后的数据不能失真，也就是说，被降维后的数据不能失真，也就是说，被PCAPCA降掉的那些维度只能是降掉的那些维度只能是那些噪声或是冗余的那些噪声或是冗余的 目的就是目的就是“降噪降噪”和和“去冗余去冗余”。“降噪降噪”的目的就是使保留下来的维度间的相关性尽可能小，的目的就是使保留下来的维度间的相关性尽可能小，“去冗余去冗余”的目的就是使保留下来的维度含有的的目的就是使保留下来的维度含有的“能量能量”尽尽可能大。可能大。著名的著名的PCA（Principal Component Analysis）第56页，共100页，编辑于2022年，星期日1.形成形成样样本矩本矩阵阵S N

28、 d，假，假设设我我们们有一个有一个样样本集本集X，里面有，里面有N个个样样本，每个本，每个样样本的本的维维度度为为d。即：。即：即每行即每行为为一个一个样样本，每一列本，每一列为为一个一个维维度，得到度，得到样样本矩本矩阵阵S著名的著名的PCA（Principal Component Analysis）第57页，共100页，编辑于2022年，星期日2.计计算算样样本矩本矩阵阵的的协协方差矩方差矩阵阵；协协方差矩方差矩阵阵度量的是度量的是维维度与度与维维度之度之间间的关系，主的关系，主对对角角线线上的元上的元素是各个素是各个维维度上的方差度上的方差(即能量即能量)，其他元素是两两，其他元素是两

29、两维维度度间间的的协协方差方差(即相关性即相关性)。著名的著名的PCA（Principal Component Analysis）第58页，共100页，编辑于2022年，星期日3.（1）去噪）去噪对协对协方差矩方差矩阵阵S进进行行谱谱分解，去不同分解，去不同维维度的相关性（非度的相关性（非对对角元素角元素化化为为0）找到一个正交矩）找到一个正交矩阵阵P，满满足足（2）降）降维维 选选取取 中中最大的最大的p个特征个特征值对应值对应的特征向量的特征向量组组成投影矩成投影矩阵阵P1：取最大的前取最大的前p(p0,称称 i为为A的的正奇异值。正奇异值。另一种定义：另一种定义：第65页，共100页，编

30、辑于2022年，星期日定理定理1：正规矩阵正规矩阵正规矩阵正规矩阵A A的奇异值等于的奇异值等于的奇异值等于的奇异值等于A A的特征值的模长。的特征值的模长。的特征值的模长。的特征值的模长。证：证：根据正规矩阵的性质，知存在酉矩阵根据正规矩阵的性质，知存在酉矩阵根据正规矩阵的性质，知存在酉矩阵根据正规矩阵的性质，知存在酉矩阵U U使得使得使得使得 A=Udiag A=Udiag(1,2,n)U UHH,其中其中其中其中 1,2,n是是是是A A的特征值，的特征值，的特征值，的特征值，所以所以所以所以AHA=Udiag=Udiag(|(|1|2 2,|2|2 2,|n|2 2)U UHH所以所以

31、所以所以A A的奇异值为的奇异值为的奇异值为的奇异值为|1|,|2|,|n|#第66页，共100页，编辑于2022年，星期日定理定理2（奇异值分解定理）（奇异值分解定理）设设A C mn，秩（秩（A）=r，则存在则存在m阶酉阶酉矩阵矩阵V和和n阶酉矩阵阶酉矩阵U使得使得 其中其中=diag(1,r),且且 1 r0.第67页，共100页，编辑于2022年，星期日1.U的列向量是的列向量是AHA的标准正交特征向量；（也称为悬挂矩阵）的标准正交特征向量；（也称为悬挂矩阵）2.U的前的前r列向量是列向量是AHA对应于对应于r个非零特征值个非零特征值 12，r2的标准正交的标准正交特征向量；特征向量；

32、3.V的列向量是的列向量是AAH的标准正交特征向量；（也称为对准矩阵）的标准正交特征向量；（也称为对准矩阵）4.V的前的前r列向量是列向量是AHA对应于特征值对应于特征值 12，r2的标准正交特征向的标准正交特征向量；量；注记：注记：第68页，共100页，编辑于2022年，星期日第二步第二步：令令 U1=(u1 ur),计算计算求矩阵求矩阵SVD的算法的算法第一步第一步：计算计算 ，并计算特征值，并计算特征值 1 n和对应的标准正交特征向和对应的标准正交特征向量量u1 un，取取U=(u1 un)注：注：根据这样的取法得根据这样的取法得AAHV1=A(AHAU1)-1=A(U1 2)-1=AU

33、1=V1 2即：即：V1对应于特征值对应于特征值 12，r2的标准正交特征向量的标准正交特征向量第69页，共100页，编辑于2022年，星期日第三步第三步：求解线性方程组求解线性方程组 的标准正交基础解系的标准正交基础解系vr+1 vm，令令V=(v1,vr,vr+1,.vm)则则U和和V即为所求。即为所求。第70页，共100页，编辑于2022年，星期日例 1 求下列矩阵的SVD分解：解：第一步第71页，共100页，编辑于2022年，星期日矩阵AHA的特征值为3,1,0，对应的特征向量为标准正交化得第72页，共100页，编辑于2022年，星期日第二步 令：计算：其中其中第73页，共100页，编

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

35、下。下面计算面计算AAH的标准正交特征向量，解得分别与的标准正交特征向量，解得分别与5，0，0对应的三对应的三个标准正交特征向量个标准正交特征向量由这三个标准正交特征向量组成矩阵由这三个标准正交特征向量组成矩阵V，所以有，所以有第78页，共100页，编辑于2022年，星期日于是可得奇异值分解式为于是可得奇异值分解式为第79页，共100页，编辑于2022年，星期日注：注：使用第二种方法时选取的使用第二种方法时选取的U和和V不唯一，他们的对应列之间相差不唯一，他们的对应列之间相差一个符号，因此当分解式不成立时，需要调整相应的特征向量符号。一个符号，因此当分解式不成立时，需要调整相应的特征向量符号。

36、第80页，共100页，编辑于2022年，星期日SVD的几何意义的几何意义:圆圆S经过变换经过变换A，变成椭圆，变成椭圆AS。圆的正交方向。圆的正交方向u1,u2 变成椭圆的变成椭圆的长、短轴方向长、短轴方向 ,。设矩阵设矩阵A的奇异值分解为的奇异值分解为A=V UT，考虑考虑A对应的线性变换对应的线性变换Au1u2 1v1 2v2 2u2 1u1SAS 1v1 2v2第81页，共100页，编辑于2022年，星期日 从变换的角度理解从变换的角度理解SVD，酉变换，酉变换U保持球面不变，对角矩阵保持球面不变，对角矩阵 将球将球面拉伸到一个有标准基的椭圆面拉伸到一个有标准基的椭圆(1，2是是A的两个

37、奇异值，对应椭圆的两个奇异值，对应椭圆的长半轴和短半轴的长半轴和短半轴)，最后酉变换最后酉变换V旋转或镜射这个椭圆，但不改变它旋转或镜射这个椭圆，但不改变它的形状。的形状。第82页，共100页，编辑于2022年，星期日矩阵奇异值分解的特点：矩阵奇异值分解的特点：1.数据压缩：矩阵数据压缩：矩阵Am n的奇异值分解为：的奇异值分解为：A=V UT，其展开式：其展开式：vA有有nm个数据个数据，分解后为分解后为(m+n+1)r个数据个数据，若若A的秩的秩r远远小于远远小于m和和n,则通过奇异值分解可以大大降低则通过奇异值分解可以大大降低A的维数的维数,可以达到降维的目的可以达到降维的目的,同时同时

38、可以降低计算机对存贮器的要求，常用于图像压缩可以降低计算机对存贮器的要求，常用于图像压缩。奇异值的减少特别的快，在很多情况下，前奇异值的减少特别的快，在很多情况下，前10%甚至甚至1%的奇异的奇异值的和就占了全部的奇异值之和的值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也以上了。也就是说，我们也可以用前可以用前k个大的奇异值来近似描述矩阵。个大的奇异值来近似描述矩阵。第83页，共100页，编辑于2022年，星期日图像图像的数字化技术与矩阵的奇异值分解的数字化技术与矩阵的奇异值分解 v计算机处理图像技术的第一步是图像的数字化存储技术，即将图像转计算机处理图像技术的第一步是图像的数字

39、化存储技术，即将图像转换成矩阵来存储。换成矩阵来存储。v转换的原理是将图形分解成象素（转换的原理是将图形分解成象素（pixels）的一个矩形的数阵，其）的一个矩形的数阵，其中的信息就可以用一个矩阵中的信息就可以用一个矩阵A=(aij)mn来存储。矩阵来存储。矩阵A的元素的元素aij 是一个是一个正的数，它相应于象素的灰度水平（正的数，它相应于象素的灰度水平（gray level）的度量值。的度量值。v由于一般来讲，相邻的象素会产生相近的灰度水平值，因此有由于一般来讲，相邻的象素会产生相近的灰度水平值，因此有可能在满足图像清晰度要求的条件下，将存储一个可能在满足图像清晰度要求的条件下，将存储一个

40、mn阶矩阵需阶矩阵需要存储的要存储的mn个数减少到个数减少到n+m+1的一个倍数的一个倍数。第84页，共100页，编辑于2022年，星期日v压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的逼近。如果图象的数字矩阵A的奇异值分解为：A=U VT，其展开式：压缩矩阵压缩矩阵A的方法是取一个秩为的方法是取一个秩为k(k r)的矩阵的矩阵Ak 来逼近矩阵来逼近矩阵A。Ak按如下方法选取：按如下方法选取：这是矩阵这是矩阵A的秩的秩1分解式分解式。第85页，共100页，编辑于2022年，星期日在在秩秩为为k(k n)的的所所有有矩矩阵阵中中，矩矩阵阵Ak所所对对应应的的图图象象和和矩矩阵

41、阵A所所对对应应的的图图象象最最相相近近。一一般般的的，k越越大大图图象象就就越越清清晰晰。压压缩缩比比：=(m+n+1)/mn;经典的方法是选取接近经典的方法是选取接近k，使使Ak的存储量比的存储量比A的存储量减少的存储量减少20%。第86页，共100页，编辑于2022年，星期日第87页，共100页，编辑于2022年，星期日第88页，共100页，编辑于2022年，星期日第89页，共100页，编辑于2022年，星期日第90页，共100页，编辑于2022年，星期日矩阵奇异值分解的特点：矩阵奇异值分解的特点：2.奇异值对矩阵的扰动不敏感奇异值对矩阵的扰动不敏感,而特征值对矩阵的扰动敏感而特征值对矩

42、阵的扰动敏感。3.奇异值的比例不变性。即奇异值的比例不变性。即kA的奇异值是的奇异值是A的奇异值的的奇异值的|k|倍倍。4.奇异值的旋转不变性。即若奇异值的旋转不变性。即若P是正交阵是正交阵,PA的奇异值与的奇异值与A的奇异值相的奇异值相同。同。v奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放大、缩小等几何变化方面有很好的应用。大、缩小等几何变化方面有很好的应用。第91页，共100页，编辑于2022年，星期日5.容易得到矩阵容易得到矩阵A的秩为的秩为k(kr)（低秩）的一个最佳逼近矩阵。（低秩）的一个最佳逼近矩阵。v奇异

43、值的这个特征可以应用于信号的分解和重构奇异值的这个特征可以应用于信号的分解和重构,提取有用提取有用信息信息,消除信号噪声等消除信号噪声等6.若若A、B都有相同的奇异向量都有相同的奇异向量,则则|A B|2=,即即,我们可以通过控制奇异值的大小来控制两个矩阵空间的距离。我们可以通过控制奇异值的大小来控制两个矩阵空间的距离。第92页，共100页，编辑于2022年，星期日v存储矩阵存储矩阵Ak只需要存储只需要存储k个奇异值，个奇异值，k个个m维向量维向量ui和和n维向维向量量vj的所有分量，共计的所有分量，共计k（m+n+1）个元素。个元素。v如果如果m=n=1000=1000，存储原矩阵，存储原矩

44、阵A需要存储需要存储1000100010001000个元素。个元素。取取k=100=100时，图象已经非常清晰了，这时的存储量是时，图象已经非常清晰了，这时的存储量是100100（2000+12000+1）=200100=200100个数。个数。v和矩阵和矩阵A比较，存储量减少了比较，存储量减少了80%80%。第93页，共100页，编辑于2022年，星期日SVD用于文本分类用于文本分类 用一个大矩阵用一个大矩阵A来描述一百万篇文章和五十万词的关联性。这个矩阵中，来描述一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文每一行对应一篇文 章，每一列对应一个词。章，每一列对应一个词。M=1

45、,000,000=1,000,000，N=500,000500,000。第。第 i 行第行第 j 列的元素，是字典中第列的元素，是字典中第 j 个词在第个词在第 i 篇文章篇文章中出现的加权词频（这个矩阵一般称为关联矩阵）。这个矩阵非常大，中出现的加权词频（这个矩阵一般称为关联矩阵）。这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。有一百万乘以五十万，即五千亿个元素。第94页，共100页，编辑于2022年，星期日 奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，比如把矩阵分解成一个一百万乘以一百的矩阵比如把矩阵分解成一个一

46、百万乘以一百的矩阵V，一个一百乘以一，一个一百乘以一百的百的 矩阵矩阵，和一个一百乘以五十万的矩阵，和一个一百乘以五十万的矩阵U。这三个矩阵的元素总。这三个矩阵的元素总数加起来也不过数加起来也不过1.51.5亿，仅仅是原来的三千分之一。相应的存储亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数量级以量和计算量都会小三个数量级以 上。上。Am nV UT=m rr rr n第95页，共100页，编辑于2022年，星期日三三 个矩阵有非常清楚的含义：第一个矩阵个矩阵有非常清楚的含义：第一个矩阵V中的每一行表示意思中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重相

47、关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越要性（或者说相关性），数值越大越 相关。最后一个矩阵相关。最后一个矩阵U中中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章类之间的相关性。因此，章的相关性。中间的矩阵则表示类词和文章类之间的相关性。因此，我们只要对关联矩阵我们只要对关联矩阵A进行一次奇异值分解，进行一次奇异值分解，我们就可以同时完成了我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关性）近义词分类和文章的

48、分类。（同时得到每类文章和每类词的相关性）第96页，共100页，编辑于2022年，星期日 这是一个矩阵，这里的一行表示一个词在哪些title中出现了,一列表示一个title中哪些词。例：第97页，共100页，编辑于2022年，星期日SVD的结果v左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性，中间的奇异值矩阵表示左奇异向量的一行与右奇异向量的一列的重要程度，数字越大越重要第98页，共100页，编辑于2022年，星期日将左奇异向量和右奇异向量都取后2维（之前是3维的矩阵），投影到一个平面上，可以得到第99页，共100页，编辑于2022年，星期日图上，每一个红色的点，都表示一个词，每一个蓝色的点，都表示一篇文档，这样我们可以对这些词和文档进行聚类，比如说stock 和 market可以放在一类，因为他们老是出现在一起，real和estate可以放在一类，dads，guide这种词就看起来有点孤立了，我们就不对他们进行合并了。按这样聚类出现的效果，可以提取文档集合中的近义词，这样当用户检索文档的时候，是用语义级别（近义词集合）去检索了，而不是之前的词的级别。第100页，共100页，编辑于2022年，星期日