矩阵的因子分解

矩阵的因子分解第1页，课件共100页，创作于2023年2月

数据集中可能包含大量特征，维灾难使得数据分析很困难，1.维归约（降维）：利用旧属性的线性组合得到新属性，使得新属性相互正交，捕获到数据的最大变差（PCA：主成分分析(principlecomponentsanalysis)和SVD）2.选择特征子集：嵌入（决策树分类其），过滤和包装（搜索，特征加权等））第2页，课件共100页，创作于2023年2月

矩阵的各种分解在矩阵计算中也扮演相当重要的角色。由于变换即矩阵，所以各种分解从根本上看是各种变换，其目的是将矩阵变换成特殊的矩阵。第3页，课件共100页，创作于2023年2月

§4.2

矩阵的满秩分解满秩分解定理：设为任意矩阵，则存在使得

A=BC,其中B为列满秩矩阵,C为行满秩矩阵.任一非（行或列）满秩的非零矩阵可表示为一列满秩矩阵和一行满秩矩阵的积；B的列可取为A的列的任一极大线性无关组；C可取为其行为A的行所生成的空间的基,然后用定理确定矩阵B。应用于极小最小二乘解和极小范数最小二乘解的算法中。第4页，课件共100页，创作于2023年2月例1

求下面矩阵的满秩分解解

思路：对矩阵A实施初等行变换得简化阶梯形矩阵H（阶梯型的非零行的第一个非零元为1，其所在的列其它元素为0）,取A的r个使H阵满秩的列为B，将H全为零的行去掉后即可构成行满秩矩阵C。第5页，课件共100页，创作于2023年2月由此可知rank(A)=2，且该矩阵第一列、第三列是线性无关的。选取第6页，课件共100页，创作于2023年2月同样，我们也可以选取

由上述例子可以看出矩阵的满秩分解形式并不唯一。但是不同的分解形式之间有如下联系：注：如果均为矩阵A

的满秩分解，那么存在矩阵满足第7页，课件共100页，创作于2023年2月则称其为A的LU

分解或三角分解。§4.3

矩阵的三角分解定义1

如果方阵A可以分解成一个单位下三角矩阵L与一个上三角矩阵U的乘积第8页，课件共100页，创作于2023年2月初等下三角矩阵第9页，课件共100页，创作于2023年2月初等下三角矩阵性质(1)det(Li)=1,第10页，课件共100页，创作于2023年2月(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第11页，课件共100页，创作于2023年2月(4)第12页，课件共100页，创作于2023年2月定理1

(LU分解定理)设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵L（主对角线上元素全为1的下三角矩阵）与唯一的上三角矩阵U

，使得的充要条件是A的所有顺序主子式均非零，即矩阵的LU分解也称为Doolitte分解若L为下三角矩阵,U为单位上三角矩阵,称为Crout分解。第13页，课件共100页，创作于2023年2月定理2

(LDU分解定理)设A是n阶非奇异矩阵，则存在唯一的单位下三角矩阵L，对角矩阵D=diag(d1,d2,…dn)和单位上三角矩阵U

，使得

A=LDU的充要条件是A的所有顺序主子式均非零，即第14页，课件共100页，创作于2023年2月矩阵的LU分解方法

矩阵的LU分解方法有很多种，这里主要介绍初等行变换消元法步骤：

1.通过初等行变换将A化为上三角矩阵U：（A，I）

（U，L1）

2.取L=：因为L1是一系列初等下三角矩阵乘积（对应初等行变换），所以L是单位下三角矩阵。第15页，课件共100页，创作于2023年2月例

1

求下列矩阵的LU分解：第16页，课件共100页，创作于2023年2月解：从而得这里第17页，课件共100页，创作于2023年2月因为所以第18页，课件共100页，创作于2023年2月1.即使矩阵A非奇异，如果A不满足前n-1个顺序主子式非零，未必能做LU分解，2.适当改变非奇异矩阵的行的次序，可使改变后的矩阵做LU分解，引入排列阵的概念说明第19页，课件共100页，创作于2023年2月定义1设e1,e2,…,en是n阶单位矩阵I的n个列向量，矩阵P=(ei1,ei2,,…,ein)称为一个n阶排列阵，其中i1,i2,…,in是1,2…n的一个排列.P是排列阵的充要条件是P为一系列形如P(i,j)的初等交换矩阵的乘积.第20页，课件共100页，创作于2023年2月排列阵的性质：1.P是排列阵，则PT和P-1也是排列阵，且PT=P-12.P1，P2是排列阵，则P1P2是排列阵3.即：用排列阵左乘矩阵A相当于将A的行按照排列阵的次序重排，右乘对A的列按排列阵的次序重排。第21页，课件共100页，创作于2023年2月引理1

设A是n阶非奇异矩阵，则存在排列阵P，使得PA的所有顺序主子式要条件均非零。定理3

设A是n阶非奇异矩阵，则存在排列阵P，使得PA=LDU所其中L是单位下三角矩阵，U是单位上三角矩阵，D是对角矩阵。第22页，课件共100页，创作于2023年2月三角方程组易于求解矩阵LU分解的一个应用——解线性方程组第23页，课件共100页，创作于2023年2月定理

设矩阵A对称正定，则存在唯一的对角元为正的下三角阵L，使得

称为对称正定矩阵A的乔累斯基分解

利用乔累斯基（Cholesky）分解式来求解Ax=b的方法也称Cholesky方法或平方根法

MATLAB函数：Chol(A)；lu(A)是求矩阵的LU分解函数乔累斯基（Cholesky）分解第24页，课件共100页，创作于2023年2月§4.4

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

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

设A是列满秩的m

n实（复）矩阵，则存在m阶正交（酉）矩阵Q和n阶非奇异实（复）上三角矩阵R，使得定理3

设A是m

n矩阵，且rank(A)=r>0,则存在m阶正交（酉）矩阵Q和r

n阶行满秩矩阵R，使得非奇异矩阵的QR分解的推广：第31页，课件共100页，创作于2023年2月推论

设A是m

n矩阵，且rank(A)=r>0,则存在m

r列正交规范矩阵Q1和r

n行满秩矩阵R，使得A=Q1R，列正交规范矩阵指的是m

r矩阵Q1满足。矩阵Q1是列正交规范矩阵的充要条件是Q1的列向量组是标准正交向量组第32页，课件共100页，创作于2023年2月一、Schmidt方法步骤：1.将矩阵A的列向量

1，

2

，…

n施以Schmidt标准正交化,得到

1，

2

，…

n

标准正交组：2.取Q=(

1，

2

，…

n)，则Q为正交矩阵

3.取R=QTA矩阵的QR分解方法第33页，课件共100页，创作于2023年2月例1

利用Schmidt方法将下列矩阵进行QR分解：第34页，课件共100页，创作于2023年2月解

先将A=[

1，

2

，

3]的三个列向量正交化与单位化：第35页，课件共100页，创作于2023年2月所以A的QR分解为：A=QR第36页，课件共100页，创作于2023年2月从而1.取A的列向量

1，

2

，…

n，对

1，由Householder矩阵性质知存在Householder矩阵H1，使得（为方便说明，不妨取负号）二、Householder

变换法步骤：第37页，课件共100页，创作于2023年2月从而2.对，当

时，存在Householder

矩阵H2，使得第38页，课件共100页，创作于2023年2月则得取如果，则，直接进行下一步。第39页，课件共100页，创作于2023年2月使得3.对An-2继续类似的变换，如此最多n-1步，也即至多可以找到n-1个矩阵令Q=Hn-1…H2H1，则Q为正交矩阵，从而得到QR分解第40页，课件共100页，创作于2023年2月例2

利用Householder变换将下列矩阵进行QR分解第41页，课件共100页，创作于2023年2月对向量，令解：从而得Householder

矩阵第42页，课件共100页，创作于2023年2月使得

注意

，即被反射到对向量，令可得Householder

矩阵第43页，课件共100页，创作于2023年2月因此取从而有第44页，课件共100页，创作于2023年2月所求的QR分解为第45页，课件共100页，创作于2023年2月定义1

设A，B

Rn

n(Cn

n),若存在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的特征值，可以按要求的顺序排列第46页，课件共100页，创作于2023年2月定义2

设A

Cn

n，若AHA=AAH，称A为正规矩阵。常见的正规矩阵：对角矩阵;对称和反对称矩阵：AT=A，AT=–A。Hermite矩阵和反Hermite矩阵：AH=A，AH=–A正交矩阵和酉矩阵：ATA=AAT=I，AHA=AAH=I。正规矩阵第47页，课件共100页，创作于2023年2月正规矩阵的性质：1.正规矩阵有n个线性无关的特征向量；2.正规矩阵属于不同特征值的特征向量是正交的；3.与正规矩阵酉相似的矩阵都是正规矩阵。第48页，课件共100页，创作于2023年2月由定理2若A是n阶正规矩阵，则A酉相似于一个对角阵，即存在一个n阶酉矩阵U使得

UHAU=，其中=diag(1,…,

n),

i(i=1,2,…n)是A的特征值。该式称为正规矩阵的谱分解式.正规是酉相似的不变性质定理2

n阶矩阵A酉相似于一个对角阵的充要条件是A是正规矩阵。第49页，课件共100页，创作于2023年2月即

i是矩阵A的特征值

i所对应的单位特征向量。设U=(

1,

2,…,

n),则由定理2知UHAU==diag(1,…,

n),可得即A

i=

i

i（1,2,…n）求谱分解式的步骤第50页，课件共100页，创作于2023年2月例1：求正规矩阵的谱分解表达式。解：首先求出矩阵A

的特征值与特征向量。容易计算第51页，课件共100页，创作于2023年2月从而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第52页，课件共100页，创作于2023年2月当λ=-3时，求得一个线性无关的特征向量为

α4=[1,-1,-1,1]T将α1,α2,α3正交化与单位化可得第53页，课件共100页，创作于2023年2月将α4单位化可得：于是有这样可得其谱分解表达式为A=U

UH第54页，课件共100页，创作于2023年2月推论1

设A是n阶Hermite矩阵，则A必酉相似于对角矩阵，即存在一个n阶酉矩阵U使得

UHAU=，其中=diag(1,…,

n),

i(i=1,2,…n)是A的实特征值。该分解式称为Hermite矩阵A的谱分解式。第55页，课件共100页，创作于2023年2月是一种通用的降维工具。在我们处理高维数据的时候，为了能降低后续计算的复杂度，在“预处理”阶段通常要先对原始数据进行降维。原则：降维后的数据不能失真，也就是说，被PCA降掉的那些维度只能是那些噪声或是冗余的目的就是“降噪”和“去冗余”。“降噪”的目的就是使保留下来的维度间的相关性尽可能小，“去冗余”的目的就是使保留下来的维度含有的“能量”尽可能大。著名的PCA（PrincipalComponentAnalysis）第56页，课件共100页，创作于2023年2月形成样本矩阵S

N

d，假设我们有一个样本集X，里面有N个样本，每个样本的维度为d。即：即每行为一个样本，每一列为一个维度，得到样本矩阵S著名的PCA（PrincipalComponentAnalysis）第57页，课件共100页，创作于2023年2月2.计算样本矩阵的协方差矩阵；协方差矩阵度量的是维度与维度之间的关系，主对角线上的元素是各个维度上的方差(即能量)，其他元素是两两维度间的协方差(即相关性)。著名的PCA（PrincipalComponentAnalysis）第58页，课件共100页，创作于2023年2月3.（1）去噪对协方差矩阵S进行谱分解，去不同维度的相关性（非对角元素化为0）找到一个正交矩阵P，满足（2）降维

选取中最大的p个特征值对应的特征向量组成投影矩阵P1：取最大的前p(p<d)个特征值对应的维度，对应的p个特征向量组成了新的特征向量矩阵P1，该P1就是投影矩阵。著名的PCA（PrincipalComponentAnalysis）第59页，课件共100页，创作于2023年2月4.对原始样本矩阵S进行投影，得到降维后的新样本矩阵S1：即S1=SP1；理由：假设PCA降维后的样本矩阵为S1，显然，根据PCA的目的，S1中的各个维度间的协方差基本为零，也就是说S1的协方差矩阵应该为对角矩阵。即满足：著名的PCA（PrincipalComponentAnalysis）由（3）第60页，课件共100页，创作于2023年2月著名的PCA（PrincipalComponentAnalysis）由于样本矩阵的每一行是一个样本，特征向量矩阵的每一列是一个特征向量。右乘相当于以每个样本的特征向量为基进行线性变换，得到的新样本矩阵中每个样本的维数变为了p，完成了降维操作。实际上，P1中的特征向量就是低维空间新的坐标系，称之为“主成分”。这就是“主成分分析”的名称由来。第61页，课件共100页，创作于2023年2月

从Beltrami（1873）和Jordan（1874）提出奇异值分解（SVD：SingularValueDecomposition）至今，SVD已经成为矩阵计算中最有用和最有效的工具之一，由于奇异值良好的数学特征,奇异值分解不仅仅应用在主成分分析、图像压缩、数字水印和文章分类中,而且在信号分解、信号重构、信号降躁、数据融合、目标识别、目标跟踪、故障检测和神经网络等方面有很好的应用。§4.6奇异值分解(SVD)

（Singular

Value

Decomposition）第62页，课件共100页，创作于2023年2月引理1

设A

Cm×n，则AHA

Cn×n，AAH

Cm×m

，且（1）Rank(AHA)=Rank(AAH)=Rank(A)（2）AHA与AAH的特征值均为非负实数；（3）AHA与AAH的非零特征值相同，并且非零特征值的个数（重特征值按重数计算）等于rank（A）；（4）AHA=0A=0第63页，课件共100页，创作于2023年2月定义1

设A

Cm×n，若存在非负实数

和非零向量u

Cn，

v

Cm，使得

Au=

v,AHv=

u

（*）称

为矩阵A的奇异值。相应地，u和v分别称为A对应于奇异值

的右奇异向量和左奇异向量。说明：由（*）式得(AHA)u=

AHv=

2u

，(AAH)v=

Au=

2v

所以

2是AHA的特征值也是AAH的特征值,而u和v分别是对应于

2的特征向量。所以有第64页，课件共100页，创作于2023年2月设A

Cm×n，rank(A)=r，设AHA的特征值1

2

r0，

r+1=r+2==n=0，称为矩阵A的奇异值。若i>0,称i为A的正奇异值。另一种定义：第65页，课件共100页，创作于2023年2月定理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页，创作于2023年2月定理2

（奇异值分解定理）设A

Cm×n，秩（A）=r，则存在m阶酉矩阵V和n阶酉矩阵U使得

其中

=diag(

1,…,

r),且

1

r>0.第67页，课件共100页，创作于2023年2月1.U的列向量是AHA的标准正交特征向量；（也称为悬挂矩阵）2.U的前r列向量是AHA对应于r个非零特征值12，

r2的标准正交特征向量；3.V的列向量是AAH的标准正交特征向量；（也称为对准矩阵）4.V的前r列向量是AHA对应于特征值12，

r2的标准正交特征向量；注记：第68页，课件共100页，创作于2023年2月第二步：令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的标准正交特征向量第69页，课件共100页，创作于2023年2月第三步：求解线性方程组的标准正交基础解系vr+1…vm，令V=(v1,…vr,vr+1,...vm)则U和V即为所求。第70页，课件共100页，创作于2023年2月例1

求下列矩阵的SVD分解：解：第一步第71页，课件共100页，创作于2023年2月矩阵AHA的特征值为3,1,0，对应的特征向量为标准正交化得第72页，课件共100页，创作于2023年2月第二步令：计算：其中第73页，课件共100页，创作于2023年2月第三步解，得其基础解系为从而第74页，课件共100页，创作于2023年2月因此所求SVD为第75页，课件共100页，创作于2023年2月例2：求下列矩阵的奇异值分解表达式第76页，课件共100页，创作于2023年2月解:（1）计算AHA的特征值分别为5,0。对应的两个标准正交特征向量由这两个标准正交特征向量组成矩阵U第77页，课件共100页，创作于2023年2月（2）计算AAH

的特征值为5，0，0，所以A的奇异值为。下面计算AAH的标准正交特征向量，解得分别与5，0，0对应的三个标准正交特征向量由这三个标准正交特征向量组成矩阵V，所以有第78页，课件共100页，创作于2023年2月于是可得奇异值分解式为第79页，课件共100页，创作于2023年2月注：使用第二种方法时选取的U和V不唯一，他们的对应列之间相差一个符号，因此当分解式不成立时，需要调整相应的特征向量符号。第80页，课件共100页，创作于2023年2月SVD的几何意义:

圆S经过变换A，变成椭圆AS。圆的正交方向u1,u2变成椭圆的长、短轴方向,。设矩阵A的奇异值分解为A=V

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

1v1

2v2

2u2

1u1SAS

1v1

2v2第81页，课件共100页，创作于2023年2月

从变换的角度理解SVD，酉变换U保持球面不变，对角矩阵

将球面拉伸到一个有标准基的椭圆(

1，2是A的两个奇异值，对应椭圆的长半轴和短半轴)，最后酉变换V旋转或镜射这个椭圆，但不改变它的形状。第82页，课件共100页，创作于2023年2月矩阵奇异值分解的特点：1.

数据压缩：矩阵Am

n的奇异值分解为：A=VUT，其展开式：A有nm个数据，分解后为(m+n+1)r个数据，若A的秩r远远小于m和n,则通过奇异值分解可以大大降低A的维数,可以达到降维的目的,同时可以降低计算机对存贮器的要求，常用于图像压缩。奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前k个大的奇异值来近似描述矩阵。第83页，课件共100页，创作于2023年2月图像的数字化技术与矩阵的奇异值分解

计算机处理图像技术的第一步是图像的数字化存储技术，即将图像转换成矩阵来存储。转换的原理是将图形分解成象素（pixels）的一个矩形的数阵，其中的信息就可以用一个矩阵A=(aij)m×n来存储。矩阵A的元素aij是一个正的数，它相应于象素的灰度水平（graylevel）的度量值。由于一般来讲，相邻的象素会产生相近的灰度水平值，因此有可能在满足图像清晰度要求的条件下，将存储一个m×n阶矩阵需要存储的m×n个数减少到n+m+1的一个倍数。第84页，课件共100页，创作于2023年2月压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的逼近。如果图象的数字矩阵A的奇异值分解为：A=U

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

r)的矩阵Ak来逼近矩阵A。Ak按如下方法选取：这是矩阵A的秩1分解式。第85页，课件共100页，创作于2023年2月在秩为k(k

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

=(m+n+1)/mn;经典的方法是选取接近k，使Ak的存储量比A的存储量减少20%。第86页，课件共100页，创作于2023年2月第87页，课件共100页，创作于2023年2月第88页，课件共100页，创作于2023年2月第89页，课件共100页，创作于2023年2月第90页，课件共100页，创作于2023年2月矩阵奇异值分解的特点：2.奇异值对矩阵的扰动不敏感,而特征值对矩阵的扰动敏感。3.奇异值的比例不变性。即kA的奇异值是A的奇异值的|k|倍。4.奇异值的旋转不变性。即若P是正交阵,PA的奇异值与A的奇异值相同。奇异值的比例和旋转不变性特征在数字图像的旋转、镜像、平移、放大、缩小等几何变化方面有很好的应用。第91页，课件共100页，创作于2023年2月5.容易得到矩阵A的秩为k(k≤r)（低秩）的一个最佳逼近矩阵。奇异值的这个特征可以应用于信号的分解和重构,提取有用信息,消除信号噪声等6.若A、B都有相同的奇异向量,则||A–B||2=,

即,