Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability

Abstract

We present a numerical algorithm for nonnegative matrix factorization (NMF) problems under noisy separability. An NMF problem under separability can be stated as one of finding all vertices of the convex hull of data points. The research interest of this paper is to find the vectors as close to the vertices as possible in a situation in which noise is added to the data points. Our algorithm is designed to capture the shape of the convex hull of data points by using its enclosing ellipsoid. We show that the algorithm has correctness and robustness properties from theoretical and practical perspectives; correctness here means that if the data points do not contain any noise, the algorithm can find the vertices of their convex hull; robustness means that if the data points contain noise, the algorithm can find the near-vertices. Finally, we apply the algorithm to document clustering, and report the experimental results.

29 pages, 6 figures. Minor revisions; Revised Figure 2; Added Table 1

References in corpus (5)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
• Factoring nonnegative matrices with linear programs
• Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization
• Topic Discovery through Data Dependent and Random Projections

Cited by in corpus (8)

• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• Consistent Estimation of Mixed Memberships with Successive Projections
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Robustness Analysis of Preconditioned Successive Projection Algorithm for General Form of Separable NMF Problem
• Mixed Membership Graph Clustering via Systematic Edge Query
• Convex Programming Based Spectral Clustering
• Spectral Clustering by Ellipsoid and Its Connection to Separable Nonnegative Matrix Factorization