Robust Near-Separable Nonnegative Matrix Factorization Using Linear\n Optimization

Nicolas Gillis, Robert Luce

Abstract

Nonnegative matrix factorization (NMF) is a powerful tool for data analysis, but it is generally NP-hard. Under the "separability" assumption, NMF becomes tractable. This paper generalizes the Hottopixx linear programming (LP) model to create a more flexible and robust framework. The proposed model eliminates the need for data normalization, automatically detects the factorization rank, and demonstrates significantly higher tolerance to noise and outliers compared to existing state-of-the-art methods.

Introduction

Nonnegative Matrix Factorization (NMF) is widely used in fields like text mining and hyperspectral imaging to decompose complex data into meaningful, sparse components. While the general problem is computationally difficult, the separability assumption—which posits that the basis vectors are themselves columns of the input matrix—allows for polynomial-time solutions.

A prominent LP-based approach, Hottopixx, successfully addressed noisy separable NMF. However, it suffered from two practical limitations: it required prior knowledge of the factorization rank ($r$) and necessitated data normalization. Normalization can be problematic as it may distort signals or amplify noise in low-magnitude data.

The Generalized LP Model

The authors introduce a new LP model that addresses these shortcomings by modifying the objective function and constraints of the original Hottopixx algorithm.

Key Improvements:

  1. Automatic Rank Detection: By removing the hard constraint on the trace of the solution matrix ($tr(X) = r$) and instead minimizing the diagonal entries, the model naturally identifies the minimum number of columns required for reconstruction within a specified noise budget ($\epsilon$).
  2. Unnormalized Data Handling: The new model employs a change of variables to operate directly on unnormalized data. It offers two variants: one for relative error (scaling with signal magnitude) and one for absolute error (independent of magnitude).
  3. Enhanced Robustness: Theoretical analysis shows that the noise bound for this model is independent of the number of columns, making it more reliable for high-dimensional datasets. The authors also identify that using a parameter $\rho=1$ for the noise constraint is superior to the $\rho=2$ used in Hottopixx.

Experimental Evaluation

The model was tested against synthetic datasets and the classic Swimmer dataset.

  • Synthetic Data: The proposed model, particularly with $\rho=1$, consistently outperformed Hottopixx across dense, sparse, and pointwise noise patterns. It was uniquely successful in "pointwise" noise scenarios where other algorithms failed.
  • Swimmer Dataset: The algorithm perfectly identified all 16 basis components (limbs) and the correct rank, even at noise levels where Hottopixx failed.

Conclusion

This research provides a more flexible and robust "plug-and-play" solution for NMF. By generalizing the LP framework, the authors have removed significant barriers to practical application, such as the need for manual rank selection and data normalization. While the $O(n^2)$ complexity of the LP variables remains a challenge for very large datasets, the theoretical and empirical gains in robustness mark a significant advancement in the field.

Summary updated

Abstract

Nonnegative matrix factorization (NMF) has been shown recently to be\ntractable under the separability assumption, under which all the columns of the\ninput data matrix belong to the convex cone generated by only a few of these\ncolumns. Bittorf, Recht, R\\'e and Tropp (`Factoring nonnegative matrices with\nlinear programs', NIPS 2012) proposed a linear programming (LP) model, referred\nto as Hottopixx, which is robust under any small perturbation of the input\nmatrix. However, Hottopixx has two important drawbacks: (i) the input matrix\nhas to be normalized, and (ii) the factorization rank has to be known in\nadvance. In this paper, we generalize Hottopixx in order to resolve these two\ndrawbacks, that is, we propose a new LP model which does not require\nnormalization and detects the factorization rank automatically. Moreover, the\nnew LP model is more flexible, significantly more tolerant to noise, and can\neasily be adapted to handle outliers and other noise models. Finally, we show\non several synthetic datasets that it outperforms Hottopixx while competing\nfavorably with two state-of-the-art methods.\n
BibTeX
@article{gillis2014robust,
  author = {Nicolas Gillis and Robert Luce},
  title = {{Robust Near-Separable Nonnegative Matrix Factorization Using Linear\textbackslash\{\}n Optimization}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=6PjEGa1J6oip},
}
Figure