刘丹 黄亚魁

摘要 提出一种新的自适应单调投影Barzilai-Borwein（BB）算法求解非负矩阵分解（NMF）。算法不使用任何线搜索，并利用自适应BB步长和梯度的利普希茨常数加速算法收敛。在适当的条件下，证明了算法的全局收敛性。此外，将算法应用于稀疏对称非负矩阵分解，数值实验表明算法是有效的。

关 键 词 非负矩阵分解;交替最小二乘算法;自适应投影Barzilai-Borwein算法;稀疏对称非负矩阵分解

中图分类号 O29     文献标志码 A

文章编号：1007-2373（2021）06-0044-07

Abstract We present a new efficient adaptive monotone projected Barzilai-Borwein （BB） method for nonnegative matrix factorization （NMF）. Our method adaptively adopts the BB stepsizes without using any line search. The Lipschitz constant of gradient is exploited to accelerate convergence. Global convergence of the proposed method is established under mild conditions. Moreover， our method is applied to sparse symmetric NMF. Experimental results show that our method is promising.

Key words nonnegative matrix factorization; alternating nonnegative least squares; adaptive projected Barzilai-Borwein method; sparse symmetric nonnegative matrix factorization

首先，测试了随机生成的NMF问题。在MATLAB中使用rand函数随机生成[m×n]的矩阵[V]，对每个[V]和给定的r，随机生成10个不同的初始点[（W0，H0）]进行测试。表1给出了由这些初始点得到的平均结果，其中Iter表示求解问题（1）的迭代次数，Niter表示求解子問题（2）和（3）的总迭代次数，Nproj表示投影的计算次数，Time表示求解问题（1）花费的CPU时间，Pgn表示[[∇PHF（Wk，Hk），∇PWF（Wk，Hk）T]F]的最终值，Residual表示[V-WkHkFVF]的最终值。可以看出，对不同维数的矩阵[V]，AMPBB算法在迭代次数、子迭代次数、投影的计算次数方面优于其他3种算法，并且AMPBB算法花费的CPU时间最少。此外，4种算法得到Pgn和Residual的结果相差不大。

其次，测试CBCL和ORL人脸图像数据集。CBCL数据集包含2 429张人脸图像且每张图像的像素为19×19，该数据集可表示为1个361×2 429的矩阵。ORL数据集包含400张人脸图像且每张图像的像素为92×112，该数据集可表示成1个10 304×400的矩阵。表2给出4种算法使用10个随机产生的初始点对这2个矩阵分解的平均结果。显然，AMPBB算法投影的计算次数和CPU时间优于其他3种算法。

2.2 稀疏symNMF问题

本节测试稀疏symNMF问题，将AMPBB与CDSSNMF[17]算法在数据集ORL、CBCL、Yale和Extended Yale上进行比较。ORL数……