Robustness Analysis of Hottopixx, a Linear Programming Model for Factoring Nonnegative Matrices

Abstract

Although nonnegative matrix factorization (NMF) is NP-hard in general, it has been shown very recently that it is tractable under the assumption that the input nonnegative data matrix is close to being separable (separability requires that all columns of the input matrix belongs to the cone spanned by a small subset of these columns). Since then, several algorithms have been designed to handle this subclass of NMF problems. In particular, Bittorf, Recht, Ré and Tropp (`Factoring nonnegative matrices with linear programs', NIPS 2012) proposed a linear programming model, referred to as Hottopixx. In this paper, we provide a new and more general robustness analysis of their method. In particular, we design a provably more robust variant using a post-processing strategy which allows us to deal with duplicates and near duplicates in the dataset.

23 pages; new numerical results; Comparison with Arora et al.; Accepted in SIAM J. Mat. Anal. Appl

Cited by in corpus (14)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• On Identifiability of Nonnegative Matrix Factorization
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• Generalized Separable Nonnegative Matrix Factorization
• Using separable non-negative matrix factorization techniques for the analysis of time-resolved Raman spectra
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Smoothed Separable Nonnegative Matrix Factorization
• Refinement of Hottopixx Method for Nonnegative Matrix Factorization Under Noisy Separability
• On the Robustness of the Successive Projection Algorithm
• Endmember Extraction from Hyperspectral Images Using Self-Dictionary Approach with Linear Programming