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

第第4 4章章 矩阵的因子分解矩阵的因子分解（Matrix Factorization and DecompositionMatrix Factorization and Decomposition）教学要求教学要求驾驭矩阵的满秩分解；驾驭矩阵的满秩分解；驾驭矩阵的三角分解；驾驭矩阵的三角分解；驾驭矩阵的正交分解；驾驭矩阵的正交分解；驾驭驾驭SchurSchur定理和正规则阵的定义；定理和正规则阵的定义；娴熟驾驭矩阵的奇异值分解；娴熟驾驭矩阵的奇异值分解；数据集中可能包含大量特征，维灾难使得数据数据集中可能包含大量特征，维灾难使得数据分析很困难，分析很困难，1.1.维归约（降维）：利用旧属性的线性组合得到维归约（降维）：利用旧属性的线性组合得到新属性，使得新属性相互正交，捕获到数据的最新属性，使得新属性相互正交，捕获到数据的最大变差（大变差（PCAPCA：主成分分析：主成分分析(principle(principle components analysis)components analysis)和和SVDSVD）2.2.选择特征子集：嵌入（决策树分类其），过滤选择特征子集：嵌入（决策树分类其），过滤和包装（搜寻，特征加权等）和包装（搜寻，特征加权等）矩阵的各种分解在矩阵计算中也扮演相当重要矩阵的各种分解在矩阵计算中也扮演相当重要的角色。由于变换即矩阵，所以各种分解从根本的角色。由于变换即矩阵，所以各种分解从根本上看是各种变换，其目的是将矩阵变换成特殊的上看是各种变换，其目的是将矩阵变换成特殊的矩阵。矩阵。4.2 矩阵的满秩分解矩阵的满秩分解满秩分解定理：设满秩分解定理：设 为随意矩阵，则存在为随意矩阵，则存在 使得使得 A=BC,其中其中B为列满秩矩阵为列满秩矩阵,C为行满秩矩阵为行满秩矩阵.任一非（行或列）满秩的非零矩阵可表示为一列满秩矩任一非（行或列）满秩的非零矩阵可表示为一列满秩矩阵和一行满秩矩阵的积；阵和一行满秩矩阵的积；B B的列可取为的列可取为A A的列的任一极大线性无关组；的列的任一极大线性无关组；C C可取为其行为可取为其行为A A的行所生成的空间的基的行所生成的空间的基,然后用定理确然后用定理确定矩阵定矩阵B 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,且且a jj 0，并且取，并且取 则则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 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分解，分解，可以解决各种应用中（例如图像压缩处理、结构分析等）出可以解决各种应用中（例如图像压缩处理、结构分析等）出现的最小二乘问题、特征值问题等矩阵计算中的核心问题。现的最小二乘问题、特征值问题等矩阵计算中的核心问题。以初等变换为工具的三角分解无法消退病态矩阵的不稳定以初等变换为工具的三角分解无法消退病态矩阵的不稳定性，因此引入以正交变换为工具的性，因此引入以正交变换为工具的QRQR分解方法分解方法定理定理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是是列满秩列满秩的的m n实（复）矩阵，则存在实（复）矩阵，则存在m阶正交阶正交（酉）矩阵（酉）矩阵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是列正交规范矩阵的充要条件是是列正交规范矩阵的充要条件是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，B Rn n(Cn n),若存在若存在n阶正交（酉）矩阶正交（酉）矩阵阵U使得使得 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的特征值，可以按要求的特征值，可以按要求的依次排列的依次排列定义定义2 设设ACnn，若，若AHA=AAH，称，称A为正规则阵。为正规则阵。常见的正规则阵：常见的正规则阵：对角矩阵对角矩阵;对称和反对称矩阵：对称和反对称矩阵：AT=A，AT=A。Hermite矩阵和反矩阵和反Hermite矩阵：矩阵：AH=A，AH=A正交矩阵和酉矩阵：正交矩阵和酉矩阵：ATA=AAT=I，AHA=AAH=I。正规则阵正规则阵正规则阵的性质：1.1.正规则阵有正规则阵有n 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),可得可得即即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,1T当当=-3时，求得一个线性无关的特征向量为时，求得一个线性无关的特征向量为 4=1,-1,-1,1T将将 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的谱分解式。的谱分解式。是一种通用的降维工具。在我们处理高维数据的时候，为是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后续计算的困难度，在了能降低后续计算的困难度，在“预处理预处理”阶段通常要先阶段通常要先对原始数据进行降维。对原始数据进行降维。原则：原则：降维后的数据不能失真，也就是说，被降维后的数据不能失真，也就是说，被PCAPCA降掉的那些维降掉的那些维度只能是那些噪声或是冗余的度只能是那些噪声或是冗余的 目的就是目的就是“降噪降噪”和和“去冗余去冗余”。“降噪降噪”的目的就是使保留下来的维度间的相关性尽可能的目的就是使保留下来的维度间的相关性尽可能小，小，“去冗余去冗余”的目的就是使保留下来的维度含有的的目的就是使保留下来的维度含有的“能量能量”尽可能大。尽可能大。著名的著名的PCAPCA（Principal Component AnalysisPrincipal Component Analysis）1.形成形成样样本矩本矩阵阵S N d，假，假设设我我们们有一个有一个样样本集本集X，里面，里面有有N个个样样本，每个本，每个样样本的本的维维度度为为d。即：。即：即每行即每行为为一个一个样样本，每一列本，每一列为为一个一个维维度，得到度，得到样样本矩本矩阵阵S著名的著名的PCAPCA（Principal Component AnalysisPrincipal Component Analysis）2.计计算算样样本矩本矩阵阵的的协协方差矩方差矩阵阵；协协方差矩方差矩阵阵度量的是度量的是维维度与度与维维度之度之间间的关系，主的关系，主对对角角线线上上的元素是各个的元素是各个维维度上的方差度上的方差(即能量即能量)，其他元素是两，其他元素是两两两维维度度间间的的协协方差方差(即相关性即相关性)。著名的著名的PCAPCA（Principal Component AnalysisPrincipal Component Analysis）3.3.（1 1）去噪）去噪对协方差矩阵对协方差矩阵S S进行谱分解，去不同维度的相关性（非对进行谱分解，去不同维度的相关性（非对角元素化为角元素化为0 0）找到一个正交矩阵）找到一个正交矩阵P P，满足，满足（2 2）降维）降维 选取选取 中最大的中最大的p p个特征值对应的特征向量个特征值对应的特征向量组成投影矩阵组成投影矩阵P1P1：取最大的前取最大的前p(pd)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（奇异值分解定理）（奇异值分解定理）设设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的标准正交特征向量；（也称为对准矩的标准正交特征向量；（也称为对准矩阵）阵）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.数据压缩：矩阵数据压缩：矩阵Am n的奇异值分解为：的奇异值分解为：A=V UT，其绽开式：，其绽开式：A有有nm个数据，分解后为个数据，分解后为(m+n+1)r个数据，若个数据，若A的秩的秩r远远小于远远小于m和和n,则通过奇异值分解可以大大降低则通过奇异值分解可以大大降低A的维数的维数,可以达到降可以达到降维的目的维的目的,同时可以降低计算机对存贮器的要求，常用于图像同时可以降低计算机对存贮器的要求，常用于图像压缩。压缩。奇异值的削减特殊的快，在很多状况下，前奇异值的削减特殊的快，在很多状况下，前10%甚至甚至1%的奇异的奇异值的和就占了全部的奇异值之和的值的和就占了全部的奇异值之和的99%以上了。也就是说，以上了。也就是说，我们也可以用前我们也可以用前k个大的奇异值来近似描述矩阵。个大的奇异值来近似描述矩阵。图像图像的数字化技术与矩阵的奇异值分解的数字化技术与矩阵的奇异值分解 v计算机处理图像技术的第一步是图像的数字化存储技术，即计算机处理图像技术的第一步是图像的数字化存储技术，即将图像转换成矩阵来存储。将图像转换成矩阵来存储。v转换的原理是将图形分解成象素（转换的原理是将图形分解成象素（pixels）的一个矩形的数阵，）的一个矩形的数阵，其中的信息就可以用一个矩阵其中的信息就可以用一个矩阵A=(aij)mn来存储。矩阵来存储。矩阵A的的元素元素aij 是一个正的数，它相应于象素的灰度水平（是一个正的数，它相应于象素的灰度水平（gray level）的度量值。的度量值。v由于一般来讲，相邻的象素会产生相近的灰度水平值，因此由于一般来讲，相邻的象素会产生相近的灰度水平值，因此有可能在满足图像清晰度要求的条件下，将存储一个有可能在满足图像清晰度要求的条件下，将存储一个mn阶阶矩阵须要存储的矩阵须要存储的mn个数削减到个数削减到n+m+1的一个倍数。的一个倍数。v压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的靠近。假如图象的数字矩阵A的奇异值分解为：A=UVT，其绽开式：压缩矩阵压缩矩阵A A的方法是取一个秩为的方法是取一个秩为k(kk(kr)r)的矩阵的矩阵Ak Ak 来靠近矩阵来靠近矩阵A A。AkAk按如下方法选取：按如下方法选取：这是矩阵这是矩阵A的秩的秩1分解式分解式。在在秩秩为为k(kk(kn)n)的的全全部部矩矩阵阵中中，矩矩阵阵AkAk所所对对应应的的图图象象和和矩矩阵阵A A所所对对应应的的图图象象最最相相近近。一一般般的的，k k越越大大图图象象就就越越清清晰晰。压压缩比：缩比：=(m+n+1)/mn;=(m+n+1)/mn;经经典典的的方方法法是是选选取取接接近近k k，使使AkAk的的存存储储量量比比A A的的存存储储量量削削减减20%20%。矩阵奇异值分解的特点：矩阵奇异值分解的特点：2.奇异值对矩阵的扰动不敏感奇异值对矩阵的扰动不敏感,而特征值对矩阵的扰动敏感而特征值对矩阵的扰动敏感。3.奇异值的比例不变性。即奇异值的比例不变性。即kA的奇异值是的奇异值是A的奇异值的的奇异值的|k|倍倍。4.奇异值的旋转不变性。即若奇异值的旋转不变性。即若P是正交阵是正交阵,PA的奇异值与的奇异值与A的奇异的奇异值相同。值相同。奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放大、缩小等几何变更方面有很好的应用。平移、放大、缩小等几何变更方面有很好的应用。5.简洁得到矩阵简洁得到矩阵A的秩为的秩为k(kr)（低秩）的一个最佳靠近矩（低秩）的一个最佳靠近矩阵。阵。奇异值的这个特征可以应用于信号的分解和重构奇异值的这个特征可以应用于信号的分解和重构,提取有用提取有用信息信息,消退信号噪声等消退信号噪声等6.若若A、B都有相同的奇异向量都有相同的奇异向量,则则|A B|2=,即即,我们可以通过限制奇异值的大小来限制两个矩阵空间的我们可以通过限制奇异值的大小来限制两个矩阵空间的距离。距离。v存储矩阵存储矩阵AkAk只须要存储只须要存储k k个奇异值，个奇异值，k k个个m m维向量维向量uiui和和n n维向量维向量vjvj的全部重量，共计的全部重量，共计k k（m+n+1m+n+1）个元素。）个元素。v假如假如m=n=1000m=n=1000，存储原矩阵，存储原矩阵A A须要存储须要存储1000100010001000个元个元素。取素。取k=100k=100时，图象已经特别清晰了，这时的存储量时，图象已经特别清晰了，这时的存储量是是100100（2000+12000+1）=200100=200100个数。个数。v和矩阵和矩阵A A比较，存储量削减了比较，存储量削减了80%80%。SVD用于文本分类用于文本分类 用一个大矩阵用一个大矩阵A来描述一百万篇文章和五十万词的关来描述一百万篇文章和五十万词的关联性。这个矩阵中，每一行对应一篇文联性。这个矩阵中，每一行对应一篇文 章，每一列章，每一列对应一个词。对应一个词。M=1,000,000，N=500,000。第。第 i 行第行第 j 列的元素，是字典中第列的元素，是字典中第 j 个词在第个词在第 i 篇文章中出现篇文章中出现的加权词频（这个矩阵一般称为关联矩阵）。这个的加权词频（这个矩阵一般称为关联矩阵）。这个矩阵特别大，有一百万乘以五十万，即五千亿个元矩阵特别大，有一百万乘以五十万，即五千亿个元素。素。奇异值分解就是把上面这样一个大矩阵，分解成三个小矩奇异值分解就是把上面这样一个大矩阵，分解成三个小矩阵相乘，比如把矩阵分解成一个一百万乘以一百的矩阵阵相乘，比如把矩阵分解成一个一百万乘以一百的矩阵V，一个一百乘以一百的一个一百乘以一百的 矩阵矩阵，和一个一百乘以五十万的矩，和一个一百乘以五十万的矩阵阵U。这三个矩阵的元素总数加起来也不过。这三个矩阵的元素总数加起来也不过1.51.5亿，仅仅是亿，仅仅是原来的三千分之一。相应的存储量和计算量都会小三个数原来的三千分之一。相应的存储量和计算量都会小三个数量级以量级以 上。上。Am nV UT=m rr rr n三三 个矩阵有特别清晰的含义：第一个矩阵个矩阵有特别清晰的含义：第一个矩阵V V中的每一行表中的每一行表示意思相关的一类词，其中的每个非零元素表示这类词中示意思相关的一类词，其中的每个非零元素表示这类词中每个词的重要性（或者说相关性），数值越大越每个词的重要性（或者说相关性），数值越大越 相关。最相关。最终一个矩阵终一个矩阵U U中的每一列表示同一主题一类文章，其中每个中的每一列表示同一主题一类文章，其中每个元素表示这类文章中每篇文章的相关性。中间的矩阵则表元素表示这类文章中每篇文章的相关性。中间的矩阵则表示类词和文章类之间的相关性。因此，示类词和文章类之间的相关性。因此，我们只要对关联矩我们只要对关联矩阵阵A A进行一次奇异值分解，进行一次奇异值分解，我们就可以同时完成了近义词我们就可以同时完成了近义词分类和文章的分类。（同时得到每类文章和每类词的相关分类和文章的分类。（同时得到每类文章和每类词的相关性）性）这是一个矩阵，这里的一行表示一个词在哪些title中出现了,一列表示一个title中哪些词。例：SVD的结果左奇异向量表示词的一些特性，右奇异向量表示文档的一些特性，中间的奇异值矩阵表示左奇异向量的一行与右奇异向量的一列的重要程度，数字越大越重要将左奇异向量和右奇异向量都取后2维（之前是3维的矩阵），投影到一个平面上，可以得到图上，每一个红色的点，都表示一个词，每一个蓝色的点，都表示一篇文档，这样我们可以对这些词和文档进行聚类，比如说stock 和 market可以放在一类，因为他们老是出现在一起，real和estate可以放在一类，dads，guide这种词就看起来有点孤立了，我们就不对他们进行合并了。按这样聚类出现的效果，可以提取文档集合中的近义词，这样当用户检索文档的时候，是用语义级别（近义词集合）去检索了，而不是之前的词的级别。P143:10(1);12(1);24(1)作业: