Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization

Abstract

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 H{H}^T$. SymNMF can be used for data analysis and in particular for various clustering tasks. In this paper, we propose simple and very efficient coordinate descent schemes to solve this problem, and that can handle large and sparse input matrices. The effectiveness of our methods is illustrated on synthetic and real-world data sets, and we show that they perform favorably compared to recent state-of-the-art methods.

25 pages, 5 figures, 7 tables. Main changes: comparison with another symNMF algorithm (namely, BetaSNMF), and correction of an error in the convergence proof

References in corpus (1)

• Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization

Cited by in corpus (15)

• Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization
• A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
• Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation
• Inexact Block Coordinate Descent Methods For Symmetric Nonnegative Matrix Factorization
• Synchronisation of Partial Multi-Matchings via Non-negative Factorisations
• Coordinate-wise descent methods for leading eigenvalue problem
• Algorithms for Positive Semidefinite Factorization
• Similarity Preserving Representation Learning for Time Series Clustering
• Quartic First-Order Methods for Low-Rank Minimization
• On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations
• Multilabel Classification by Hierarchical Partitioning and Data-dependent Grouping
• Exterior Point Method for Completely Positive Factorization
• Tangent Space Based Alternating Projections for Nonnegative Low Rank Matrix Approximation
• A Decomposition Algorithm for the Sparse Generalized Eigenvalue Problem
• Estimating the covariance structure of heterogeneous SIS epidemics on networks