Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization

Abstract

The separability assumption (Donoho & Stodden, 2003; Arora et al., 2012) turns non-negative matrix factorization (NMF) into a tractable problem. Recently, a new class of provably-correct NMF algorithms have emerged under this assumption. In this paper, we reformulate the separable NMF problem as that of finding the extreme rays of the conical hull of a finite set of vectors. From this geometric perspective, we derive new separable NMF algorithms that are highly scalable and empirically noise robust, and have several other favorable properties in relation to existing methods. A parallel implementation of our algorithm demonstrates high scalability on shared- and distributed-memory machines.

15 pages, 6 figures

References in corpus (4)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• A convex model for non-negative matrix factorization and dimensionality reduction on physical space
• Factoring nonnegative matrices with linear programs
• CUR from a Sparse Optimization Viewpoint

Cited by in corpus (31)

• Towards K-means-friendly Spaces: Simultaneous Deep Learning and Clustering
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• On Identifiability of Nonnegative Matrix Factorization
• Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• Compressed Nonnegative Matrix Factorization is Fast and Accurate
• Generalized Separable Nonnegative Matrix Factorization
• A Fast Gradient Method for Nonnegative Sparse Regression with Self Dictionary
• Dictionary-based Tensor Canonical Polyadic Decomposition
• Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability
• Scalable methods for nonnegative matrix factorizations of near-separable tall-and-skinny matrices
• Matrix Factorization at Scale: a Comparison of Scientific Data Analytics in Spark and C+MPI Using Three Case Studies
• Intersecting Faces: Non-negative Matrix Factorization With New Guarantees
• Learning Mixed Membership Mallows Models from Pairwise Comparisons
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Rank-One NMF-Based Initialization for NMF and Relative Error Bounds under a Geometric Assumption
• Necessary and Sufficient Conditions for Novel Word Detection in Separable Topic Models
• Towards a Near Universal Time Series Data Mining Tool: Introducing the Matrix Profile
• Divide-and-Conquer Learning by Anchoring a Conical Hull
• Mixed Membership Graph Clustering via Systematic Edge Query
• Necessary and Sufficient Conditions and a Provably Efficient Algorithm for Separable Topic Discovery
• How to Fake Multiply by a Gaussian Matrix
• Deep NMF Topic Modeling
• PD-ML-Lite: Private Distributed Machine Learning from Lighweight Cryptography
• Spectral Clustering by Ellipsoid and Its Connection to Separable Nonnegative Matrix Factorization
• Dirichlet Simplex Nest and Geometric Inference
• Convex Analysis of Mixtures for Separating Non-negative Well-grounded Sources
• Fast Clustering and Topic Modeling Based on Rank-2 Nonnegative Matrix Factorization
• Persistent Reductions in Regularized Loss Minimization for Variable Selection
• First Order Methods for Robust Non-negative Matrix Factorization for Large Scale Noisy Data