第四章矩阵的因子分解..ppt

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

1、第第4 4章章 矩阵的因子分解矩阵的因子分解（Matrix Factorization and Decomposition）教学要求教学要求掌握矩阵的满秩分解；掌握矩阵的满秩分解；掌握矩阵的三角分解；掌握矩阵的三角分解；掌握矩阵的正交分解；掌握矩阵的正交分解；掌握掌握SchurSchur定理和正规矩阵的定义；定理和正规矩阵的定义；熟练掌握矩阵的奇异值分解；熟练掌握矩阵的奇异值分解；数据集中可能包含大量特征，维灾难使得数据分析很困难，1.维归约（降维）：利用旧属性的线性组合得到新属性，使得新属性相互正交，捕获到数据的最大变差（PCA：主成分分析(principle components anal

2、ysis)和SVD）2.选择特征子集：嵌入（决策树分类其），过滤和包装（搜索，特征加权等）矩阵的各种分解在矩阵计算中也扮演相当重要的角色。矩阵的各种分解在矩阵计算中也扮演相当重要的角色。由于变换即矩阵，由于变换即矩阵，所以各种分解从根本上看是各种变换，所以各种分解从根本上看是各种变换，其目的是将矩阵变换成特殊的矩阵。其目的是将矩阵变换成特殊的矩阵。4.2 矩阵的满秩分解矩阵的满秩分解满秩分解定理：满秩分解定理：设设 为任意矩阵，则存在为任意矩阵，则存在 使得使得 A=BC,其中其中B为列满秩矩阵为列满秩矩阵,C为行满秩矩阵为行满秩矩阵.任一非（行或列）满秩的非零矩阵可表示为一列满秩矩阵和一行满

3、秩矩阵的积；B的列可取为A的列的任一极大线性无关组；C可取为其行为A的行所生成的空间的基,然后用定理确定矩阵B。应用于极小最小二乘解和极小范数最小二乘解的算法中。应用于极小最小二乘解和极小范数最小二乘解的算法中。例例1 求下面矩阵的满秩分解求下面矩阵的满秩分解解解 思路：思路：对矩阵对矩阵A实施初等行变换得实施初等行变换得简化阶梯简化阶梯形矩阵形矩阵H（阶梯型的非零行的第一个非零元为（阶梯型的非零行的第一个非零元为1，其所在的列其它元，其所在的列其它元素为素为0）,取取A的的r个使个使H阵满秩的列为阵满秩的列为B，将，将H全为零的行去全为零的行去掉后即可构成行满秩矩阵掉后即可构成行满秩矩阵C。

4、由此可知由此可知rank(A)=2，且该矩阵第一列、第三列是线性无关的。，且该矩阵第一列、第三列是线性无关的。选取选取同样，我们也可以选取同样，我们也可以选取 由上述例子可以看出矩阵的满秩分解形式并不唯一。由上述例子可以看出矩阵的满秩分解形式并不唯一。但是不同的分解形式之间有如下联系：但是不同的分解形式之间有如下联系：注：注：如果如果 均为矩阵均为矩阵A 的满秩分解，那么存在的满秩分解，那么存在矩阵矩阵 满足满足则称其为则称其为A的的 LU 分解或三角分解分解或三角分解。4.3 矩阵的三角分解矩阵的三角分解定义定义1 如果方阵如果方阵A可以分解成一个可以分解成一个单位下三角矩阵单位下三角矩阵L

5、与一个与一个上三上三角矩阵角矩阵U的乘积的乘积初等下三角矩阵初等下三角矩阵初等下三角矩阵性质初等下三角矩阵性质(1)det(Li)=1,(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(4)定理定理1(LU分解定理分解定理)设设A是是n阶阶非奇异矩阵非奇异矩阵，则存在唯一的，则存在唯一的单位下三角矩阵单位下三角矩阵L（主对

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

7、是的充要条件是A的所有顺序主子式均非零，即的所有顺序主子式均非零，即矩阵的矩阵的LU分解方法分解方法 矩阵的矩阵的LU分解方法有很多种，这里主要介绍初等行变换消分解方法有很多种，这里主要介绍初等行变换消元法元法 步骤：步骤：1.通过初等行变换将通过初等行变换将A化为上三角矩阵化为上三角矩阵U：（A，I）（U，L1）2.取取L=：因为：因为L1是一系列是一系列初等下三角矩阵初等下三角矩阵乘积（对应乘积（对应初等行变换），所以初等行变换），所以L是单位下三角矩阵。是单位下三角矩阵。例 1 求下列矩阵的求下列矩阵的LU分解：分解：解：解：从而得从而得 这里这里因为因为所以所以1.即使矩阵即使矩阵A非

8、奇异，如果非奇异，如果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)的初等交换矩的初等交换矩阵的乘

9、积阵的乘积.排列阵的性质：排列阵的性质：1.P是排列阵，则是排列阵，则PT和和P-1也是排列阵，且也是排列阵，且PT=P-12.P1，P2是排列阵，则是排列阵，则P1P2是排列阵是排列阵3.即：用排列阵左乘矩阵即：用排列阵左乘矩阵A相当于将相当于将A的行按照排列阵的次序重的行按照排列阵的次序重排，右乘对排，右乘对A的列按排列阵的次序重排。的列按排列阵的次序重排。引理引理1 设设A是是n阶非奇异矩阵，则存在排列阵阶非奇异矩阵，则存在排列阵P，使得，使得PA的的所有顺序主子式要条件均非零。所有顺序主子式要条件均非零。定理定理3 设设A是是n阶非奇异矩阵，则存在排列阵阶非奇异矩阵，则存在排列阵P，使

10、得，使得 PA=LDU所其中所其中L是单位下三角矩阵，是单位下三角矩阵，U是单位上三角矩阵，是单位上三角矩阵，D是对角矩阵。是对角矩阵。三角方程组易于求解矩阵LU分解的一个应用解线性方程组定理 设矩阵A对称正定，则存在唯一的对角元为正的下三角阵 L，使得 称为对称正定矩阵A的乔累斯基分解 利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法 MATLAB函数：Chol(A)；lu(A)是求矩阵的是求矩阵的LU分解函数分解函数乔累斯基（Cholesky）分解4.4 QR分解分解 QR分解在矩阵计算中占据相当重要的地位。利用分解在矩阵计算中占据相当重要的地位

11、。利用QR分解，分解，可以解决各种应用中（例如图像压缩处理、结构分析等）出可以解决各种应用中（例如图像压缩处理、结构分析等）出现的最小二乘问题、特征值问题等矩阵计算中的核心问题。现的最小二乘问题、特征值问题等矩阵计算中的核心问题。以以初等变换初等变换为工具的三角分解无法消除病态矩阵的不稳定为工具的三角分解无法消除病态矩阵的不稳定性，因此引入以性，因此引入以正交变换正交变换为工具的为工具的QR分解方法分解方法定理定理1(QR分解定理分解定理)设设A是是n阶阶非奇异非奇异实（复）矩阵，则存在实（复）矩阵，则存在正交（酉）矩阵正交（酉）矩阵Q与与非奇异实（复）上三角矩阵非奇异实（复）上三角矩阵R，使

12、得，使得 A=QR且除去相差一个对角元绝对值全等于且除去相差一个对角元绝对值全等于1的对角矩阵因子，分解的对角矩阵因子，分解式是唯一的。式是唯一的。矩阵的矩阵的QR分解也称为正交三角分解；分解也称为正交三角分解；若规定上三角矩阵若规定上三角矩阵R的对角元符号，则的对角元符号，则A的的QR分解唯一。分解唯一。证明：证明：先证明分解的存在性。将矩阵先证明分解的存在性。将矩阵A按列分块得到按列分块得到由于由于 ，所以，所以 是线性无关的。利用是线性无关的。利用Schmidt正交化与单位化方法，先得到一组正交向量组正交化与单位化方法，先得到一组正交向量组再单位化，这样得到一组标准正交向量组再单位化，这

13、样得到一组标准正交向量组并且向量组之间有如下关系并且向量组之间有如下关系于是有于是有为正交矩阵。为正交矩阵。证毕证毕唯一性：设唯一性：设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是是列满秩列满秩的的m n实（复）矩阵，则存在实（复）矩阵，则存在m阶正交阶正交（酉）矩阵（酉

14、）矩阵Q和和n阶非奇异实（复）上三角矩阵阶非奇异实（复）上三角矩阵R，使得，使得定理定理3 设设A是是m n矩阵矩阵，且，且rank(A)=r0,则存在则存在m阶正交阶正交（酉）矩阵（酉）矩阵Q和和r n阶行满秩矩阵阶行满秩矩阵R，使得，使得非奇异矩阵的非奇异矩阵的QR分解的推广：分解的推广：推论推论 设设A是是m n矩阵，且矩阵，且rank(A)=r0,则存在则存在m r列正交规列正交规范矩阵范矩阵Q1和和r n行满秩矩阵行满秩矩阵R，使得，使得 A=Q1R，列正交规范矩阵指的是列正交规范矩阵指的是m r矩阵矩阵Q1满足满足 。矩阵矩阵Q1是列正交规范矩阵的是列正交规范矩阵的充要条件充要条件

15、是是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

16、，对对 1，由由Householder矩阵性矩阵性质知存在质知存在Householder 矩阵矩阵H1，使得（为方便说明，不妨取负使得（为方便说明，不妨取负号）号）二、二、Householder 变换法变换法步骤：步骤：从而从而2.对对 ，当当 时时，存在存在Householder 矩阵矩阵H2，使得使得则得则得取取如果如果 ，则则 ，直接进行下一步。直接进行下一步。使得使得3.对对An-2 继续类似的变换继续类似的变换，如此最多如此最多n-1步，也即至多可以找到步，也即至多可以找到n-1个矩阵个矩阵令令Q=Hn-1H2H1，则则Q为正交矩阵，从而得到为正交矩阵，从而得到QR分解分解例2 利用

17、利用Householder变换将下列矩阵进行变换将下列矩阵进行QR分解分解对向量对向量 ，令，令解：从而得从而得Householder 矩阵矩阵使得使得 注意注意 ，即，即 被被 反射到反射到对向量对向量 ，令，令可得可得Householder 矩阵矩阵因此取因此取从而有从而有所求的所求的QR分解为分解为定义定义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 N

18、ormal Matrices theory and Normal Matrices)定理定理1（Schur定理）定理）任何一个任何一个n阶复矩阵阶复矩阵A都酉相似于一个都酉相似于一个上三角矩阵上三角矩阵，即存在一个即存在一个n阶酉矩阵阶酉矩阵U和一个和一个n阶上三角矩阶上三角矩阵阵R使得使得 UHAU=R其中其中R的对角元是的对角元是A的特征值，可以按要求的顺序排列的特征值，可以按要求的顺序排列定义定义2 设设A Cn n，若，若AHA=AAH，称，称A为为正规矩阵。正规矩阵。常见的正规矩阵：常见的正规矩阵：对角矩阵对角矩阵对角矩阵对角矩阵;对称和反对称矩阵：对称和反对称矩阵：对称和反对称矩阵

19、：对称和反对称矩阵：A AT T=A A，A AT 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。正规矩阵正规矩阵正规矩阵的性质：1.1.正规矩阵有n个线性无关的特征向量；2.正规矩阵属于不同特征值的特征向量是正交的；正规矩阵属于不同特征值的特征向量是正交的；3.与正规矩阵酉相似的矩阵都是正规矩阵。与正规矩阵酉相似的矩阵都是正

20、规矩阵。由定理由定理由定理由定理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酉相似于一个酉相似于一个酉相似于一个酉相似于一个对角阵对角阵的充要条件是的充要条件是的充要条件是的充要条件

21、是A A是是是是正正规矩阵。规矩阵。即即 i是矩阵是矩阵 A的特征值的特征值 i所对应的所对应的单位特征向量单位特征向量。设设U=(1,2,n),则由定理则由定理2知知 UHAU=diag(1,n),可得可得即即A i=i i（1,2,n）求谱分解式的步骤例例1：求正规矩阵求正规矩阵的谱分解表达式。的谱分解表达式。解：解：首先求出矩阵首先求出矩阵A 的特征值与特征向量。容易计算的特征值与特征向量。容易计算从而从而A的特征值为的特征值为 1=2=3=1,4=-3当当=1时，求得三个线性无关的特征向量为时，求得三个线性无关的特征向量为 1=1,1,0,0T 2=1,0,1,0T 3=-1,0,0,

22、1T当当=-3时，求得一个线性无关的特征向量为时，求得一个线性无关的特征向量为 4=1,-1,-1,1T将将 1,2,3正交化与单位化可得正交化与单位化可得将将4单位化可得：单位化可得：于是有于是有这样可得其谱分解表达式为这样可得其谱分解表达式为A=U UH推论推论1 设设A是是n n阶阶阶阶HermiteHermite矩阵，则矩阵，则矩阵，则矩阵，则A必酉相似于对角矩阵，必酉相似于对角矩阵，即存在一个即存在一个n阶酉矩阵阶酉矩阵U使得使得 UHAU=，其中其中=diag(1,n),i(i=1,2,n)是是A的的实特征值实特征值。该分解式该分解式称为称为Hermite矩阵矩阵A的谱分解式的谱分

23、解式。是一种通用的降维工具。在我们处理高维数据的时候，为是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后续计算的复杂度，在了能降低后续计算的复杂度，在“预处理预处理”阶段通常要先阶段通常要先对原始数据进行降维对原始数据进行降维。原则：原则：降维后的数据不能失真，也就是说，被降维后的数据不能失真，也就是说，被PCAPCA降掉的那些维降掉的那些维度只能是那些噪声或是冗余的度只能是那些噪声或是冗余的 目的就是目的就是“降噪降噪”和和“去冗余去冗余”。“降噪降噪”的目的就是使保留下来的维度间的相关性尽可能的目的就是使保留下来的维度间的相关性尽可能小，小，“去冗余去冗余”的目的就是使保留下来

24、的维度含有的的目的就是使保留下来的维度含有的“能量能量”尽可能大。尽可能大。著名的著名的PCA（Principal Component Analysis）1.形成形成样样本矩本矩阵阵S N d，假，假设设我我们们有一个有一个样样本集本集X，里面，里面有有N个个样样本，每个本，每个样样本的本的维维度度为为d。即：。即：即每行即每行为为一个一个样样本，每一列本，每一列为为一个一个维维度，得到度，得到样样本矩本矩阵阵S著名的著名的PCA（Principal Component Analysis）2.计计算算样样本矩本矩阵阵的的协协方差矩方差矩阵阵；协协方差矩方差矩阵阵度量的是度量的是维维度与度与维维

25、度之度之间间的关系，主的关系，主对对角角线线上上的元素是各个的元素是各个维维度上的方差度上的方差(即能量即能量)，其他元素是两两，其他元素是两两维维度度间间的的协协方差方差(即相关性即相关性)。著名的著名的PCA（Principal Component Analysis）3.（1）去噪）去噪对协对协方差矩方差矩阵阵S进进行行谱谱分解，去不同分解，去不同维维度的相关性（非度的相关性（非对对角元素化角元素化为为0）找到一个正交矩）找到一个正交矩阵阵P，满满足足（2）降）降维维 选选取取 中中最大的最大的p个特征个特征值对应值对应的特征向量的特征向量组组成投影矩成投影矩阵阵P1：取最大的前取最大的前

26、p(p0,称称 i为为A的的正奇异值。正奇异值。另一种定义：另一种定义：定理定理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

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

28、特征向量；（也称为对准矩的标准正交特征向量；（也称为对准矩阵）阵）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的标准正交特征向量的标准正交

29、特征向量第三步第三步：求解线性方程组求解线性方程组 的标准正交基础解系的标准正交基础解系vr+1 vm，令，令V=(v1,vr,vr+1,.vm)则则U和和V即为所求。即为所求。例 1 求下列矩阵的SVD分解：解：第一步矩阵AHA的特征值为3,1,0，对应的特征向量为标准正交化得第二步 令：计算：其中其中第三步 解 ，得其基础解系为从而因此所求因此所求SVD为为例例2：求下列矩阵的奇异值分解表达式求下列矩阵的奇异值分解表达式解解:（1）计算计算AHA的特征值分别为的特征值分别为5,0。对应的两个标准正对应的两个标准正交特征向量交特征向量由这两个标准正交特征向量组成矩阵由这两个标准正交特征向量组

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

31、量符号。SVD的几何意义的几何意义:圆圆S经过变换经过变换A，变成椭圆，变成椭圆AS。圆的正交方向。圆的正交方向u1,u2 变成椭变成椭圆的长、短轴方向圆的长、短轴方向 ,。设矩阵设矩阵A的奇异值分解为的奇异值分解为A=V UT，考虑考虑A对应的线性变换对应的线性变换Au1u2 1v1 2v2 2u2 1u1SAS 1v1 2v2 从变换的角度理解从变换的角度理解SVD，酉变换，酉变换U保持球面不变，对角矩阵保持球面不变，对角矩阵 将球面拉伸到一个有标准基的椭圆将球面拉伸到一个有标准基的椭圆(1，2是是A的两个奇异值，的两个奇异值，对应椭圆的长半轴和短半轴对应椭圆的长半轴和短半轴)，最后酉变换

32、最后酉变换V旋转或镜射这个椭旋转或镜射这个椭圆，但不改变它的形状。圆，但不改变它的形状。矩阵奇异值分解的特点：矩阵奇异值分解的特点：1.数据压缩：矩阵数据压缩：矩阵Am n的奇异值分解为：的奇异值分解为：A=V UT，其展开式：其展开式：A有有nm个数据个数据，分解后为分解后为(m+n+1)r个数据个数据，若若A的秩的秩r远远小远远小于于m和和n,则通过奇异值分解可以大大降低则通过奇异值分解可以大大降低A的维数的维数,可以达到降可以达到降维的目的维的目的,同时可以降低计算机对存贮器的要求，常用于图像同时可以降低计算机对存贮器的要求，常用于图像压缩压缩。奇异值的减少特别的快，在很多情况下，前奇异

33、值的减少特别的快，在很多情况下，前10%甚至甚至1%的的奇异值的和就占了全部的奇异值之和的奇异值的和就占了全部的奇异值之和的99%以上了。也就是以上了。也就是说，我们也可以用前说，我们也可以用前k个大的奇异值来近似描述矩阵。个大的奇异值来近似描述矩阵。图像图像的数字化技术与矩阵的奇异值分解的数字化技术与矩阵的奇异值分解 v计算机处理图像技术的第一步是图像的数字化存储技术，即计算机处理图像技术的第一步是图像的数字化存储技术，即将图像转换成矩阵来存储。将图像转换成矩阵来存储。v转换的原理是将图形分解成象素（转换的原理是将图形分解成象素（pixels）的一个矩形的数阵，）的一个矩形的数阵，其中的信息

34、就可以用一个矩阵其中的信息就可以用一个矩阵A=(aij)mn来存储。矩阵来存储。矩阵A的元的元素素aij 是一个正的数，它相应于象素的灰度水平（是一个正的数，它相应于象素的灰度水平（gray level）的度量值。的度量值。v由于一般来讲，相邻的象素会产生相近的灰度水平值，因此由于一般来讲，相邻的象素会产生相近的灰度水平值，因此有可能在满足图像清晰度要求的条件下，将存储一个有可能在满足图像清晰度要求的条件下，将存储一个mn阶阶矩阵需要存储的矩阵需要存储的mn个数减少到个数减少到n+m+1的一个倍数的一个倍数。v压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的逼近。如果图象的数

35、字矩阵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%。矩阵奇异值分解的特点：矩阵奇异值

36、分解的特点：2.奇异值对矩阵的扰动不敏感奇异值对矩阵的扰动不敏感,而特征值对矩阵的扰动敏感而特征值对矩阵的扰动敏感。3.奇异值的比例不变性。即奇异值的比例不变性。即kA的奇异值是的奇异值是A的奇异值的的奇异值的|k|倍倍。4.奇异值的旋转不变性。即若奇异值的旋转不变性。即若P是正交阵是正交阵,PA的奇异值与的奇异值与A的奇异的奇异值相同。值相同。奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放大、缩小等几何变化方面有很好的应用。平移、放大、缩小等几何变化方面有很好的应用。5.容易得到矩阵容易得到矩阵A的秩为的秩为k(kr)（低秩）

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

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

39、=500,000500,000。第。第 i 行第行第 j 列的元素，是字典列的元素，是字典中第中第 j 个词在第个词在第 i 篇文章中出现的加权词频（这个矩阵一般篇文章中出现的加权词频（这个矩阵一般称为关联矩阵）。这个矩阵非常大，有一百万乘以五十万，称为关联矩阵）。这个矩阵非常大，有一百万乘以五十万，即五千亿个元素。即五千亿个元素。奇异值分解就是把上面这样一个大矩阵，分解成三个小矩奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，比如把矩阵分解成一个一百万乘以一百的矩阵阵相乘，比如把矩阵分解成一个一百万乘以一百的矩阵V，一个一百乘以一百的一个一百乘以一百的 矩阵矩阵，和一个一百乘以五十

40、万的矩，和一个一百乘以五十万的矩阵阵U。这三个矩阵的元素总数加起来也不过。这三个矩阵的元素总数加起来也不过1.51.5亿，仅仅是亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数原来的三千分之一。相应的存储量和计算量都会小三个数量级以量级以 上。上。Am nV UT=m rr rr n三三 个矩阵有非常清楚的含义：第一个矩阵个矩阵有非常清楚的含义：第一个矩阵V中的每一行表中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越每个词的重要性（或者说相关性），数值越大越 相关。最相关。最后

41、一个矩阵后一个矩阵U中的每一列表示同一主题一类文章，其中每个中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章类之间的相关性。因此，示类词和文章类之间的相关性。因此，我们只要对关联矩我们只要对关联矩阵阵A进行一次奇异值分解，进行一次奇异值分解，我们就可以同时完成了近义词我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关分类和文章的分类。（同时得到每类文章和每类词的相关性）性）这是一个矩阵，这里的一行表示一个词在哪些title中出现了,一列表示一个title中哪些词。例

42、：SVD的结果左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性，中间的奇异值矩阵表示左奇异向量的一行与右奇异向量的一列的重要程度，数字越大越重要将左奇异向量和右奇异向量都取后2维（之前是3维的矩阵），投影到一个平面上，可以得到图上，每一个红色的点，都表示一个词，每一个蓝色的点，都表示一篇文档，这样我们可以对这些词和文档进行聚类，比如说stock 和 market可以放在一类，因为他们老是出现在一起，real和estate可以放在一类，dads，guide这种词就看起来有点孤立了，我们就不对他们进行合并了。按这样聚类出现的效果，可以提取文档集合中的近义词，这样当用户检索文档的时候，是用语义级别（近义词集合）去检索了，而不是之前的词的级别。P143:10(1);12(1);24(1)作业: