Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization

doi:10.1007/s40305-020-00322-9

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (2): 327-345.doi: 10.1007/s40305-020-00322-9

• Special Issue: Machine Learning and Optimization Algorithm • Previous Articles Next Articles

Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization

Yong-Yong Chen, Fang-Fang Xu

College of Mathematics and Systems Science, Shandong University of Science and Technology, Qingdao 266590, Shandong, China

Received:2019-11-26 Revised:2020-06-07 Online:2023-06-30 Published:2023-05-24
Contact: Fang-Fang Xu, Yong-Yong Chen E-mail:xuff@sdust.edu.cn;yongyongchen.cn@gmail.com
Supported by:
the National Natural Science Foundation of China (No. 11901359), and Shandong Provincial Natural Science Foundation (No. ZR2019QA017)

Abstract

Abstract: Orthogonal nonnegative matrix factorization (ONMF) is widely used in blind image separation problem, document classification, and human face recognition. The model of ONMF can be efficiently solved by the alternating direction method of multipliers and hierarchical alternating least squares method. When the given matrix is huge, the cost of computation and communication is too high. Therefore, ONMF becomes challenging in the large-scale setting. The random projection is an efficient method of dimensionality reduction. In this paper, we apply the random projection to ONMF and propose two randomized algorithms. Numerical experiments show that our proposed algorithms perform well on both simulated and real data.

Key words: Orthogonal nonnegative matrix factorization, Random projection method, Dimensionality reduction, Augmented lagrangian method, Hierarchical alternating least squares algorithm

CLC Number:

68W20
90C06

Yong-Yong Chen, Fang-Fang Xu. Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization[J]. Journal of the Operations Research Society of China, 2023, 11(2): 327-345.

TrendMD

References

[1] Choi, S.:Algorithms for orthogonal nonnegative matrix factorization. IEEE International Joint Conference on Neural Networks. pp. 1828-1832. IEEE Press, Hong Kong (2008)
[2] Ding, C., Li, T., Peng, W., Park, H.:Orthogonal nonnegative matrix t-factorizations for clustering. In:Twelfth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 126-135. ACM Press, Philadelphia (2006)
[3] Li, X., Cui, G., Dong, Y.:Discriminative and orthogonal subspace constraints-based nonnegative matrix factorization. ACM Trans. Intell. Syst. Technol. 9(6), Article No. 65(2019)
[4] Mirzal, A.:Orthogonal nonnegative matrix factorization for blind image separation. In:International Visual Informatics Conference, pp. 25-35. Springer, Cham (2013)
[5] Tolic, D., Antulov-Fantulin, N., Kopriva, I.:A nonlinear orthogonal non-negative matrix factorization approach to subspace clustering. Pattern Recogn. 82, 40-55(2018)
[6] Wen, Z., Yin, W.:A feasible method for optimization with orthogonality constraints. Math. Program. 142(1), 397-434(2013)
[7] Li, B., Zhou, G., Cichocki, A.:Two efficient algorithms for approximately orthogonal nonnegative matrix factorization. IEEE Signal Process. Lett. 22(7), 843-846(2015)
[8] Li, P., Bu, J., Yang, Y., Ji, R., Chen, C., Cai, D.:Discriminative orthogonal nonnegative matrix factorization with flexibility for data representation. Expert Syst. Appl. 41(4), 1283-1293(2017)
[9] Li, Z., Wu, X., Peng, H.:Nonnegative matrix factorization on orthogonal subspace. Pattern Recogn. Lett. 31(9), 905-911(2010)
[10] Mirzal, A.:A convergent algorithm for orthogonal nonnegative matrix factorization. J. Comput. Appl. Math. 260(2), 149-166(2014)
[11] Ye, J., Jin, Z.:Nonnegative matrix factorization on orthogonal subspace with smoothed L₀ norm constrained. In:Yang, J., Fang, F., Sun, C. (eds.) Intelligent Science and Intelligent Data Engineering. IScIDE 2012. Lecture Notes in Computer Science, vol. 7751. Springer, Berlin (2013)
[12] Yoo, J., Choi, S.:Orthogonal nonnegative matrix factorization:multiplicative updates on Stiefel manifolds. In:Yang, J., Fang, F., Sun, C. (eds.) Intelligent Data Engineering and Automated Learning-IDEAL 2008, vol. 5326, pp. 140-147. Springer, Daejeon (2008)
[13] Pompili, F., Gillis, N., Absil, P.A., Glineur, F.:Two algorithms for orthogonal nonnegative matrix factorization with application to clustering. Neurocomputing 141, 15-25(2014)
[14] Jin, Q.G., Liang, G.L.:Fast hierarchical alternating nonnegative least squares algorithm for nonnegative matrix factorization. Comput. Simul. 29(11), 174-185(2012)
[15] Kimura, K., Kudo, M., Tanaka, Y.:A column-wise update algorithm for nonnegative matrix factorization in Bregman divergence with an orthogonal constraint. Mach. Learn. 103(2), 285-306(2017)
[16] Kimura, K., Tanaka, Y., Kudo, M.:A fast hierarchical alternating least squares algorithm for orthogonal nonnegative matrix factorization. In:Phung, D., Li, H. (eds.) Proceedings of the Sixth Asian Conference on Machine Learning, vol. 39, pp. 129-141(2014)
[17] Drineas, P., Mahoney, M.W.:Randnla:randomized numerical linear algebra. Commun. ACM 59(6), 80-90(2016)
[18] Erichson, N.B., Mendible, A., Wihlborn, S., Kutz, J.N.:Randomized nonnegative matrix factorization. Pattern Recogn. Lett. 104, 1-7(2018)
[19] Erichson, N.B., Voronin, S., Brunton, S.L., Kutz, J.N.:Randomized matrix decompositions using R. J. Stat, Softw 89(11), 1-48(2019). https://doi.org/10.18637/jss.v089.i11
[20] Halko, N., Martinsson, P.G., Tropp, J.A.:Finding structure with randomness:probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217-288(2009)
[21] Ghashami, M., Liberty, E., Phillips, J.M., Woodruff, D.P.:Frequent directions:simple and deterministic matrix sketching. SIAM J. Comput. 45(5), 1762-1792(2016)
[22] Tepper, M., Sapiro, G.:Compressed nonnegative matrix factorization is fast and accurate. IEEE Trans. Signal Process. 64(9), 2269-2283(2016)
[23] Lin, C.J.:Projected gradient methods for nonnegative matrix factorization. Neural Comput. 19(10), 2756-2779(2007)
[24] Lin, L., Liu, Z.Y.:An alternating projected gradient algorithm for nonnegative matrix factorization. Appl. Math. Comput. 217(24), 9997-10002(2011)
[25] Dai, Y.H., Han, D.R., Yuan, X.M., Zhang, W.X.:A sequential updating scheme of the Lagrange multiplier for separable convex programming. Math. Comput. 86, 315-343(2017)
[26] Deng, W., Yin, W.:On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889-916(2016)
[27] Sun, D., Toh, K.C., Yang, L.:A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type of constraints. SIAM J. Optim. 25, 882-915(2015)
[28] Wu, Z., Li, M., Wang, D.Z.W., Han, D.:A symmetric alternating direction Method of multipliers for separable nonconvex minimization problems. Asia Pac. J. Oper. Res. 34(6), 1-27(2017)
[29] Yang, J., Zhang, Y.:Alternating direction algorithms for 1-problems in compressive sensing. SIAM J. Sci. Comput. 33(1), 250-278(2009)
[30] Wang, X., Xie, X., Lu, L.:An effective initialization for orthogonal nonnegative matrix factorization. J. Comput. Math. 30(1), 34-46(2012)
[31] Nie, F., Xu, D., Li, X.:Initialization independent clustering with actively self-training method. IEEE Trans. Syst. Man Cybern. B Cybern. 42(1), 17-27(2012)

Randomized Algorithms for Orthogonal Nonnegative Matrix Factorization

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 2

Recommended Articles

Metrics

Comments

[1]	Ying Cui, Chao Ding, Xu-Dong Li, Xin-Yuan Zhao. Augmented Lagrangian Methods for Convex Matrix Optimization Problems [J]. Journal of the Operations Research Society of China, 2022, 10(2): 305-342.
[2]	Shi-qian Ma. Alternating Direction Method of Multipliers for Sparse Principal Component Analysis [J]. Journal of the Operations Research Society of China, 2013, 1(2): 253-.