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 language | English (US) |
|---|---|
| Article number | 7879849 |
| Pages (from-to) | 3120-3135 |
| Number of pages | 16 |
| Journal | IEEE Transactions on Signal Processing |
| Volume | 65 |
| Issue number | 12 |
| DOIs | |
| State | Published - 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