Multi-agent solver for non-negative matrix factorization based on optimization

Tu, Zhipeng ; Li, Weijian

Kybernetika, Tome 57 (2021) no. 1, pp. 60-77

Abstract (VO)

This paper investigates a distributed solver for non-negative matrix factorization (NMF) over a multi-agent network. After reformulating the problem into the standard distributed optimization form, we design our distributed algorithm (DisNMF) based on the primal-dual method and in the form of multiplicative update rule. With the help of auxiliary functions, we provide monotonic convergence analysis. Furthermore, we show by computational complexity analysis and numerical examples that our distributed NMF algorithm performs well in comparison with the centralized NMF algorithm.

Détail

DOI : 10.14736/kyb-2021-1-0060

Classification : 15A23, 68W15
Keywords: distributed optimization; non-negative matrix factorization; multiplicative update rules; multi-agent network

Bibliographie

[1] Bertsekas, D. P., Tsitsiklis, J. W.: Parallel and Distributed Computation: Numerical Methods. Prentice hall Englewood Cliffs, NJ 1989. | DOI | MR

[2] Cai, D., He, X., Han, J., Huang, T. S.: Graph regularized nonnegative matrix factorization for data representation. IEEE Trans. Pattern Analysis Machine Intell. 33 (2010), 1548-1560. | DOI

[3] Deng, W., Zeng, X., Hong, Y.: Distributed computation for solving the sylvester equation based on optimization. IEEE Control Systems Lett. 4 (2019), 414-419. | DOI | MR

[4] Godsil, Ch., Royle, G. F.: Algebraic graph theory. Springer Science Business Media 207 (2013). | MR

[5] He, X., Kan, M.-Y., Xie, P., Chen, X.: Comment-based multi-view clustering of web 2.0 items. In: Proc. 23rd International Conference on World wide web, 2014, pp. 771-782. | DOI

[6] Horst, R., Tuy, H.: Global Optimization. Springer-Verlag, Berlin 1996. | DOI | MR

[7] Huang, K., Sidiropoulos, N. D., Swami, A.: Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition. IEEE Trans. Signal Process. 62 (2013), 211-224. | DOI | MR

[8] Jain, P., Kar, P.: Non-convex optimization for machine learning. arXiv preprint arXiv:1712.07897, 2017. | DOI

[9] Kim, H., Park, H.: Nonnegative matrix factorization based on alternating non-negativity constrained least squares and active set method. SIAM J. Matrix Analysis Appl. 30 (2008), 713-730. | DOI | MR

[10] Lee, D. L., Seung, H. S.: Learning the parts of objects by non-negative matrix factorization. Nature 401 (1999), 788-791. | DOI

[11] Lee, D. S., Seung, H. S.: Algorithms for non-negative matrix factorization. Adv. Neural Inform. Process. Systems xx (2001), 556-562.

[12] Li, W., Zeng, X., Hong, Y., Ji, H.: Distributed Design for nuclear norm minimization of linear matrix equation with constraints. IEEE Trans. Automat. Control(2020). | DOI | MR

[13] Lin, Ch.-J.: Projected gradient methods for nonnegative matrix factorization. Neural Comput. 19 (2007), 2756-2779. | DOI | MR

[14] Liu, Ch., Yang, H.-Ch., Fan, J., He, L.-W., Wang, Y.-M.: Distributed nonnegative matrix factorization for web-scale dyadic data analysis on mapreduce. In: Proc. 19th International Conference on World wide web (2010), pp. 681-690. | DOI

[15] Liu, J., Wang, Ch., Gao, J., Han, J.: Multi-view clustering via joint nonnegative matrix factorization. In: Proc. 2013 SIAM International Conference on Data Mining, SIAM 2013, pp. 252-260. | DOI

[16] Nedic, A., A, Ozdaglar, Parrilo, P. A.: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 922-938. | DOI | MR

[17] Peterka, V.: Bayesian system identification. In: Trends and Progress in System Identification (P. Eykhoff, ed.), Pergamon Press, Oxford 1981, pp. 239-304. | DOI | MR | Zbl

[18] Qiu, Z., Liu, S., Xie, L.: Distributed constrained optimal consensus of multi-agent systems. Automatica 68 (2016), 209-215. | DOI | MR

[19] Ram, S. S., Nedić, A., Veeravalli, V. V.: Distributed stochastic subgradient projection algorithms for convex optimization. J. Optim. Theory Appl. 147 (2010), 516-545. | DOI | MR

[20] Shi, G., Anderson, B. D. O., Helmke, U.: Network flows that solve linear equations. IEEE Trans. Automat. Control 62 (2017), 2659-2674. | DOI | MR

[21] Wen, Z., Yin, W., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Programm. Comput. 4 (2012), 333-361. | DOI | MR

[22] Xu, F., He, G.: New algorithms for nonnegative matrix completion. Pacific J. Optim. 11 (2015), 459-469. | MR

[23] Yang, S., Liu, Q., Wang, J.: A multi-agent system with a proportional-integral protocol for distributed constrained optimization. IEEE Trans. Automat. Control 62 (2016), 3461-3467. | DOI | MR

[24] Yi, P., Hong, Y., Liu, F.: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Systems Control Lett. 83 (2015), 45-52. | DOI | MR | Zbl

[25] Yin, J., Gao, L., Zhang, Z. M.: Scalable nonnegative matrix factorization with block-wise updates. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer-Heidelberg, Berlin 2014, pp. 337-352. | DOI

[26] Yuan, D., Ho, D. W. C., Xu, S.: Regularized primal-dual subgradient method for distributed constrained optimization. IEEE Trans. Cybernet. 46 (2015), 2109-2118. | DOI

[27] Zeng, X., Cao, K.: Computation of linear algebraic equations with solvability verification over multi-agent networks. Kybernetika 53 (2017), 803-819. | DOI | MR

[28] Zeng, X., Yi, P., Hong, Y.: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2016), 5227-5233. | DOI | MR

[29] Zeng, X., Liang, S., Hong, Y., Chen, J.: Distributed computation of linear matrix equations: An optimization perspective. IEEE Trans. Automat. Control 64 (2019), 1858-1873. | DOI | MR