A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
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.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringCommunity DetectionImage SegmentationSemantic SegmentationSimilar Papers 제목 키워드 기반
Frank-Wolfe Optimization for Symmetric-NMF under Simplicial Constraint
Symmetric nonnegative matrix factorization has found abundant applications in various domains by providing a symmetric low-rank decomposition of nonnegative matrices. In this paper we propose a Frank-Wolfe (FW) solver to…
ClusteringA Provable Splitting Approach for Symmetric Nonnegative Matrix Factorization
The symmetric Nonnegative Matrix Factorization (NMF), a special but important class of the general NMF, has found numerous applications in data analysis such as various clustering tasks. Unfortunately, designing fast alg…
ClusteringImage ClusteringVocal Bursts Type PredictionDropping Symmetry for Fast Symmetric Nonnegative Matrix Factorization
Symmetric nonnegative matrix factorization (NMF), a special but important class of the general NMF, is demonstrated to be useful for data analysis and in particular for various clustering tasks. Unfortunately, designing …
ClusteringImage ClusteringRethinking Symmetric Matrix Factorization: A More General and Better Clustering Perspective
Nonnegative matrix factorization (NMF) is widely used for clustering with strong interpretability. Among general NMF problems, symmetric NMF is a special one that plays an important role in graph clustering where each el…
ClusteringGraph ClusteringCoordinate Descent Methods for Symmetric Nonnegative Matrix Factorization
Given a symmetric nonnegative matrix $A$, symmetric nonnegative matrix factorization (symNMF) is the problem of finding a nonnegative matrix $H$, usually with much fewer columns than $A$, such that $A \approx HH^T$. SymN…
Clustering