非負矩陣分解的自適應單調投影Barzilai-Borwein算法

劉丹 黃亞魁

摘要 提出一種新的自適應單調投影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數據集包含400張人臉圖像且每張圖像的像素裁剪為32×32，該數據集可表示成1個1 024×400的矩陣;CBCL數據集表示成一個361×2 429的矩陣;Yale數據集包含165張人臉圖像且每張圖像的像素為32×32，該數據集可表示成一個1 024×165的矩陣;Extended Yale數據集包含2 429張人臉圖像且每張圖像的像素為32×32，該數據集可表示成一個1 024×2 429的矩陣。令矩陣C為數據集得到的矩陣，對稱矩陣取[V=CCT]。參數選取[γ=5]和[λ=50]。為了公平起見，2種算法使用相同的終止條件，即最大迭代次數達到500次。圖2描繪了AMPBB與CDSSNMF算法的相對誤差隨迭代次數的變化。可以看出，與CDSSNMF算法相比，AMPBB算法的相對誤差更小。

3 結論

本文提出了一種新的自適應單調投影BB算法（AMPBB）求解非負矩陣分解（NMF）。AMPBB算法自適應地采用投影BB算法，當選取大步長[αBB1t]時，計算2次投影和梯度，這使得算法的目標函數值下降更快，投影的計算次數、迭代次數和消耗的CPU時間更少。此外，分析了算法的全局收斂性。數值實驗表明，AMPBB算法是有效的。進一步，AMPBB算法應用于稀疏對稱NMF，與CDSSNMF算法相比，AMPBB算法的相對誤差更小。

參考文獻：

[1]? ? LEE D D，SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature，1999，401（6755）：788-791.

[2]? ? STOEAN R，ATENCIARUIZ M A. Non-negative matrix factorization for medical imaging[C]// The European Symposium on Artificial Neural Networks，2018.

[3]? ? FU X，HUANG K J，SIDIROPOULOS N D，et al. Nonnegative matrix factorization for signal and data analytics：identifiability，algorithms，and applications[J]. IEEE Signal Processing Magazine，2019，36（2）：59-80.

[4]? ? BRUNET J P，TAMAYO P，GOLUB T R，et al. Metagenes and molecular pattern discovery using matrix factorization[J]. Proceedings of the National Academy of Sciences of the United States of America，2004，101（12）：4164-4169.

[5]? ? VAVASIS S A. On the complexity of nonnegative matrix factorization[J]. SIAM Journal on Optimization，2010，20（3）：1364-1377.

[6]? ? LEE D D，SEUNG H S. Algorithms for nonnegative matrix factorization[C]// Advances in Neural Information Processing Systems，2001，556-562.

[7]? ? BERRY M W，BROWNE M，LANGVILLE A N，et al. Algorithms and applications for approximate nonnegative matrix factorization[J]. Computational Statistics & Data Analysis，2007，52（1）：155-173.

[8]? ? PAATERO P，TAPPER U. Positive matrix factorization：a non-negative factor model with optimal utilization of error estimates of data values[J]. Environmetrics，1994，5（2）：111-126.

[9]? ? GRIPPO L，SCIANDRONE M. On the convergence of the block nonlinear Gauss-Seidel method under convex constraints[J]. Operations Research Letters，2000，26（3）：127-136.

[10]? LIN C J. Projected gradient methods for nonnegative matrix factorization[J]. Neural Computation，2007，19（10）：2756-2779.

[11]? GONG P H，ZHANG C S. Efficient nonnegative matrix factorization via projected Newton method[J]. Pattern Recognition，2012，45（9）：3557-3565.

[12]? HAN L X，NEUMANN M，PRASAD A U. Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization[J]. Electronic Transactions on Numerical Analysis，2010，36：54-82.

[13]? GUAN N Y，TAO D C，LUO Z G，et al. NeNMF：an optimal gradient method for nonnegative matrix factorization[J]. IEEE Transactions on Signal Processing，2012，60（6）：2882-2898.

[14]? HUANG Y K，LIU H W，ZHOU S S. Quadratic regularization projected Barzilai-Borwein method for nonnegative matrix factorization[J]. Data Mining and Knowledge Discovery，2015，29（6）：1665-1684.

[15]? HUANG Y K，LIU H W，ZHOU S. An efficient monotone projected Barzilai-Borwein method for nonnegative matrix factorization[J]. Applied Mathematics Letters，2015，45：12-17.

[16]? ZHOU B，GAO L，DAI Y H. Gradient methods with adaptive step-sizes[J]. Computational Optimization and Applications，2006，35（1）：69-86.

[17]? BELACHEW M T. Efficient algorithm for sparse symmetric nonnegative matrix factorization[J]. Pattern Recognition Letters，2019，125：735-741.

[18]? KUANG D，YUN S，PARK H. SymNMF：nonnegative low-rank approximation of a similarity matrix for graph clustering[J]. Journal of Global Optimization，2015，62（3）：545-574.

[19]? HE Z S，XIE S L，ZDUNEK R，et al. Symmetric nonnegative matrix factorization：algorithms and applications to probabilistic clustering[J]. IEEE Transactions on Neural Networks，2011，22（12）：2117-2131.

[20]? LANG L Y，JING X K. Application of Non-negative sparse matrix factorization in occluded face recognition[J]. Journal of Computers，2011，6（12）：2675-2679.

[21]? DOBROVOLSKYI H，KEBERLE N，TERNOVYY Y. Sparse symmetric nonnegative matrix factorization applied to face recognition[C]//2017 9th IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems：Technology and Applications （IDAACS）. September 21-23，2017，Bucharest，Romania. IEEE，2017：1042-1045.