Kybernetika 57 no. 1, 60-77, 2021

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

Zhipeng Tu and Weijian LiDOI: 10.14736/kyb-2021-1-0060

Abstract:

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.

Keywords:

distributed optimization, multi-agent network, non-negative matrix factorization, multiplicative update rules

Classification:

15A23, 68W15

paper.pdf

References:

  1. D. P. Bertsekas and J. W. Tsitsiklis: Parallel and Distributed Computation: Numerical Methods. Prentice hall Englewood Cliffs, NJ 1989.   DOI:10.1109/TPAMI.2010.231
  2. D. Cai, X. He, J. Han and T. S. Huang: Graph regularized nonnegative matrix factorization for data representation. IEEE Trans. Pattern Analysis Machine Intell. 33 (2010), 1548-1560.   DOI:10.1109/TPAMI.2010.231
  3. W. Deng, X. Zeng and Y. Hong: Distributed computation for solving the sylvester equation based on optimization. IEEE Control Systems Lett. 4 (2019), 414-419.   DOI:10.1109/LCSYS.2019.2942711
  4. Ch. Godsil and G. F. Royle: Algebraic graph theory. Springer Science Business Media 207 (2013).   CrossRef
  5. X. He, M.-Y. Kan, P. Xie and X. Chen: Comment-based multi-view clustering of web 2.0 items. In: Proc. 23rd International Conference on World wide web, 2014, pp. 771-782.   DOI:10.1145/2566486.2567975
  6. R. Horst and H. Tuy: Global Optimization. Springer-Verlag, Berlin 1996.   DOI:10.1007/978-3-662-03199-5
  7. K. Huang, N. D. Sidiropoulos and A. Swami: Non-negative matrix factorization revisited: Uniqueness and algorithm for symmetric decomposition. IEEE Trans. Signal Process. 62 (2013), 211-224.   DOI:10.1109/TSP.2013.2285514
  8. P. Jain and P. Kar: Non-convex optimization for machine learning. arXiv preprint arXiv:1712.07897, 2017.   DOI:10.1561/9781680833690
  9. H. Kim and H. Park: 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:10.1137/07069239X
  10. D. L. Lee and H. S. Seung: Learning the parts of objects by non-negative matrix factorization. Nature 401 (1999), 788-791.   DOI:10.1038/44565
  11. D. S. Lee and H. S. Seung: Algorithms for non-negative matrix factorization. Adv. Neural Inform. Process. Systems xx (2001), 556-562.   CrossRef
  12. W. Li, X. Zeng, Y. Hong and H. Ji: Distributed Design for nuclear norm minimization of linear matrix equation with constraints. IEEE Trans. Automat. Control(2020).   DOI:10.1109/TAC.2020.2981930
  13. Ch.-J. Lin: Projected gradient methods for nonnegative matrix factorization. Neural Comput. 19 (2007), 2756-2779.   DOI:10.1162/neco.2007.19.10.2756
  14. Ch. Liu, H.-Ch. Yang, J. Fan, L.-W. He and Y.-M. Wang: 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:10.1145/1772690.1772760
  15. J. Liu, Ch. Wang, J. Gao and J. Han: Multi-view clustering via joint nonnegative matrix factorization. In: Proc. 2013 SIAM International Conference on Data Mining, SIAM 2013, pp. 252-260.   DOI:10.1137/1.9781611972832.28
  16. A. Nedic, A, Ozdaglar and P. A. Parrilo: Constrained consensus and optimization in multi-agent networks. IEEE Trans. Automat. Control 55 (2010), 922-938.   DOI:10.1109/TAC.2010.2041686
  17. V. Peterka: Bayesian system identification. In: Trends and Progress in System Identification (P. Eykhoff, ed.), Pergamon Press, Oxford 1981, pp. 239-304.   DOI:10.1016/B978-0-08-025683-2.50013-2
  18. Z. Qiu, S. Liu and L. Xie: Distributed constrained optimal consensus of multi-agent systems. Automatica 68 (2016), 209-215.   DOI:10.1016/j.automatica.2016.01.055
  19. S. S. Ram, A. Nedić and V. V. Veeravalli: Distributed stochastic subgradient projection algorithms for convex optimization. J. Optim. Theory Appl. 147 (2010), 516-545.   DOI:10.1007/s10957-010-9737-7
  20. G. Shi, B. D. O. Anderson and U. Helmke: Network flows that solve linear equations. IEEE Trans. Automat. Control 62 (2017), 2659-2674.   DOI:10.1109/TAC.2016.2612819
  21. Z. Wen, W. Yin and Y. Zhang: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Programm. Comput. 4 (2012), 333-361.   DOI:10.1007/s12532-012-0044-1
  22. F. Xu and G. He: New algorithms for nonnegative matrix completion. Pacific J. Optim. 11 (2015), 459-469.   CrossRef
  23. S. Yang, Q. Liu and J. Wang: A multi-agent system with a proportional-integral protocol for distributed constrained optimization. IEEE Trans. Automat. Control 62 (2016), 3461-3467.   DOI:10.1109/TAC.2016.2610945
  24. P. Yi, Y. Hong and F. Liu: Distributed gradient algorithm for constrained optimization with application to load sharing in power systems. Systems Control Lett. 83 (2015), 45-52.   DOI:10.1016/j.sysconle.2015.06.006
  25. J. Yin, L. Gao and Z. M. Zhang: 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:10.1007/978-3-662-44845-8\_22
  26. D. Yuan, D. W. C. Ho and S. Xu: Regularized primal-dual subgradient method for distributed constrained optimization. IEEE Trans. Cybernet. 46 (2015), 2109-2118.   DOI:10.1109/TCYB.2015.2464255
  27. X. Zeng and K. Cao: Computation of linear algebraic equations with solvability verification over multi-agent networks. Kybernetika 53 (2017), 803-819.   DOI:10.14736/kyb-2017-5-0803
  28. X. Zeng, P. Yi and Y. Hong: Distributed continuous-time algorithm for constrained convex optimizations via nonsmooth analysis approach. IEEE Trans. Automat. Control 62 (2016), 5227-5233.   DOI:10.1109/TAC.2016.2628807
  29. X. Zeng, S. Liang, Y. Hong and J. Chen: Distributed computation of linear matrix equations: An optimization perspective. IEEE Trans. Automat. Control 64 (2019), 1858-1873.   DOI:10.1109/TAC.2018.2847603