Optimization Online


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

Nicolas Gillis (nicolas.gillis***at***uclouvain.be)

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 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.

Keywords: Nonnegative matrix factorization, separability, robustness, linear programming, HottTopixx

Category 1: Applications -- Science and Engineering (Data-Mining )

Category 2: Linear, Cone and Semidefinite Programming (Linear Programming )

Citation: arXiv:1211.6687

Download: [PDF]

Entry Submitted: 11/29/2012
Entry Accepted: 11/29/2012
Entry Last Modified: 12/04/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society