Two Algorithms for Orthogonal Nonnegative Matrix Factorization with Application to Clustering

Abstract

Approximate matrix factorization techniques with both nonnegativity and orthogonality constraints, referred to as orthogonal nonnegative matrix factorization (ONMF), have been recently introduced and shown to work remarkably well for clustering tasks such as document classification. In this paper, we introduce two new methods to solve ONMF. First, we show athematical equivalence between ONMF and a weighted variant of spherical k-means, from which we derive our first method, a simple EM-like algorithm. This also allows us to determine when ONMF should be preferred to k-means and spherical k-means. Our second method is based on an augmented Lagrangian approach. Standard ONMF algorithms typically enforce nonnegativity for their iterates while trying to achieve orthogonality at the limit (e.g., using a proper penalization term or a suitably chosen search direction). Our method works the opposite way: orthogonality is strictly imposed at each step while nonnegativity is asymptotically obtained, using a quadratic penalty. Finally, we show that the two proposed approaches compare favorably with standard ONMF algorithms on synthetic, text and image data sets.

17 pages, 8 figures. New numerical experiments (document and synthetic data sets)

References in corpus (2)

• On Tensors, Sparsity, and Nonnegative Factorizations
• Two Algorithms for Orthogonal Nonnegative Matrix Factorization with Application to Clustering

Cited by in corpus (21)

• Two Algorithms for Orthogonal Nonnegative Matrix Factorization with Application to Clustering
• Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
• Deep matrix factorizations
• A Nonlinear Orthogonal Non-Negative Matrix Factorization Approach to Subspace Clustering
• Community detection in multiplex networks based on orthogonal nonnegative matrix tri-factorization
• Block Alternating Bregman Majorization Minimization with Extrapolation
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Deep Approximately Orthogonal Nonnegative Matrix Factorization for Clustering
• Orthogonal symmetric non-negative matrix factorization under the stochastic block model
• Long-Term Identity-Aware Multi-Person Tracking for Surveillance Video Summarization
• Matrix cofactorization for joint spatial-spectral unmixing of hyperspectral images
• Bearing damage detection with orthogonal and non-negative low-rank feature extraction
• Matrix Cofactorization for Joint Representation Learning and Supervised Classification -- Application to Hyperspectral Image Analysis
• Structured Nonnegative Matrix Factorization for Traffic Flow Estimation of Large Cloud Networks
• Approximation Algorithms for Orthogonal Non-negative Matrix Factorization
• Alternating Iteratively Reweighted Minimization Algorithms for Low-Rank Matrix Factorization
• Orthogonal Nonnegative Matrix Factorization with the Kullback-Leibler divergence
• Document Clustering Games in Static and Dynamic Scenarios
• Improved Conic Reformulations for K-means Clustering
• Orthogonal Nonnegative Tucker Decomposition