A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality

Songtao Lu, Mingyi Hong, Zhengdao Wang

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

Symmetric nonnegative matrix factorization (SymNMF) has important applications in data analytics problems such as document clustering, community detection, and image segmentation. In this paper, we propose a novel nonconvex variable splitting method for solving SymNMF. The proposed algorithm is guaranteed to converge to the set of Karush-Kuhn-Tucker (KKT) points of the nonconvex SymNMF problem. Furthermore, it achieves a global sublinear convergence rate. We also show that the algorithm can be efficiently implemented in parallel. Further, sufficient conditions are provided that guarantee the global and local optimality of the obtained solutions. Extensive numerical results performed on both synthetic and real datasets suggest that the proposed algorithm converges quickly to a local minimum solution.

Original languageEnglish (US)
Article number7879849
Pages (from-to)3120-3135
Number of pages16
JournalIEEE Transactions on Signal Processing
Volume65
Issue number12
DOIs
StatePublished - Jun 15 2017

Bibliographical note

Funding Information:
This work was supported in part by the National Science Foundation under Grant 1523374 and Grant 1526078 and in part by the Air Force Office of Scientific Research under Grant 15RT0767. This paper was presented in part at the 42nd IEEE International Conference on Acoustics, Speech, and Signal Processing, New Orleans, LA, USA, March 2017.

Publisher Copyright:
© 1991-2012 IEEE.

Keywords

  • Karush-Kuhn-Tucker points
  • Symmetric nonnegative matrix factorization
  • clustering
  • global and local optimality
  • variable splitting

Fingerprint Dive into the research topics of 'A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality'. Together they form a unique fingerprint.

Cite this