  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\'e 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.
