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

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 which guarantee the global and local optimality of the obtained solutions. Extensive numerical results performed on both synthetic and real data sets suggest that the proposed algorithm converges quickly to a local minimum solution.

IEEE Transactions on Signal Processing (to appear)

References in corpus (12)

• An Alternating Direction Algorithm for Matrix Completion with Nonnegative Factors
• Decomposition by Partial Linearization: Parallel Optimization of Multi-Agent Systems
• Guaranteed Matrix Completion via Non-convex Factorization
• Global convergence of splitting methods for nonconvex composite optimization
• Bilinear Generalized Approximate Message Passing
• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Parallel Successive Convex Approximation for Nonsmooth Nonconvex Optimization
• Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problems
• Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization

Cited by in corpus (7)

• Inexact Block Coordinate Descent Methods For Symmetric Nonnegative Matrix Factorization
• Sparse Phase Retrieval via Truncated Amplitude Flow
• An inner-loop free solution to inverse problems using deep neural networks
• InverseNet: Solving Inverse Problems with Splitting Networks
• On the Sublinear Convergence of Randomly Perturbed Alternating Gradient Descent to Second Order Stationary Solutions
• Two-Dimensional Tomography From Noisy Projection Tilt Series Taken At Unknown View Angles With Non-Uniform Distribution
• An Incremental Path-Following Splitting Method for Linearly Constrained Nonconvex Nonsmooth Programs