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

第4章矩阵的因子分解 MatrixFactorizationandDecomposition 教学要求掌握矩阵的满秩分解 掌握矩阵的三角分解 掌握矩阵的正交分解 掌握Schur定理和正规矩阵的定义 熟练掌握矩阵的奇异值分解 数据集中可能包含大量特征 维灾难使得数据分析很困难 1 维归约 降维 利用旧属性的线性组合得到新属性 使得新属性相互正交 捕获到数据的最大变差 PCA 主成分分析 principlecomponentsanalysis 和SVD 2 选择特征子集 嵌入 决策树分类其 过滤和包装 搜索 特征加权等 矩阵的各种分解在矩阵计算中也扮演相当重要的角色 由于变换即矩阵 所以各种分解从根本上看是各种变换 其目的是将矩阵变换成特殊的矩阵 4 2矩阵的满秩分解满秩分解定理 设为任意矩阵 则存在使得A BC 其中B为列满秩矩阵 C为行满秩矩阵 任一非 行或列 满秩的非零矩阵可表示为一列满秩矩阵和一行满秩矩阵的积 B的列可取为A的列的任一极大线性无关组 C可取为其行为A的行所生成的空间的基 然后用定理确定矩阵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 且ajj 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 2 n的一个排列 P是排列阵的充要条件是P为一系列形如P i j 的初等交换矩阵的乘积 排列阵的性质 1 P是排列阵 则PT和P 1也是排列阵 且PT P 12 P1 P2是排列阵 则P1P2是排列阵3 即 用排列阵左乘矩阵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 4QR分解 QR分解在矩阵计算中占据相当重要的地位 利用QR分解 可以解决各种应用中 例如图像压缩处理 结构分析等 出现的最小二乘问题 特征值问题等矩阵计算中的核心问题 以初等变换为工具的三角分解无法消除病态矩阵的不稳定性 因此引入以正交变换为工具的QR分解方法 定理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 r 0 则存在m阶正交 酉 矩阵Q和r n阶行满秩矩阵R 使得 非奇异矩阵的QR分解的推广 推论设A是m n矩阵 且rank A r 0 则存在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 1 H2H1 则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 5Schur定理和正规矩阵 SchurtheoryandNormalMatrices 定理1 Schur定理 任何一个n阶复矩阵A都酉相似于一个上三角矩阵 即存在一个n阶酉矩阵U和一个n阶上三角矩阵R使得UHAU R其中R的对角元是A的特征值 可以按要求的顺序排列 定义2设A Cn n 若AHA AAH 称A为正规矩阵 常见的正规矩阵 对角矩阵 对称和反对称矩阵 AT A AT A Hermite矩阵和反Hermite矩阵 AH A AH A正交矩阵和酉矩阵 ATA AAT I AHA AAH I 正规矩阵 正规矩阵的性质 1 正规矩阵有n个线性无关的特征向量 2 正规矩阵属于不同特征值的特征向量是正交的 3 与正规矩阵酉相似的矩阵都是正规矩阵 由定理2若A是n阶正规矩阵 则A酉相似于一个对角阵 即存在一个n阶酉矩阵U使得UHAU 其中 diag 1 n i i 1 2 n 是A的特征值 该式称为正规矩阵的谱分解式 正规是酉相似的不变性质 定理2n阶矩阵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 0 T 2 1 0 1 0 T 3 1 0 0 1 T 当 3时 求得一个线性无关的特征向量为 4 1 1 1 1 T将 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的谱分解式 是一种通用的降维工具 在我们处理高维数据的时候 为了能降低后续计算的复杂度 在 预处理 阶段通常要先对原始数据进行降维 原则 降维后的数据不能失真 也就是说 被PCA降掉的那些维度只能是那些噪声或是冗余的目的就是 降噪 和 去冗余 降噪 的目的就是使保留下来的维度间的相关性尽可能小 去冗余 的目的就是使保留下来的维度含有的 能量 尽可能大 著名的PCA PrincipalComponentAnalysis 形成样本矩阵SN d 假设我们有一个样本集X 里面有N个样本 每个样本的维度为d 即 即每行为一个样本 每一列为一个维度 得到样本矩阵S 著名的PCA PrincipalComponentAnalysis 2 计算样本矩阵的协方差矩阵 协方差矩阵度量的是维度与维度之间的关系 主对角线上的元素是各个维度上的方差 即能量 其他元素是两两维度间的协方差 即相关性 著名的PCA PrincipalComponentAnalysis 3 1 去噪对协方差矩阵S进行谱分解 去不同维度的相关性 非对角元素化为0 找到一个正交矩阵P 满足 2 降维选取 中最大的p个特征值对应的特征向量组成投影矩阵P1 取最大的前p p d 个特征值对应的维度 对应的p个特征向量组成了新的特征向量矩阵P1 该P1就是投影矩阵 著名的PCA PrincipalComponentAnalysis 4 对原始样本矩阵S进行投影 得到降维后的新样本矩阵S1 即S1 SP1 理由 假设PCA降维后的样本矩阵为S1 显然 根据PCA的目的 S1中的各个维度间的协方差基本为零 也就是说S1的协方差矩阵应该为对角矩阵 即满足 著名的PCA PrincipalComponentAnalysis 由 3 著名的PCA PrincipalComponentAnalysis 由于样本矩阵的每一行是一个样本 特征向量矩阵的每一列是一个特征向量 右乘相当于以每个样本的特征向量为基进行线性变换 得到的新样本矩阵中每个样本的维数变为了p 完成了降维操作 实际上 P1中的特征向量就是低维空间新的坐标系 称之为 主成分 这就是 主成分分析 的名称由来 从Beltrami 1873 和Jordan 1874 提出奇异值分解 SVD SingularValueDecomposition 至今 SVD已经成为矩阵计算中最有用和最有效的工具之一 由于奇异值良好的数学特征 奇异值分解不仅仅应用在主成分分析 图像压缩 数字水印和文章分类中 而且在信号分解 信号重构 信号降躁 数据融合 目标识别 目标跟踪 故障检测和神经网络等方面有很好的应用 4 6奇异值分解 SVD SingularValueDecomposition 引理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 0 A 0 定义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的特征向量 所以有 设A Cm n rank A r 设AHA的特征值 1 2 r 0 r 1 r 2 n 0 称为矩阵A的奇异值 若 i 0 称 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 Cm n 秩 A r 则存在m阶酉矩阵V和n阶酉矩阵U使得其中 diag 1 r 且 1 r 0 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对应的线性变换A u1 u2 1v1 2v2 AS 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个大的奇异值来近似描述矩阵 图像的数字化技术与矩阵的奇异值分解 计算机处理图像技术的第一步是图像的数字化存储技术 即将图像转换成矩阵来存储 转换的原理是将图形分解成象素 pixels 的一个矩形的数阵 其中的信息就可以用一个矩阵A aij m n来存储 矩阵A的元素aij是一个正的数 它相应于象素的灰度水平 graylevel 的度量值 由于一般来讲 相邻的象素会产生相近的灰度水平值 因此有可能在满足图像清晰度要求的条件下 将存储一个m n阶矩阵需要存储的m n个数减少到n m 1的一个倍数 压缩数字化图形存储量的方法主要是应用矩阵的奇异值分解和矩阵范数下的逼近 如果图象的数字矩阵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 矩阵奇异值分解的特点 2 奇异值对矩阵的扰动不敏感 而特征值对矩阵的扰动敏感 3 奇异值的比例不变性 即kA的奇异值是A的奇异值的 k 倍 4 奇异值的旋转不变性 即若P是正交阵 PA的奇异值与A的奇异值相同 奇异值的比例和旋转不变性特征在数字图像的旋转 镜像 平移 放大 缩小等几何变化方面有很好的应用 5 容易得到矩阵A的秩为k k r 低秩 的一个最佳逼近矩阵 奇异值的这个特征可以应用于信号的分解和重构 提取有用信息 消除信号噪声等6 若A B都有相同的奇异向量 则 A B 2 即 我们可以通过控制奇异值的大小来控制两个矩阵空间的距离 存储矩阵Ak只需要存储k个奇异值 k个m维向量ui和n维向量vj的所有分量 共计k m n 1 个元素 如果m n 1000 存储原矩阵A需要存储1000 1000个元素 取k 100时 图象已经非常清晰了 这时的存储量是100 2000 1 200100个数 和矩阵A比较 存储量减少了80 SVD用于文本分类 用一个大矩阵A来描述一百万篇文章和五十万词的关联性