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 separable (that is, there exists a cone spanned by a small subset of the columns containing all columns). Since then, several algorithms have been designed to handle this subclass of NMF problems. In particular, Bittorf, Recht, R\’e and Tropp (`Factoring nonnegative matrices with linear programs’, NIPS 2012) proposed a linear programming model, referred to as HottTopixx. In this paper, we provide a new and more general robustness analysis of their method. In particular, our analysis is almost tight and allows duplicates and near duplicates in the dataset. Moreover, we design a provably more robust variant using an appropriate post-processing strategy.
Citation
arXiv:1211.6687