非負(fù)矩陣分解的自適應(yīng)單調(diào)投影Barzilai-Borwein算法

劉丹 黃亞魁

摘要 提出一種新的自適應(yīng)單調(diào)投影Barzilai-Borwein（BB）算法求解非負(fù)矩陣分解（NMF）。算法不使用任何線搜索，并利用自適應(yīng)BB步長(zhǎng)和梯度的利普希茨常數(shù)加速算法收斂。在適當(dāng)?shù)臈l件下，證明了算法的全局收斂性。此外，將算法應(yīng)用于稀疏對(duì)稱非負(fù)矩陣分解，數(shù)值實(shí)驗(yàn)表明算法是有效的。

關(guān) 鍵 詞 非負(fù)矩陣分解;交替最小二乘算法;自適應(yīng)投影Barzilai-Borwein算法;稀疏對(duì)稱非負(fù)矩陣分解

中圖分類號(hào) O29? ? ?文獻(xiàn)標(biāo)志碼 A

文章編號(hào)：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

首先，測(cè)試了隨機(jī)生成的NMF問(wèn)題。在MATLAB中使用rand函數(shù)隨機(jī)生成[m×n]的矩陣[V]，對(duì)每個(gè)[V]和給定的r，隨機(jī)生成10個(gè)不同的初始點(diǎn)[（W0，H0）]進(jìn)行測(cè)試。表1給出了由這些初始點(diǎn)得到的平均結(jié)果，其中Iter表示求解問(wèn)題（1）的迭代次數(shù)，Niter表示求解子問(wèn)題（2）和（3）的總迭代次數(shù)，Nproj表示投影的計(jì)算次數(shù)，Time表示求解問(wèn)題（1）花費(fèi)的CPU時(shí)間，Pgn表示[[?PHF（Wk，Hk），?PWF（Wk，Hk）T]F]的最終值，Residual表示[V-WkHkFVF]的最終值?？梢钥闯?，對(duì)不同維數(shù)的矩陣[V]，AMPBB算法在迭代次數(shù)、子迭代次數(shù)、投影的計(jì)算次數(shù)方面優(yōu)于其他3種算法，并且AMPBB算法花費(fèi)的CPU時(shí)間最少。此外，4種算法得到Pgn和Residual的結(jié)果相差不大。

其次，測(cè)試CBCL和ORL人臉圖像數(shù)據(jù)集。CBCL數(shù)據(jù)集包含2 429張人臉圖像且每張圖像的像素為19×19，該數(shù)據(jù)集可表示為1個(gè)361×2 429的矩陣。ORL數(shù)據(jù)集包含400張人臉圖像且每張圖像的像素為92×112，該數(shù)據(jù)集可表示成1個(gè)10 304×400的矩陣。表2給出4種算法使用10個(gè)隨機(jī)產(chǎn)生的初始點(diǎn)對(duì)這2個(gè)矩陣分解的平均結(jié)果。顯然，AMPBB算法投影的計(jì)算次數(shù)和CPU時(shí)間優(yōu)于其他3種算法。

2.2 稀疏symNMF問(wèn)題

本節(jié)測(cè)試稀疏symNMF問(wèn)題，將AMPBB與CDSSNMF[17]算法在數(shù)據(jù)集ORL、CBCL、Yale和Extended Yale上進(jìn)行比較。ORL數(shù)據(jù)集包含400張人臉圖像且每張圖像的像素裁剪為32×32，該數(shù)據(jù)集可表示成1個(gè)1 024×400的矩陣;CBCL數(shù)據(jù)集表示成一個(gè)361×2 429的矩陣;Yale數(shù)據(jù)集包含165張人臉圖像且每張圖像的像素為32×32，該數(shù)據(jù)集可表示成一個(gè)1 024×165的矩陣;Extended Yale數(shù)據(jù)集包含2 429張人臉圖像且每張圖像的像素為32×32，該數(shù)據(jù)集可表示成一個(gè)1 024×2 429的矩陣。令矩陣C為數(shù)據(jù)集得到的矩陣，對(duì)稱矩陣取[V=CCT]。參數(shù)選取[γ=5]和[λ=50]。為了公平起見(jiàn)，2種算法使用相同的終止條件，即最大迭代次數(shù)達(dá)到500次。圖2描繪了AMPBB與CDSSNMF算法的相對(duì)誤差隨迭代次數(shù)的變化?？梢钥闯?，與CDSSNMF算法相比，AMPBB算法的相對(duì)誤差更小。

3 結(jié)論

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

參考文獻(xiàn)：

[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.