定理在积极数据:NMF的独特性

文摘

我们调查的条件,非负矩阵分解(NMF)是独一无二的,介绍几个定理可以决定是否分解实际上是独特的。定理是通过几个例子来说明定理的使用及其局限性。我们已经表明,腐败的一个独特的NMF矩阵相加噪声导致的噪声估计无噪声的唯一解。最后,我们使用一个随机的NMF分析底层模型的特性将导致NMF小估计错误。

1。介绍

大量的积极的数据出现在音乐分析等研究领域,文本分析,图像分析和概率论。之前演绎科学应用于大量的数据,通常是适当的减少数据预处理,例如,通过矩阵秩减少或特征提取。主成分分析是一种这样的预处理。当原始数据是负的,通常需要保存这个属性的预处理。例如,元素在功率谱图,概率,像素强度仍应负的处理后才有意义。这导致了建筑等级减少矩阵和特征提取的算法产生负的输出。许多算法与非负矩阵分解(NMF)算法提出的李和Seung [1,2]。NMF算法因式分解一个非负矩阵或为两个非负矩阵和: 没有封闭的问题找到解决方案和给定一个,但李和Seung (1,2)提出了两种计算高效算法最小化之间的区别和两种不同的错误的功能。之后,提出了很多其他算法(见[3])。

一个有趣的问题是,一个特定的矩阵的NMF是独一无二的。这个问题的重要性取决于NMF的特定应用程序。当使用一个模型可以有两个不同的观点像NMF-either可以认为模型描述自然和变量和有一个物理意义或可以认为模型可以捕获感兴趣的一部分,即使没有参数和模型之间的一对一的映射,以及物理系统。当使用NMF时,人可以怀疑一些潜在的干扰版本吗还是另一个模型构造的数据,或者换句话说,一个地面真理和确实存在。这些问题是很重要的在评估是否这是一个问题,还有一个NMF的解决方案,相同的数据,也就是说, 如果使用NMF尽管数据并不认为是由(1),它可能不是一个问题,有几个其他的解决方案。另一方面,如果一个假定地面真理存在,它可能是一个问题如果模型不检测,也就是说,如果它是不可能的和从数据矩阵。

第一篇文章的主题是两个伯曼之间的通讯和托马斯。在[4伯曼]要求相当于一个简单的非负矩阵的类的描述一个NMF的存在。我们应当看到,由托马斯·[答案5可以转移到一个NMF唯一性定理。

第一篇文章调查NMF的独特性是Donoho Stodden [6]。他们用凸二元性得出这样的结论:在某些情况下,那里的列向量“描述部分,因此是不重叠的,从而正交,NMF的解决方案是独一无二的。

同时随着NMF的发展,Plumbley [7)与非负独立分量分析,其中一个问题是估计一个旋转矩阵从观察的形式,在那里是一个非负向量。在此设置中,Plumbley调查一个属性为非负独立同分布(先验知识)向量这样可以被估计。他表明,如果元素接地和足够大的观察,然后呢可以被估计。唯一性约束(7)是一个统计的条件。

的结果(7]NMF高度关联的独特性是由于一个事实:在大多数情况下,新的NMF解决方案的形式和节中描述3。通过使用Plumbley两次的结果,可以构造NMF的受限制的唯一性定理。

在本文中,我们研究在何种情况下NMF的观察到非负矩阵是独一无二的。我们提出独特新颖的必要和充分条件。几个例子说明这些条件和他们的解释。此外,我们表明,NMF健壮的加性噪声。更具体地说,我们表明,可以获得准确的估计和从嘈杂的数据时产生NMF是独一无二的。最后,我们考虑到生成NMF作为随机过程,显示特定类的这些过程几乎肯定导致NMFs独特。

本文的结构如下。部分2介绍了符号,一些定义和基本结果。一个精确的定义和一个独特的NMF的两大特征给出了部分3。的最小限制和为一个独特的NMF进行部分4。条件和独特的NMF的例子给出了部分5。节6,结果表明,在噪声的情况下被添加到一个数据矩阵与一个独特的NMF,可以绑定错误的估计和。概率视图的独特性被认为是部分7。讨论了定理的含义8,部分9总结了纸。

2。基本面

这里我们将介绍凸二元性,将论文的框架,但首先我们要定义要使用的符号。非负实数表示为弗罗贝尼乌斯范数表示,是由一组向量张成的空间。每种类型的变量有自己的字体。例如,一个标量来标示,一个列向量表示,用一个行向量,用一个矩阵,一组是用,用一个随机变量。此外,是指数向量。当一个条件一组用于描述一个矩阵,它指的是列向量的矩阵。NMF是对称的和,所以一个矩阵的定理也可以用于其他。

在本文中,我们做一个几何解释的NMF类似用于5,6]。为此,我们需要下面的定义。

定义1。的积极的跨是由。

在一些文献,积极跨叫做圆锥壳。

定义2。一组被称为单形锥如果有一组这样。的订单单纯的锥最小数量的元素吗。

定义3。的双到一组,表示的话,是。

下面的引理很容易证明,随后将使用。对于更一般的介绍凸二元性,看到[8]。

引理1。(一)如果,然后当且仅当对所有。
(b)如果和是可逆的,然后。
(c)如果,然后。
(d)如果和单形锥和关闭吗,然后。

3所示。对偶空间和NMF

在本节中,我们定义独特的NMF和一些独特的NMF一般条件。作为一个起点,让我们假设和有满秩,。

让和是任何实现的矩阵,。然后,。的列向量和因此依据相同的空间,因此存在一个基础转移矩阵这样。由此可见,。因此,所有NMF的解决方案的形式。在这些情况下,NMF的模棱两可的矩阵。注意,如果以上参数是无效的,因为可以不同,从而。

例1。下面的一个例子矩阵的秩但是没有,NMF有两种解决方案矩阵连接解决方案 我们顺便提及,托马斯(5)使用这个矩阵来说明一个相关的问题。这就完成了。

引理2 (Minc [9引理2 1.1])。一个非负矩阵的逆非负当且仅当它是一个按比例缩小的排列。

引理2显示所有NMF解形式和,在那里是一个按比例缩小的排列,是有效的,从而,NMF只能是唯一的排列和扩展。这将导致以下本文独特的NMF的定义。

定义4。一个矩阵有一个独特的NMF如果歧义是排列和扩展的列和行。

独特性的缩放和排列歧义的定义是一个著名的模棱两可,发生在许多盲源分离问题。这种独特的NMF的定义,可以进行以下两个独特的NMF的性格特征。定理1。如果,NMF独特当且仅当积极的象限是唯一订购单形锥这样。证明。证明之前的分析矩阵结合以上引理1(b)。也可以证明这个定理的证明步骤后(5]。定理2(见[6])。NMF独特当且仅当只有一个订购单形锥这样,在那里是积极的象限。证明。证明是直接从定义。第一个特征是激励,5和介绍的第二个特征是隐式的6]。注意,这两个特征的独特NMF分析问题从两个不同的观点。定理1需要一个已知的和对作为起点,看着“里面”的解决方案,维行向量空间和列向量。定理2看问题从“外”,也就是说,维列空间。

4所示。矩阵的条件

如果是独一无二的,那么这两个和分别必须是唯一的,只有一个NMF的其中一个,即和。在本节中,一个必要条件和给出一个充分条件。

下面的定义将被证明是必要条件的行向量和列向量。

定义5。一组向量的被称为边界附近如果对所有和有一个元素这样

在闭集的情况下,边界条件是密切和。在本节中,集将有限的(因此关闭了),但在部分7上面的一般定义是必要的。

定理3。行向量的集合必须边界关闭相应的NMF是唯一的。

证明。如果行向量的集合不是边界附近,存在索引和这样总是超过th元素倍的行向量的元素。让,在那里 和表示标准的基向量。这组满足条件因此,我们使用定理1,得出结论,NMF不能是唯一的。

的行向量小元素确定独特性可以从下面的例子。

例2。下面是一个例子并不是唯一的但是多少。
让 在这里边界接近但不是唯一的吗。的独特性可以验证通过策划矩阵如图1,观察定理的条件1是能够实现的。这就完成了。

在三维空间中,如示例2,很容易调查边界是否关闭是unique-if,然后只能有两种结构类型:要么是微不足道的(理想的)解决方案在哪里或解决方案的对角线是零。在更高的维度,所有非平凡解组合数量的增加和调查所有可能的重要的结构变得更加复杂。例如,如果是矩阵的例子吗2,那么矩阵 边界接近,可以从几个方面来分解,例如, 而不是寻求一个独特的必要和充分条件,没什么比必要的充分条件。在这个充分条件,我们只关注的行向量以零(或很小)元素。定义6。一组向量在被称为强烈边界附近如果是边界附近,存在一个和一个编号的向量中的元素和有向量的完成以下:
(1) 对所有;和(2) ,在那里是矩阵的条件数”定义为最大和最小奇异值之间的比例10,81页),和是一个投影矩阵,选择最后一个元素的一个向量。定理4。如果强烈边界关闭呢是独一无二的。证明是相当的技术,因此在附录中给出。最重要的是要注意到定理的必要条件3和定理的充分条件4是非常相似的。第一项强烈边界附近定义中指出,有几个向量小值。第二项确保与小值是线性无关的向量元素。

5。R的独特性

在本节中,独特的条件进行了分析。首先,示例3用于调查当强烈边界关闭和一对是独一无二的。结尾部分的约束和结果在一个独特的NMF。

例3。这是一个调查的独特性当和给出了作为 在哪里。这两个和强烈边界密切,吗参数可以计算 上面的方程表明,小将导致接近一个和一个在一个大接近一个结果。在图2,矩阵是策划。虚线是理想的解决方案,并在所有数据重复。这是看到阴影区域时减少增加,固体边界增加的时候增加。对所有值,阴影区域和固体边界与冲三角形相交。因此,它是不可能得到另一个解决方案通过增加/减少所需的解决方案。图中显示,NMF是独一无二的并不是唯一的可选择的解决方案是虚线所示。的NMF并非独一无二还可以通过选择来验证吗的对称正交矩阵 看看这两个和是负的。如果,那么矩阵是由 这表明不需要零NMF的独一无二的。这就完成了。

在上面的示例中,=从而实现相同的约束。在许多应用程序中,的意思和不同,例如,在音乐分析的列向量光谱的笔记和吗是一个注意活动矩阵(11]。

其次,是研究如何使一个不对称的唯一性约束。

定义7。一组向量被称为足够的传播如果对所有和,有一个元素这样

注意,在充分的定义设置传播th元素大于之和与强烈边界定义的th元素小于之和。

引理3。一套充分传播的双重空间是积极的象限。

证明。一套充分传播非负,因此积极的象限的一部分双重任何足够传播集合。让是一个向量的负面元素th元素和选择 在任何足够传播集,一个存在,这样因此 的因此不是在任何足够双重传播。

在有限集的情况下,充分传播条件是一样的要求按比例缩小的版本的所有标准基向量充分传播组的一部分。很容易确认一套充分扩散边界附近,也强烈参数是一个。

定理5。如果一对充分扩散和强烈边界,NMF的是独一无二的。

证明。引理3州双组一套充分传播积极的象限, 定理4州是独一无二的,通过使用(16)和定理1我们得出这样的结论:是独一无二的。

定理5结果是一个更强大的版本Donoho和Stodden6定理1]。定理1在[6)还假设充分扩散,但条件比强烈边界接近的假设。

6。摄动分析

在前面的部分中,我们分析了情况与一个独特的解决方案。在本节中,结果表明,在某些情况下可以视为非唯一性估计噪声和。描述了如何关闭估计的误差函数两人是真实的一对是 在哪里是一个置换矩阵和是一个对角矩阵。

定理6。让是一个独特的NMF。给出一些,存在一个这样,任何非负,在那里满足 在哪里

证明在附录中给出。这个定理指出,如果观察被加性噪声,然后它会导致噪声估计和。此外,定理6表明,如果噪音小,这将导致小估计错误。在本节中,弗罗贝尼乌斯规范中使用(17)和(19)定理6混凝土。定理6也是相同的有效证明如果使用任何连续度量而不是弗罗贝尼乌斯的规范在这些方程。例4。这个例子调查中的加性噪声之间的关系和估计误差和。的列向量是依据一个人的照片,一只狗,和太阳如图3(一个),3 (b),3 (c)。在图3 (d),图片显示的三个基础。矩阵所有的图片组合的集合,也就是说, 定理5可以得出结论,NMF的吗是独特的因为和充分扩散,从而也强烈边界附近。

在这个例子中,两个不同的噪声矩阵,和,使用。的矩阵模型的观察和元素随机均匀先验知识。矩阵元素包含- 1的位置元素有两个零,也就是说,是- 1在狗的位置和这个男人是重叠的。在这种情况下,误差矩阵模拟模型不匹配,出现在以下两种类型的真实数据。如果数据集组成的图片,根据图片会重叠,一个像素将包括一个基础图片而不是重叠的照片的混合物。如果数据是一组振幅谱,真正的模型是一个复杂的值并不是一个加法的振幅。
分解的估计误差绘制在图4当错误的标准矩阵,也就是说,。估计的使用迭代算法对计算Lee Seung[弗罗贝尼乌斯范数最小化的2]。该算法运行500次迭代,从100个不同的位置。最小化的分解是选择,数值计算。图4显示,当添加误差很小,可以估计底层参数。当添加噪声矩阵的规范增加时,两个噪声矩阵的行为,和,是不同的。为,估计误差的增加慢慢添加了规范的矩阵的估计误差增加显著大于规范时。在仿真中,我们进行了以下的观察可以解释这一差别在两种类型的噪声的性能。当基础,图片仍然吵闹的版本的人,狗和太阳。当使用和规范比吗,根据照片是男人不包括重叠,狗不重叠,重叠的男人和狗。另一种方法来描述不同的等级是一个扰动是在一维,在哪里满秩和扰动在许多维度。这就完成了。
推论1。让是一个独特的NMF和,在那里和。鉴于和存在一个这样,如果双方的最大绝对值和小于,然后 在哪里是任何NMF的。 证明。这是直接从定理6。的情况下可以使用推论有小的元素和但没有(或不够)零元素下面的例子。

例5。让,在那里生成的例子吗3。让所有在这两个元素和等于。在图5,是策划和。在这个例子中,阴影区域和固体边界相交与所需的解决方案。因此,它可以被简单地增加/减少其他解决方案所需的解决方案。为的解决方案接近所需的解决方案的角落。当,大多数角落可以放置在固体边界和仍然形成一个三角形包含阴影区域。当,角落可以在固体边界。这就完成了。

7所示。概率和独特性

在本节中,行向量的列被视为两个随机变量的结果。样本空间的特征(一个随机变量的可能结果)导致独特的NMF将调查。

定理7。我们的行向量生成的随机变量我们的列向量生成由一个随机变量。如果样本空间强烈边界附近的样本空间是充分扩散,那么所有和,存在和这样 在哪里是矩阵,这样吗和非负和数据大小吗是这样的,和。

证明。如果数据是按比例缩小的,,它不改变测量时解的非唯一性矩阵。因此证明了规范化的版本和。让和归一化的版本和。存在有限集和向量的关闭和强烈边界附近和充分扩散。由定理5众所周知,是独一无二的。通过增加向量的个数从采样和,对于任何,将会有两个向量的子集,和,的概率更大将会实现 可以使用推论1在这个子集。事实上,限制相当于限制(21)当向量规范化总结了证据。

例6。让所有的元素指数i.i.d.因此产生足够的样本空间传播。此外,让每一行是指数i.i.d.加上一个随机向量样本空间因此强烈边界附近。在图6,上面的变量显示以下四个矩阵大小。这就完成了。

8。讨论

本文的方法是调查当nonnegativity导致独特性与NMF连接,。Nonnegativity是唯一的假设的定理,定理所以不能用作一个NMF论点nonunique如果有额外的信息或。一个例子与强唯一性结果是稀疏NMF算法霍耶(12)建立在假设的行向量知道之间的比率规范和规范。赛思et al。13)研究独特性强唯一性结果在这种情况下,列示。另一个例子是数据矩阵每一行添加了一个常数。在这种情况下,仿射NMF算法(14)可以使NMF独特即使设置违反定理3在这篇文章中。

如图4,类型的噪声大大影响误差曲线。介绍了应用噪声由于添加剂模型并不持有,例如,当图片或光谱,是可能影响噪声通过一个非线性函数的元素。介绍了这样一个非线性函数(15),实验表明,它能改善结果。寻找良好的非线性函数理论框架将有趣的调查。

节中定义的充分传播条件5有一个独特的NMF由于引理重要作用吗3。充分扩散假设是间接在相关领域也会导致独特的解决方案,例如,在[7]在groundedness假设会导致变量与一个足够样本空间传播。如果矩阵充分扩散,那么列会发生(几乎)单独列。德维尔(16)使用“发生”的假设,从而充分扩散假设,使盲源分离成为可能。

9。结论

我们已经调查了NMF的独特性从三个不同的观点如下:

(我)独特性在噪声免费的情况下;(2)底层模型的估计误差矩阵具有独特的NMF时添加噪声;和(3)潜在的导致矩阵的随机过程模型可以估计小错误。通过这样做,我们已经表明,它可以使许多新颖有用的特征,可以作为理论支撑使用大量NMF算法。几个开放问题可以发现在所有的三个观点,如果解决,会给一个更好的理解的非负矩阵因子分解。

附录

定理的证明4。这个定理,是一个独特的NMF。为了证明这一点,结果表明,条件定理1满足了。积极的象限是自对偶(),从而,在那里是一个订购单形锥包含。让的行向量是用。一个订购单形锥,,是一个闭集,因此它需要包含关闭用。两个项目的定义6强烈的边界可以新配方包含边界:
(1) 对所有,(2)向量是线性无关的。其余的遵循用归纳法证明。如果,然后因此是独一无二的。因此,让。然后线性无关的向量0是第一个元素,然后呢因此需要零基向量的第一个元素。换句话说,只有一个基向量的第一个元素非零。我们称这个向量。对所有有一个向量在第一个元素非负和零th元素,所以所有的元素除了第一个零。证明完成后通过观察,如果向量的第一个元素被删除,它仍然是强烈边界问题是因此关闭维问题。

定理的证明6。让是开放的对接近和, 让所有非负的集合对不在哪里。的独特性确保 对所有。弗罗贝尼乌斯规范是连续的,是一个封闭的有界集,上面的声明是积极的保证吗 从一个连续函数达到其限制在一个封闭的有界集17定理4.28)。的对不在哪里可以是由一个对角矩阵转变成一个矩阵对的,,拥有相同的产品也可以转换成一对,和有大的元素,即 ,从而。
选择是错误所需的解决方案可以有界。让是任何矩阵由一对非负矩阵不是。因为被选中时,。通过三角不等式,我们得到的 不是所有的解决方案因此有一个更大的错误并将不会错误的最小值。

确认

本研究项目智能支持的声音,丹麦技术研究委员会批准号26-02-0092。支持m·g·克里斯坦森的工作参数音频处理项目,丹麦研究委员会对技术和生产科学批准号274-06-0521。这部分工作是之前的一次会议上提出了(18]。

引用

1. d·d·李和h . s . Seung“学习对象的部分非负矩阵分解,“自然,卷401,不。6755年,第791 - 788页,1999年。视图:出版商的网站|谷歌学术搜索
2. d·d·李和h . s . Seung“非负矩阵分解算法,”先进的神经信息处理系统13麻省理工学院出版社,页556 - 562年,剑桥,质量,美国,2000年。视图:谷歌学术搜索
3. m·w·贝瑞·m·布朗,a . n . Langville v . p . Pauca和r . j . Plemmons”近似的非负矩阵分解算法和应用程序”,计算统计和数据分析,52卷,不。1,第173 - 155页,2007。视图:出版商的网站|谷歌学术搜索
4. 73 - 14 a·伯曼”问题,非负矩阵的秩分解,“暹罗审查,15卷,不。3,p。655年,1973年。视图:出版商的网站|谷歌学术搜索
5. l·托马斯,“解决问题73 - 14,非负矩阵分解,“暹罗审查,16卷,不。3、393 - 394年,1974页。视图:出版商的网站|谷歌学术搜索
6. d . Donoho诉Stodden,“什么时候非负矩阵分解给正确分解为部分吗?“在神经信息处理系统的进步16麻省理工学院出版社,页1141 - 1148年,剑桥,质量,美国,2004年。视图:谷歌学术搜索
7. m . Plumbley“非负独立分量分析的条件。”IEEE信号处理信件,9卷,不。6,177 - 180年,2002页。视图:出版商的网站|谷歌学术搜索
8. r·t·Rockafellar凸分析美国新泽西州普林斯顿大学,普林斯顿大学出版社,1970年版,1日。
9. h . Minc非负矩阵约翰·威利& Sons,纽约,纽约,美国第1版,1988年版。
10. g·h·戈卢布和c f . v .贷款,矩阵计算医学博士,巴尔的摩的约翰·霍普金斯大学出版社,第三版,1996年版。
11. p . Smaragdis和j·布朗”,非负矩阵分解为复调音乐转录,”《IEEE音频和声学信号处理应用的研讨会上发表(WASPAA ' 03)新帕,页177 - 180年,纽约,美国,2003年10月。视图:谷歌学术搜索
12. p·o·霍耶,”与稀疏约束非负矩阵分解,”机器学习的研究》杂志上5卷,第1469 - 1457页,2004年。视图:谷歌学术搜索
13. f·泰斯、k . Stadlthanner和t .田中,”第一个结果稀疏非负矩阵分解的唯一性,”13日欧洲信号处理研讨会论文集(EUSIPCO ' 05)2005年9月,土耳其安塔利亚。视图:谷歌学术搜索
14. h . Laurberg l·k·汉森,“仿射非负矩阵分解,”《IEEE国际会议音响、演讲和信号处理(ICASSP ' 07),卷2,页653 - 656,檀香山,夏威夷,美国,2007年4月。视图:出版商的网站|谷歌学术搜索
15. m·n·施密特j·拉森,这。萧,”风降噪使用非负稀疏编码,”《IEEE车间对机器学习信号处理(MLSP ' 07)塞萨洛尼基,页431 - 436年,2007年8月,希腊。视图:出版商的网站|谷歌学术搜索
16. y帝威,“时间和时频correlation-based盲源分离方法,”诉讼的第四届国际研讨会上独立分量分析和盲目的信号分离(ICA ' 03)奈良,页1059 - 1064年,日本,2003年4月。视图:谷歌学术搜索
17. t .很有数学分析美国,addison - wesley,阅读,质量,第二版,1974年版。
18. h . Laurberg“非负矩阵分解的唯一性”学报14 IEEE / SP车间在统计信号处理(SSP ' 07)美国威斯康星州麦迪逊,页44-48,2007年8月。视图:出版商的网站|谷歌学术搜索

版权

版权©2008汉斯Laurberg et al。这是一个开放的分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。