求解非负矩阵分解的修正非单调投影梯度法.pdf

第37卷 第6期 应 用 数 学 学 报 Vo1．37No．6 2014年 11月 ACTAMATHEMATICAEAPPLICATAESINICA Nov．，2014 求解非负矩阵分解的修正 非单调投影梯度法 李向利 f桂林电子科技大学数学与计算科学学院，桂林 541004) (E—mail：lixiangli213@gmail．coiY1) 刘红卫 (西安电子科技大学数学与统计学院，西安710071) 摘 要 非负矩阵分解 (NMF)是一新的特征提取方法．十几年来，NMF备受关注，并且被成 功的应用于许多数据分析问题．非负矩阵分解 目前的算法大部分是基于乘性算法，交替的最小 二乘算法．然而，这些算法的收敛性都不能得到保证，这归咎于聚点的存在性不清楚．本文提 出了—修正的非单调投影梯度算法求解 NMF．该方法能保证投影梯度算法产生的点列至少有一 聚点．数据实验表明该方法要比乘性算法好． 关键词 非负矩阵分解；修正的投影梯度法；非单调技巧 MR(2000)主题分类 62G05；62N01 中图分类 029 1 前言 非负矩阵分解有着广泛的应用，包括文本挖掘 [1】，子系统识别 癌症类发现 [。 天文图像 [6】j音乐转录 [7]．神经生物学 (基因的分离)【一引，和数据分析 (模式识别，分割， 聚类，降维)(见 [10—20])． 非负矩阵分解问题可描述如下：给一非负矩阵A∈R ，找到一分解使得 A ≈ 日 (1．1) 这里 和 H分别是维数为 m ×r和 r×佗的非负矩阵．r通常选择使得r《mn．一 本文 2012年 1O月 25日收到．2013年 2月 27日收到修改稿． 国家 自然科学基金 (No61362021)，广西 自然科学基金 (No．PF141259)，广西杰出青年基金 (No．2012GXSFFA060003)和广西教育厅重点 (No．LD14075B)资助项 目． 6期 李向利，刘红卫：求解非负矩阵分解的修正非单调投影梯度法 1069 般的，转化 (1．1)为如下优化问题： minF(W,H)三 —WHIIF2， s．t． 日 0． (1．2) 这里 H 0表示 和 日里的每个元素都是非负的， l1． 是 F一范数． 自从 1999年 NMF被 Lee，Seung[]提出后，就得到了许多研究者的关注，例如 Paatero和 Tapper[．目前存在的大部分算法都是基于乘性算法 [21,23]和交替的最小二 乘算法 [22]．尽管这些方法有其优点，但他们都缺少收敛性分析．究其原因，聚点的存在 性不清楚．在 2『4]中，Lin对乘性算法提出了一种修正策略，在这个策略里，如果 的 整列全是零，则对应的H行不变．这个修正的策略能保证修正点列是有界的．此外， Lin已经证明了修正点列的任何聚点是 (1．2)的稳定点． 设X=( )，Q={X∈R( )I 0}，则 (1．2)可转化为如下形式： min，()， s．t．X ∈Q． (1．3) 如果 (1．3)满足 (x 一Vf(X ))一X =0， (1．41 则 X是 (1．3)的一稳定点，其中 = ( (-)为Q上的正交投影算子．显然， (1．4)等价于下面的互补系统：