Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization

Abstract

Nonnegative matrix factorization (NMF) has been shown recently to be tractable under the separability assumption, under which all the columns of the input data matrix belong to the convex cone generated by only a few of these columns. Bittorf, Recht, Ré and Tropp (`Factoring nonnegative matrices with linear programs', NIPS 2012) proposed a linear programming (LP) model, referred to as Hottopixx, which is robust under any small perturbation of the input matrix. However, Hottopixx has two important drawbacks: (i) the input matrix has to be normalized, and (ii) the factorization rank has to be known in advance. In this paper, we generalize Hottopixx in order to resolve these two drawbacks, that is, we propose a new LP model which does not require normalization and detects the factorization rank automatically. Moreover, the new LP model is more flexible, significantly more tolerant to noise, and can easily be adapted to handle outliers and other noise models. Finally, we show on several synthetic datasets that it outperforms Hottopixx while competing favorably with two state-of-the-art methods.

27 page; 4 figures. New Example, new experiment on the Swimmer data set

References in corpus (4)

• 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
• Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing

Cited by in corpus (21)

• Truncated Cauchy Non-negative Matrix Factorization
• Deep Spectrum Cartography: Completing Radio Map Tensors Using Learned Neural Models
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• Learning From Hidden Traits: Joint Factor Analysis and Latent Clustering
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• Generalized Separable Nonnegative Matrix Factorization
• Introduction to 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
• Rank-One NMF-Based Initialization for NMF and Relative Error Bounds under a Geometric Assumption
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Identifiability-Guaranteed Simplex-Structured Post-Nonlinear Mixture Learning via Autoencoder
• Smoothed Separable Nonnegative Matrix Factorization
• Provably robust blind source separation of linear-quadratic near-separable mixtures
• A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization
• Automatic Dimension Selection for a Non-negative Factorization Approach to Clustering Multiple Random Graphs
• A model selection approach for clustering a multinomial sequence with non-negative factorization
• Analyzing Raman Spectral Data without Separability Assumption
• Techniques for clustering interaction data as a collection of graphs