非负矩阵分解算法概述 （吴有光） NOTE：本文为科普文章，尽量做到通俗而不严格，比较适合理论小白补补NMF历史 第一部分Lee&Seung的世界 1 引言 现实生活中的数据，我们总是希望有个稀疏表达，这是从压缩或数据存储的角度希望达到的效果。从另一方面来讲，我们面对大量数据的时候，总是幻想能够发现其中的“规律”，那么在表示或处理的时候，直接操作这些提纲挈领的“规律”，会有效得多。这个事情，让很多的科学家都伤透脑筋，不过也因此有了饭碗。 1.1第一个例子 我们先来看一个简单的例子。在人文、管理或社会学里，实证研究方法是常用的方法。比如我们来考察大学生就业过程，对学生的选择工作类别的动机，我们常说“想吃劳保饭的同学铁了心要考公务员，喜欢轻松自由氛围的同学更趋向于外企，只想稳定的同学认为国企最好，富二代神马的最爱创业然后继承家产了”，这句话如果要严格来论证是不可能的，那么我们转而寻求“调查论证”，即通过设计问卷（问卷上设计了可能影响学生选择的因素，比如家庭情况、学业情况、性格取向、对大城市或家乡的热恋程度、以及人生观价值观等等各种我们可能会影响就业取向的因素）各种我们猜测会影响学生。 问卷上来后，我们通过统计得到如下的列表。 图1 第一个例子的统计表示例 表中的各个因素我们进行了量化，比如性格因素从完全内向到热情奔放分为5个等级（可以用一些问题来直接或间接获得这个等级）。那么剩下的问题就是回答开始的问题：
（1）是不是我们设计的每个因素都有效？（显然不是，之所以设计问卷就是要来解决这个问题的） （2）是什么因素影响了学生的最终选择？或者说，从统计上来看，每个因素占多大比重？ 这时，用矩阵来表示可写为，其中就表示那个因素矩阵，表示最终取向，代 表我们要求的系数。我们把要求的用代替，写成矩阵形式为： (1) 更进一步，如果我们不仅调查学生的去向，还想同时调查很多事情，那么就会有 ，这样上面的式子改写为： (2) 此时问题转化为： Q1：已知，如何求解，使之满足上面的等式，其中具有初始值（就是我们设计的 一堆东西）。 如果我们让固定，这就是一个方程求解的过程。然而，当我们认为也可以缩减，即认为很少样本就足够表示我们真实取得的样本，那么问题进一步转化为：Q2：如何同时求解和，使之满足。 或者我们也可以只对因素矩阵进行分解，即直接对其进行消减： (3) 其中，为消减后因素矩阵，为在基底下的表示系数，这里要求列数要大大低于的列数，否则就没有实际意义。 上面这个过程，就类似Paatero&T apper于1994年提出的实矩阵分解（Positive Matrix Factorization, PMF）模型，此模型后来被Lee&Seung提出的非负矩阵分解(Nonnegative Matrix Factorization, NMF/NNMF)模型所取代。 1.2 第二个例子 第一个例子为了给非数学、非信号处理的同学一个印象，写的罗里吧嗦，那第二个例子我们就简单写。 给定一组信号，如何找到对其进行稀疏表示？即如何找到满足的和，因为，这里要求且。 这个问题对信号处理的同学来说，太熟悉了。因为我们毕生的精力都在干这件事情。 如果去掉的非负限制，是有很多现成且高效的方法的，比如主成分分析（Principle Component Analysis，PCA）、独立成分分析（Independent Component Analysis，ICA）、因子分析（Factor Analysis，FA）等。然而，施加了非负限制后，这些方法就不适用了。而为什么要施加非负限制，回想第一个例子就明白了，我们最终找的是“影响因子”，因子会有负的么？ 于是，非负矩阵分解就出世了， 1.3 非负矩阵分解 非负矩阵分解（Non-negative Matrix Factorization，NMF）从1999年正式提出【1】至今，
对于图像的约束非负矩阵分解 摘要：非负矩阵分解(NMF)对于寻找非负数据的块基础和线性表示是一个常用的方法。它已经广泛的应用于各种应用，比如模式识别，信息检索，计算机视觉。但是，NMF本质上是一个非监督方法，不能利用标签信息。在本文中，我们提出一种新的半监督矩阵分解方法，叫约束非负矩阵分解(CNMF)，将标签作为附加约束合并进来。特别地，本文显示出结合标签信息能非常简洁地提高矩阵分解的识别能力。我们利用两个函数公式和提供的相应优化问题的更新解决方法来研究所提出的CNMF方法。通过实际数据的评估，我们所提出的方法和最先进的方法相比更有效。 索引词：非负矩阵分解，半监督学习，降维，聚类
1.简介 许多数据分析中一个基础的问题就是寻找一个合适的表示数据[1]，[2]，[3]，[4]，[5]，[6]，[7]，[8]。可以应用一个非常有效的方法表示数据之间的潜在结构。矩阵分解技术作为这类数据表示的基础工具已经得到越来越多的注意。运用不同的标准已经得到了大量不同的方法。最流行的技术包括主成分分析(PCA)[9]，奇异值分解(SVD)[10]，和向量量化[11]。矩阵分解的中心是找到两个或者更多的因子产生原始数据的一个好的逼近。在实际应用中，分解之后的矩阵维数通常远远小于原始数据的维数。这就引起了数据的压缩表示，促进了其他研究比如聚类和分类。 在矩阵分解方法中，非负矩阵分解(NMF)有一个限制即所有的矩阵因子都必须是非负的，即所有的因子必须大于等于零。这个非负性约束使NMF从感觉上只能对原始数据进行加操作不能减。因此，对于图像处理，人脸识别[2][12]，文件聚类[13][14]是一个理想的降维方法，它们就是由部分组成整体的。 NMF是一个非监督学习方法。NMF不能应用于许多实际的问题当专家认为是可行的有限知识中。但是许多机器语言的研究发现未标签的数据当与一些少量的标签数据相结合时在研究精确度上会产生相当大的提高[15][16][17]。全标签训练集的处理过程可能会很昂贵，然而少量的标签数据的获得相对便宜。在这种情况下，半监督学习方法就有很大的实用价值。因此，用半监督学习方法研究NMF 很有意义。 最近，蔡登等人提出了一种图表正则化NMF(GNMF)方法来编码数据空间的几何信息。GNMF构建一个最近邻图表模拟多种结构。当标签信息可行时，它自然地应用到图表结构中。特别地，如果两个数据点使用同一个标签，大的权重会被分配到边缘连接它们。如果两个数据点使用不同的标签，相应的权重都是0。这就引起了半监督GNMF。这个方法的最大缺点是相同类别的数据点将会一起映射到一个新的表示空间，而且怎样有原则的选取权重并不清晰，这一观点没有理论保证。 本文中，我们提出一种新的矩阵分解方法，叫约束非负矩阵分解(CNMF)，将标签信息作为附加的约束。我们算法的中心是相同类别的数据可以在一个新的表示空间中合并。这样，已经获得的部分表示就有和原始数据一致的标签，因此就有多的识别能力。我们方法的另一个优点是参数自由，避免了参数调试来获得更好的结果。这就使我们的算法更容易方便的应用于真实世界应用中。我们还讨论了怎样高效的解决相应的最优化问题。给出最优化收敛性证明。本文贡献如下：1.标准NMF是一个非监督学习算法不需要结合标签信息。本文中，我们将它扩展为半监督学习算法。此外，我们将标签信息作为约束；这样一来，有相同标签
矩阵分解以及矩阵范数在数值计算中的应用 张先垒 （自动化与电气工程学院 控制科学与工程 2012210186） 【摘要】矩阵的分解是将一个矩阵分解为较为简单的或具有某种特性的若干矩阵的和或 者乘积，这是矩阵理论及其应用中比较常见的方法。由于矩阵的这些特殊的分解形式，一方面反映了矩阵的某些数值特性，如矩阵的秩、特征值、奇异值等；另一方面矩阵的分解方法与过程往往为某些有效的数值计算方法和理论分析提供了重要的依据，它是应用于解最优化问题、特征值问题、最小二乘方问题的主要数学工具。 关键词 ： 矩阵分解 对角化 逆矩阵 范数 条件数 1. 引言 矩阵分解在工程中的应用主要是在解线性方程组中,而这主要就是关系到储存和计算时间的问题上面,如何实现最小的储存和最少的计算时间是在工程计算中的头等问题。在这方年就牵涉到很多对矩阵进行怎样的分解，这篇文章介绍了基本的关于三角分解相关的内容以及关于界的稳定性的考虑。 2. 矩阵的三角分解求解线性方程组 数值求解线性方程组的方法中有一个主要是直接法，假设计算中没有舍入误差，经过有限次算术运算能够给出问题的精确解的数值方法。其中高斯消去法就是利用矩阵的分解实现的。矩阵论一种有效而且应用广泛的分解法就是三角分解法，将一个矩阵分解为一个酉矩阵（或正交矩阵）与一个三角矩阵的乘积或者三角矩阵与三角矩阵的乘积。（见课本P93例4.3）考虑一般的线性方程组，设其中的系数矩阵A 是可逆的， 1111 n m mn a a A a a ?? ? = ? ??? （1-1） 设矩阵A 的第一列中至少有一个是非零元素（否则A 就是奇异矩阵）不妨设为1i a 若一 般的记初等矩阵 [1] 如1-2式及矩阵论课本上的Givens 矩阵。
非负矩阵分解算法概述 (吴有光 NOTE :本文为科普文章,尽量做到通俗而不严格,比较适合理论小白补补 NMF 历史第一部分 Lee&Seung的世界 1 引言 现实生活中的数据,我们总是希望有个稀疏表达,这是从压缩或数据存储的角度希望达到的效果。从另一方面来讲, 我们面对大量数据的时候, 总是幻想能够发现其中的“规律” , 那么在表示或处理的时候,直接操作这些提纲挈领的“规律” ,会有效得多。这个事情,让很多的科学家都伤透脑筋,不过也因此有了饭碗。 1.1第一个例子 我们先来看一个简单的例子。在人文、管理或社会学里,实证研究方法是常用的方法。比如我们来考察大学生就业过程, 对学生的选择工作类别的动机, 我们常说“ 想吃劳保饭的同学铁了心要考公务员, 喜欢轻松自由氛围的同学更趋向于外企, 只想稳定的同学认为国企最好,富二代神马的最爱创业然后继承家产了” ,这句话如果要严格来论证是不可能的,那么我们转而寻求“调查论证” ,即通过设计问卷(问卷上设计了可能影响学生选择的因素, 比如家庭情况、学业情况、性格取向、对大城市或家乡的热恋程度、以及人生观价值观等等各种我们可能会影响就业取向的因素各种我们猜测会影响学生。 问卷上来后,我们通过统计得到如下的列表。 图 1 第一个例子的统计表示例 表中的各个因素我们进行了量化,比如性格因素从完全内向到热情奔放分为 5 个等级 (可以用一些问题来直接或间接获得这个等级。那么剩下的问题就是回答开始的问题:
(1是不是我们设计的每个因素都有效?(显然不是,之所以设计问卷就是要来解决这个问题的 (2是什么因素影响了学生的最终选择?或者说,从统计上来看,每个因素占多大比重? 这时, 用矩阵来表示可写为 , 其中就表示那个因素矩阵, 表示最终取向, 代表我们要求的系数。我们把要求的用代替,写成矩阵形式为: (1 更进一步,如果我们不仅调查学生的去向,还想同时调查很多事情,那么就会有 ,这样上面的式子改写为: (2 此时问题转化为: Q1:已知 ,如何求解
矩阵分解的研究及应用 摘要：将一矩阵分解为若干个矩阵的和或积，是解决某些线性问题的重要方法，其技巧性、实用性强。 本文首先分成四部分内容来阐述矩阵分解的形式及一些很常见的分解。最后举例说明矩阵分解的应用。 关键词：特征值分解 秩分解 三角分解 和分解 关于矩阵分解的形式的文献已有很多，但对于这个问题的分析各不相同。本文从四个方面来论述矩阵的分解的形式，并以一些具体的例子来说明矩阵分解在实际应用中的重要性。 一、特征值分解 性质1：任意n 阶矩阵A ，存在酉矩阵T ，使得1 10n A T T λλ-*?? ? = ? ??? ，其中1,,n λλ 为矩阵A 的 特征值。称形如这样的分解叫做矩阵A 的特征值分解。 性质1'：任意n 阶矩阵A ，存在酉矩阵T ，使得11s J A T T J -?? ? = ? ??? ，其中 11i i i i i i n n J λλλ??? ? ?= ? ? ? ? ，1,2,,i s = 且1,,s λλ 为矩阵A 的特征值。 对于对称矩阵有如下结论： 定理1.1：若A 为n 阶实对称矩阵，则存在正交矩阵T ，使得11n A T T λλ-?? ? = ? ??? ， 其中1,,n λλ 为矩阵A 的特征值。 证明 由性质1,知 存在酉矩阵T ，使得1 10n A T T λλ-*?? ? = ? ??? 又由于A 为n 阶实对称矩阵，因此 111 111000n n n A T T T T A T T λλλλλλ---'??**?????? ? ? ? ?'==== ? ? ? ? ? ? ? ?*??????? ? 从而，得 1 100n n λλλλ*???? ? ? = ? ? ? ?*???? 因此11n A T T λλ-?? ? = ? ??? 得证。
矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质若干矩阵之积或之和，大体分为三角分解、分解、满秩分解和奇异值分解.矩阵地分解是很重要地一部分内容，在线性代数中时常用来解决各种复杂地问题，在各个不同地专业领域也有重要地作用.秩亏网平差是测量数据处理中地一个难点，不仅表现在原理方面，更表现在计算方面，而应用矩阵分解来得到未知数地估计数大大简化了求解过程和难度. 矩阵地三角分解 如果方阵可表示为一个下三角矩阵和一个上三角矩阵之积，即，则称可作三角分解.矩阵三角分解是以消去法为根据导出地，因此矩阵可以进行三角分解地条件也与之相同，即矩阵地前个顺序主子式都不为，即.所以在对矩阵进行三角分解地着手地第一步应该是判断是否满足这个前提条件，否则怎么分解都没有意义.矩阵地三角分解不是唯一地，但是在一定地前提下，地分解可以是唯一地，其中是对角矩阵.矩阵还有其他不同地三角分解，比如分解和分解，它们用待定系数法来解求地三角分解，当矩阵阶数较大地时候有其各自地优点，使算法更加简单方便.资料个人收集整理，勿做商业用途 矩阵地三角分解可以用来解线性方程组.由于，所以可以变换成，即有如下方程组：资料个人收集整理，勿做商业用途 先由依次递推求得,,……，，再由方程依次递推求得，，……，. 资料个人收集整理，勿做商业用途 必须指出地是，当可逆矩阵不满足时，应该用置换矩阵左乘以便使地个顺序主子式全不为零，此时有：资料个人收集整理，勿做商业用途 这样，应用矩阵地三角分解，线性方程组地解求就可以简单很多了. 矩阵地分解 矩阵地分解是指，如果实非奇异矩阵可以表示为，其中为正交矩阵，为实非奇异上三角矩阵.分解地实际算法各种各样，有正交方法、方法和方法，而且各有优点和不足.资料个人收集整理，勿做商业用途 ．正交方法地分解 正交方法解求分解原理很简单，容易理解.步骤主要有：）把写成个列向量（，，……，），并进行正交化得（，，……，）；) 单位化，并令（，，……，），（，，……，），其中；）. 这种方法来进行分解，过程相对较为复杂，尤其是计算量大，尤其是阶数逐渐变大时，就显得更加不方便.资料个人收集整理，勿做商业用途 ．方法地分解 方法求分解是利用旋转初等矩阵，即矩阵()来得到地，()是正交矩阵，并且(()).()地第行第列 和第行第列为，第行第列和第行第列分别为和，其他地都为.任何阶实非奇异矩阵可通过左连乘()矩阵（乘积为）化为上三角矩阵，另，就有.该方法最主要地是在把矩阵化为列向量地基础上找出和，然后由此把矩阵地一步步向上三角矩阵靠近.方法相对正交方法明显地原理要复杂得多，但是却计算量小得多，矩阵()固有地性质很特别可以使其在很多方面地应用更加灵活.资料个人收集整理，勿做商业用途 ．方法地分解 方法分解矩阵是利用反射矩阵，即矩阵，其中是单位列向量，是正交矩阵，.可以证明，两个矩阵地乘积就是矩阵，并且任何实非奇异矩阵可通过连乘矩阵（乘积为）化为上三角矩阵，则.这种方法首要地就是寻找合适地单位列向量去构成矩阵，
《线性代数与矩阵分析》课程小论文 矩阵分解及其应用 学生姓名：****** 专业：******* 学号：******* 指导教师：******** 2015年12月
Little Paper about the Course of "Linear Algebra and Matrix Analysis" Matrix Decomposition and its Application Candidate:****** Major:********* StudentID:****** Supervisor:****** 12,2015
中文摘要 将特定类型的矩阵拆解为几个矩阵的乘机称为矩阵的分解。本文主要介绍几种矩阵的分解方法，它们分别是矩阵的等价分解、三角分解、谱分解、奇异值分解和 Fitting 分解等。矩阵的分解理论和方法是矩阵分析中重要的部分，在求解矩阵的特征值、解线性方程组以及实际工程中有着广泛的运用。因此，本文将介绍矩阵等价分解、三角分解、奇异值分解的理论运用以及三角分解的工程运用。 关键词：等价分解,三角分解,奇异值分解,运用
Abstract Many particular types of matrix are split into the product of a matrix of several matrices, which is called decomposition of matrix. In this paper, we introduce some methods of matrix decomposition, which are equivalent decomposition, triangular decomposition, spectral decomposition, singular value decomposition, Fitting decomposition and so on. The decomposition theory and method of matrix is an important part of matrix analysis, which is widely used in solving the characteristic value, solving linear equations and the practical engineering. In this paper, we will introduce the theory of matrix equivalence decomposition, triangular decomposition, singular value decomposition and the engineering application of triangular decomposition. Key words：Equivalent Decomposition, Triangular Decomposition, Singular Value Decomposition, Application
机器学习中的数学 5 强大的矩阵奇异 值分解SVD 机器学习中的数学(5)-强大的矩阵奇异值分解(SVD)及其应用 版权声明： 本文由LeftNotEasy发布于本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系wheeleast@https://www.doczj.com/doc/da16886099.html, 前言： 上一次写了关于PCA与LDA的文章，PCA的实现一般有两种，一种是用特征值分解去实现的，一种是用奇异值分解去实现的。在上篇文章中便是基于特征值分解的一种解释。特征值和奇异值在大部分人的印象中，往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面，也很少讲任何跟特征值与奇异值有关的应用背景。奇异值分解是一个有着很明显的物理意义的一种方法，它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示，这些小矩阵描述的是矩阵的重要的特性。就像是描述一个人一样，给别人描述说这个人长得浓眉大眼，方脸，络腮胡，而且带个黑框的眼镜，这样寥寥的几个特征，就让别人脑海里面就有一个较为清楚的认识，实际上，人脸上的特征是有着无数种的，之所以能这么描述，是因为人天生就有着非常好的抽取重要特征的能力，让机器学会抽取重要的特征，SVD是一个重要的方法。 在机器学习领域，有相当多的应用与奇异值都可以扯上关系，比如做feature reduction的PCA，做数据压缩(以图像压缩为代表)的算法，还有做搜索引擎语义层次检索的LSI(Latent Semantic Indexing) 另外在这里抱怨一下，之前在百度里面搜索过SVD，出来的结果都是俄罗斯的一种狙击枪(AK47同时代的)，是因为穿越火线这个游戏里面有一把狙击枪叫做SVD，而在Google上面搜索的时候，出来的都是奇异值分解(英文资料为主)。想玩玩战争游戏，玩玩COD不是非常好吗，玩山寨的CS有神马意思啊。
矩阵的奇异值分解（SVD）及其应用 版权声明： 本文由LeftNotEasy发布于https://www.doczj.com/doc/da16886099.html,, 本文可以被全部的转载或者部分使用，但请注明出处，如果有问题，请联系wheeleast@https://www.doczj.com/doc/da16886099.html, 前言： 上一次写了关于PCA与LDA的文章，PCA的实现一般有两种，一种是用特征值分解去实现的，一种是用奇异值分解去实现的。在上篇文章中便是基于特征值分解的一种解释。特征值和奇异值在大部分人的印象中，往往是停留在纯粹的数学计算中。而且线性代数或者矩阵论里面，也很少讲任何跟特征值与奇异值有关的应用背景。奇异值分解是一个有着很明显的物理意义的一种方法，它可以将一个比较复杂的矩阵用更小更简单的几个子矩阵的相乘来表示，这些小矩阵描述的是矩阵的重要的特性。就像是描述一个人一样，给别人描述说这个人长得浓眉大眼，方脸，络腮胡，而且带个黑框的眼镜，这样寥寥的几个特征，就让别人脑海里面就有一个较为清楚的认识，实际上，人脸上的特征是有着无数种的，之所以能这么描述，是因为人天生就有着非常好的抽取重要特征的能力，让机器学会抽取重要的特征，SVD是一个重要的方法。 在机器学习领域，有相当多的应用与奇异值都可以扯上关系，比如做feature reduction的PCA，做数据压缩（以图像压缩为代表）的算法，还有做搜索引擎语义层次检索的LSI（Latent Sem antic Indexing） 另外在这里抱怨一下，之前在百度里面搜索过SVD，出来的结果都是俄罗斯的一种狙击枪（AK47同时代的），是因为穿越火线这个游戏里面有一把狙击枪叫做SVD，而在Google上面搜索的时候，出来的都是奇异值分解（英文资料为主）。想玩玩战争游戏，玩玩COD不是非常好吗，玩山寨的CS有神马意思啊。国内的网页中的话语权也被这些没有太多营养的帖子所占据。真心希望国内的气氛能够更浓一点，搞游戏的人真正是喜欢制作游戏，搞Data Mining的人是真正喜欢挖数据的，都不是仅仅为了混口饭吃，这样谈超越别人才有意义，中文文章中，能踏踏实实谈谈技术的太少了，改变这个状况，从我自己做起吧。 前面说了这么多，本文主要关注奇异值的一些特性，另外还会稍稍提及奇异值的计算，不过本文不准备在如何计算奇异值上展开太多。另外，本文里面有部分不算太深的线性代数的知识，如果完全忘记了线性代数，看本文可能会有些困难。 一、奇异值与特征值基础知识： 特征值分解和奇异值分解在机器学习领域都是属于满地可见的方法。两者有着很紧密的关系，我在接下来会谈到，特征值分解和奇异值分解的目的都是一样，就是提取出一个矩阵最重要的特征。先谈谈特征值分解吧： 1）特征值： 如果说一个向量v是方阵A的特征向量，将一定可以表示成下面的形式：
浅析矩阵分解的原理及其在人脸识别中的应用 摘要：矩阵分解方法有多种，本文首先对矩阵的分解方法做了简单的介绍，这些分解在数值代数和最优化问题的解决中都有着十分重要的角色以及在其它领域方面也起着必不可少的作用。人脸识别是指采用机器对人脸图像进行分析,进而提取有效的识别信息从而达到身份辨认的目的。近年来因其在安全、认证、人机交互、视频电话等方面的广泛应用前景而越来越成为计算机模式识别领域的热点。本文在分析矩阵分解的原理后详细针对其在人脸识别中的应用做了一些初步认识的总结。 关键词：矩阵分解QR分解奇异值分解非负矩阵分解人脸识别 矩阵是数学中最重要的基本概念之一，是代数学的一个主要研究对象，也是数学研究及应用的一个重要工具。在近代数学、工程技术、信息处理、经济理论管理科学中，也大量涉及到矩阵理论的知识，矩阵分解是指根据一定的原理用某种算法将一个矩阵分解成若干个矩阵的乘积或者一些矩阵之和。这些分解式的特殊形式，一是能明显地反映出原矩阵的某些特征；二是分解的方法与过程提供了某些有效的数值计算方法和理论分析依据。人脸识别是指采用机器对人脸图像进行分析 ,进而提取有效的识别信息从而达到身份辨认的目的。虽然人类能轻松地识别出人脸,但人脸的自动机器识别却是一个难度极大的课题,它涉及到图像处理、模式识别、计算机视觉和神经网络等学科,也和对人脑的认识程度紧密相关。现在矩阵分解在人脸识别中应用很广泛，有不同的算法来实现，本文将对现有的算法做总结和比较。 1 矩阵的分解方法 矩阵分解 (decomposition, factorization)是将矩阵拆解为数个矩阵的乘积，可分为三角分解、满秩分解、QR分解、Jordan分解和SVD（奇异值）分解等，常见的有三种：1)三角分解法 (Triangular Factorization)，2)QR 分解法 (QR Factorization)，3)奇异值分解法 (Singular Value Decomposition)。 1.1 矩阵的三角（LU）分解 LU分解，设A=()是n阶可逆矩阵，如果A的对角线下（上）方的元素全为零，即对i>j， =0（对i 矩阵分解及其简单应用 x=b，即有如下方程组：Ly=bUx=y 先由Ly=b依次递推求得y1, y2,……，yn，再由方程Ux=y依次递推求得 xn，xn-1，……， x1、必须指出的是，当可逆矩阵A不满足?k≠0时，应该用置换矩阵P左乘A以便使PA的n个顺序主子式全不为零，此时有： Ly=pbUx=y 这样，应用矩阵的三角分解，线性方程组的解求就可 以简单很多了。2、矩阵的QR分解矩阵的QR分解是指，如果实 非奇异矩阵A可以表示为A=QR，其中Q为正交矩阵，R为实非奇 异上三角矩阵。QR分解的实际算法各种各样，有Schmidt正交方法、Givens方法和Householder方法，而且各有优点和不足。2、1．Schmidt正交方法的QR分解Schmidt正交方法解求QR分解原 理很简单，容易理解。步骤主要有：1）把A写成m个列向量a= （a1，a2，……，am），并进行Schmidt正交化得=（α1， α2，……，αm）；2) 单位化，并令Q=（β1，β2，……，βm），R=diag（α1， α2，……，αm）K，其中a=K；3）A=QR、这种方法来进行QR分解，过程相对较为复杂，尤其是计算量大，尤其是阶数逐渐变大时，就显得更加不方便。2、2．Givens方法的QR分解Givens方 法求QR分解是利用旋转初等矩阵，即Givens矩阵Tij(c,s)来得 到的，Tij(c,s)是正交矩阵，并且det(Tij(c,s))=1。Tij(c,s)的第i行第i列和第j行第j列为cos，第i行第j列和第j行第i 列分别为sin和-sin，其他的都为0、任何n阶实非奇异矩阵A可通过左连乘Tij(c,s)矩阵（乘积为T）化为上三角矩阵R，另 Q=T-，就有A=QR。该方法最主要的是在把矩阵化为列向量的基础上找出c和s，然后由此把矩阵的一步步向上三角矩阵靠近。Givens方法相对Schmidt正交方法明显的原理要复杂得多，但是却计算量小得多，矩阵Tij(c,s)固有的性质很特别可以使其在很多方面的应用更加灵活。2、3．Householder方法的QR分解Householder方法分解矩阵是利用反射矩阵，即Householder矩阵H=E-2uuT，其中u是单位列向量，H是正交矩阵，detH=-1。可以证明，两个H矩阵的乘积就是Givens矩阵，并且任何实非奇异矩阵A可通过连乘Householder矩阵（乘积为S）化为上三角矩阵R，则A= QR。这种方法首要的就是寻找合适的单位列向量去构成矩阵H，过程和Givens方法基本相似，但是计算量要小一些。矩阵的QR分解可以用来解决线性最小二乘法的问题，也可以用来降低矩阵求逆的代价。矩阵的求逆是件不小的工程，尤其是阶数慢慢变大的情况时，而用先把矩阵QR分解成正交矩阵和上三角矩阵，就容易多了，况且正交矩阵的转置就是逆，这一点是其他的矩阵分解无法比拟的。在解求线性方程组中，如果系数矩阵的阶数比较大，可以利用QR分解来使计算简单化。另外，QR分解考虑的是n阶矩阵，其他的矩阵是不能用这种方法进行分解，由于QR 分解的这一前提条件，使得下面提到的满秩矩阵分解和奇异值分解就有了其特殊的意义。3、满秩分解满秩分解也称最大秩分 第34卷第2期2004年3月 东南大学学报(自然科学版) JOURNA L OF S OUTHE AST UNIVERSITY (Natural Science Edition ) V ol 134N o 12Mar.2004 一种受限非负矩阵分解方法 黄钢石1 张亚非1 陆建江1,2,3 徐宝文2,3 (1解放军理工大学通信工程学院,南京210007) (2东南大学计算机科学与工程系,南京210096) (3江苏省软件质量研究所,南京210096) 摘要:提出一种获取潜在语义的受限非负矩阵分解方法.通过在非负矩阵分解方法的目标函数上增加3个约束条件来定义受限非负矩阵分解方法的目标函数,给出求解受限非负矩阵分解方法目标函数的迭代规则,并证明迭代规则的收敛性.与非负矩阵分解方法相比,受限非负矩阵分解方法能获取尽可能正交的潜在语义.实验表明,受限非负矩阵分解方法在信息检索上的精度优于非负矩阵分解方法. 关键词:非负矩阵分解;受限非负矩阵分解;潜在语义;信息检索中图分类号:TP18 文献标识码:A 文章编号:1001-0505(2004)022******* Constrained factorization method for non 2negative m atrix Huang G angshi 1 Zhang Y afei 1 Lu Jianjiang 1,2,3 Xu Baowen 2,3 (1Institute of C ommunication Engineering ,P LA University of Science and T echnology ,Nanjing 210007,China ) (2Department of C om puter Science and Engineering ,S outheast University ,Nanjing 210096,China ) (3Jiangsu Institute of S oftware Quality ,Nanjing 210096,China ) Abstract :A novel method ,constrained non 2negative matrix factorization ,is presented to capture the latent semantic relations.The objective function of constrained non 2negative matrix factorization is defined by im posing three additional constraints ,in addition to the non 2negativity constraint in the standard non 2negative matrix factorization.The update rules to s olve the objective function with these constraints are presented ,and its convergence is proved.In contrast to the standard non 2negative matrix factorization ,the constrained non 2negative matrix factorization can capture the semantic relations as orthog onal as possible.The experiments indicate that the constrained non 2negative matrix factorization has better precision than the standard non 2negative matrix factorization in in formation retrieval. K ey w ords :non 2negative matrix factorization ;constrained non 2negative matrix factorization ;latent semantic relations ;information retrieval 收稿日期:2003206213. 基金项目:国家自然科学基金青年科学基金资助项目(60303024)、国家973规划资助项目(G 1999032701)、国家自然科学基金资助项目 (60073012). 作者简介:黄钢石(1969— ),男,博士生,工程师,huang -gangshi @https://www.doczj.com/doc/da16886099.html,;张亚非(联系人),男,博士,教授,博士生导师,y f zhang888@https://www.doczj.com/doc/da16886099.html,.非负矩阵分解(non 2negative matrix factorization ,NMF )是一种新的矩阵分解方法,它将一个元素非负的矩阵分解为左右2个非负矩阵乘积[1,2].由于分解后的矩阵中仅包含非负元素,因此原矩阵中列向量可解释为对左矩阵中所有列向量(称为基向量)的加权和,而权重系数为右矩阵中对应列向量中的元素.这种基于基向量组合的表示形式具有直观的语义解释,反映了人们思维中“局部构成整体”的概念.NMF 已成功应用于多个领域[3,4],作者也已尝试将NMF 应用于从用户会话中发现典型用户文件[5,6]. NMF 算法也可以用于获取文本集中的潜在语义.由于NMF 算法得到的解是局部最优解,获取的潜在 语义之间往往存在冗余[2],为使潜在语义尽可能正交,提出一种受限的非负矩阵分解方法C NMF 对矩阵分解及其应用 矩阵分解是指将一个矩阵表示为结构简单或具有特殊性质若干矩阵之积或之和，大体分为三角分解、QR 分解、满秩分解和奇异值分解。矩阵的分解是很重要的一部分内容，在线性代数中时常用来解决各种复杂的问题，在各个不同的专业领域也有重要的作用。秩亏网平差是测量数据处理中的一个难点，不仅表现在原理方面，更表现在计算方面，而应用矩阵分解来得到未知数的估计数大大简化了求解过程和难度。 1. 矩阵的三角分解 如果方阵A可表示为一个下三角矩阵L和一个上三角矩阵U之积，即A=LU 则称A可作三角分解。矩阵三角分解是以Gauss消去法为根据导出的，因此矩阵可以进行三角分解的条件也与之相同，即矩阵A的前n-1个顺序主子式都不为0, 即?k工0.所以在对矩阵A进行三角分解的着手的第一步应该是判断是否满足这个前提条件，否则怎么分解都没有意义。矩阵的三角分解不是唯一的，但是在一定的前提下， A=LDU勺分解可以是唯一的，其中D是对角矩阵。矩阵还有其他不同的三角分解，比如Doolittle 分解和Crout 分解，它们用待定系数法来解求 A 的三角分解，当矩阵阶数较大的时候有其各自的优点，使算法更加简单方便。 矩阵的三角分解可以用来解线性方程组Ax=b。由于A=LU，所以Ax=b可以变换成LU x=b，即有如下方程组： Ly = b { {Ux = y 先由Ly = b依次递推求得y i, y2, ........ ，y n，再由方程Ux = y依次递推求得X n， x n-1 ， ... ，X1 . 必须指出的是，当可逆矩阵A不满足?k工0时，应该用置换矩阵P左乘A以便使PA 的n个顺序主子式全不为零，此时有： Ly = pb { { Ux = y 这样，应用矩阵的三角分解，线性方程组的解求就可以简单很多了。 2. 矩阵的QF分解 矩阵的QR分解是指，如果实非奇异矩阵A可以表示为A=QR其中Q为正交矩阵，R为实非奇异上三角矩阵。QR分解的实际算法各种各样，有Schmidt正交方 浅谈矩阵的LU 分解和QR 分解及其应用 基于理论研究和计算的需要，往往有必要把矩阵分解为具有某种特性的矩阵之积，这就是我们所说的矩阵分解. 本文将介绍两种常用的矩阵分解方法，以及其在解线性方程组及求矩阵特征值中的应用. 1.矩阵的LU 分解及其在解线性方程组中的应用 1.1 高斯消元法 通过学习，我们了解到利用Gauss 消去法及其一些变形是解决低阶稠密矩阵方程组的有效方法.并且近些年来利用此类方法求具有较大型稀疏矩阵也取得了较大进展.下面我们就通过介绍Gauss 消去法，从而引出矩阵的LU 分解及讨论其对解线性方程组的优越性. 首先通过一个例子引入： 例1,解方程组 (1.1) (1. 2)(1.3) 解.1Step (1.1)(2)(1.3)?-+ 消去(1.3)中未知数,得到 23411x x --=-(1.4) 2Shep . (1.2)(1.4)+ 消去(1.4)中的未知数2 x 有12323364526x x x x x x ++=-=-=-????? 显然方程组的解为* x =123?? ? ? ? ?? 上述过程相当于 111604152211?? ?- ? ?-??~111604150411?? ?- ? ?---??~111 604150026?? ? - ? ? --?? 2-（）+ ()i i r 表示矩阵的行 由此看出，消去法的基本思想是：用逐次消去未知数的方法把原方程化为与其等价的三角方程组. 下面介绍解一般n 阶线性方程组的Gauss 消去法. 设111n n1nn a a a a A ?? ?= ? ??? 1n x X x ?? ?= ? ??? 1n b b b ?? ? = ? ??? 则n 阶线性方程组 AX b =(1.5) 并且A 为非奇异矩阵. 通过归纳法可以将AX b =化为与其等价的三角形方程，事实上： 及方程(1.5)为()()1 1 A X b =,其中 ()1A A =()1 b b = (1) 设(1) 11 0a ≠，首先对行计算乘数() ()1 1i11 11i a m m =.用1i m -乘(1.5)的第一个方程加到第 ()2,3,,i i n =?个方程上.消去方程(1.5)的第2个方程直到第n 个方程的未知数1x . 得到与(1.5)等价的方程组()()()11n 12n 111nn 0a a x x a ????? ? ? ? ? ? ?????? =()()112n b b ?? ? ? ??? 简记作 ()()22A b =(1.6) 其中()()() ()()()211211111 ij ij i ij i i i a m b b m a a b =-=- (2) 一般第()11k k n ≤≤-次消去，设第1k -步计算完成.即等价于 ()()k k A X b = (1.7) 且消去未知数121,,,k x x x -?.其中() ()()() ()() ()()()()11 1 11 12 12222 2k k k k kk kn k nk nna n n a a a a a A a a a a ?? ? ? ? ? = ? ? ? ?? ? 目录 摘要 (i) Abstract (iii) 第一章绪论 (1) 1.1课题研究的背景和意义 (1) 1.2国内外研究现状 (2) 1.3论文主要工作 (4) 1.3.1论文的主要内容 (4) 1.3.2论文的组织结构 (5) 第二章非负矩阵分解模型及相关变体 (7) 2.1非负矩阵分解 (7) 2.2非负矩阵分解的相关变体 (8) 2.3具有代表性的生物数据 (9) 2.4本章小结 (10) 第三章基于高斯赛德尔方法的非负矩阵分解及其生物学应用 (11) 3.1基因微阵列数据以及其聚类分析 (11) 3.1.1基因微阵列数据 (11) 3.1.2基因表达数据聚类分析 (11) 3.2基于高斯塞德尔方法的非负矩阵分解 (13) 3.2.1提出的动机 (13) 3.2.2GSNMF模型 (13) 3.2.3GSNMF优化算法高斯塞德尔非负方程组优化 (14) 3.3数值实验 (16) 3.3.1聚类评估标准 (17) 3.3.2实验数据 (17) 3.3.3聚类实验 (18) 3.4本章小结 (20) 第四章基于一致信息熵度量的图正则非负矩阵分解及其生物学应用 (21) 4.1图正则非负矩阵分解 (21) 4.2鲁棒的图正则非负矩阵分解变体 (22) 4.2.1最大化一致信息熵的图正则非负矩阵分解 (22) 4.2.2鲁棒流型非负矩阵分解 (22) 4.3基于一致信息熵度量的图正则非负矩阵分解 (22) 4.3.1一致信息熵度量 (22) 4.3.2CGNMF模型 (23) 4.3.3CGNMF更新规则 (23) 4.3.4CGNMF模型的图学习 (25) 4.3.5CGNMF模型收敛性证明 (27) 4.4数值实验 (28) 4.4.1经典人脸库上的识别实验 (28) 4.4.2人机结合的脑电波数据聚类分析实验 (32) 4.5本章小结 (34) 第五章基于一致信息熵度量的有监督非负矩阵分解 (35) 5.1模型判别罚项 (35) 5.1.1部分判别罚项 (35) 5.1.2完全判别罚项 (36) 5.2基于一致信息熵度量的有监督非负矩阵分解 (37) 5.3数值实验 (38) 5.3.1EEG数据的分类识别实验 (38) 5.3.2结果分析 (43) 5.4本章小结 (43) 第六章结束语 (45) 6.1工作总结 (45) 6.2不足和展望 (45) 致谢 (47) 参考文献 (49) 作者在学期间取得的学术成果 (53)矩阵分解及其简单应用
一种受限非负矩阵分解方法_黄钢石
(完整word版)矩阵分解及其简单应用
浅谈矩阵的LU分解和QR分解及其应用
非负矩阵分解及其生物信息学应用
相关主题
文本预览