Robust near-separable nonnegative matrix factorization using linear optimization

Nicolas Gillis, Robert Luce

TL;DR

This paper introduces a new, more robust linear programming (LP) model for Nonnegative Matrix Factorization (NMF) that overcomes key limitations of previous methods. It automatically detects the factorization rank and no longer requires input data normalization, making it more practical and tolerant to noise and outliers.

What Problem Does This Paper Address?

Nonnegative Matrix Factorization (NMF) is a powerful technique for dimensionality reduction and feature extraction, particularly useful when data is inherently non-negative (e.g., image pixel intensities, word counts). The core idea is to decompose a data matrix $M$ into two nonnegative matrices, $W$ and $H$, such that $M \approx WH$. This decomposition can reveal underlying "parts" or features ($W$) and their contributions to the observed data ($H$).

However, NMF is generally NP-hard. A significant breakthrough came with the "separability assumption," which states that the data matrix columns can be formed by nonnegative combinations of a few "basis" columns. Under this assumption, NMF becomes tractable. The "Hottopixx" LP model by Bittorf et al. (2012) leveraged this for "near-separable NMF" (handling noisy data). Despite its robustness, Hottopixx had two major drawbacks:

  1. Requires Normalization: The input data matrix $M$ must have columns that sum to one, which can distort the data and degrade performance.
  2. Requires Known Rank: The factorization rank ($r$) must be specified in advance, often requiring trial-and-error to find the optimal value.

This paper aims to address these limitations by proposing a new LP model that automatically determines the rank and eliminates the need for data normalization, while also improving robustness to noise and handling outliers.

Methods

The core contribution is a novel LP formulation that generalizes Hottopixx. The key innovations are:

  • Rank Detection: The new model removes the explicit constraint on the trace of the optimization variable $X$ (which fixed the rank in Hottopixx). Instead, the objective function and other constraints implicitly guide the model to identify the appropriate number of basis vectors.
  • No Normalization Required: The formulation is adapted to work directly with unnormalized data matrices. This is achieved by reformulating the objective and constraints to account for the varying norms of the input data columns.
  • Improved Robustness: The paper provides theoretical analysis demonstrating that the new model is significantly more tolerant to noise than Hottopixx. It also shows how the model can be extended to handle outliers.
  • Post-processing: For cases with duplicates or near-duplicates in the data, a post-processing step (Algorithm 4) is employed to refine the extracted column indices.

The new LP model (Equation 3 in the paper) is: $$ \min_{X \in \mathbb{R}^{n \times n}} p^T \text{diag}(X) \quad \text{subject to} \quad \|M - MX\|_1 \le \rho \epsilon, \quad X(i,i) \le 1 \text{ for all } i, \quad X(i,j) \le X(i,i) \text{ for all } i,j $$ where $p$ is a vector of positive entries, $\epsilon$ is the noise level, and $\rho$ is a parameter. The paper explores different choices for $\rho$, finding $\rho=1$ to be particularly effective.

Datasets

The paper evaluates its proposed method on:

  • Synthetic Data Sets: Six different data models are generated to test robustness under varying noise types (dense, sparse, pointwise) and data structures ("Dirichlet" and "Middle Points"). These models are designed to specifically challenge NMF algorithms.
  • Swimmer Data Set: A well-known benchmark dataset for NMF, consisting of binary images of a body with four limbs in different positions. This dataset is used to test the algorithm's ability to handle a known rank and specific data structure.

No new datasets are introduced; the focus is on evaluating existing algorithms on established benchmarks.

Key Insights and Ideas

  • Rank Detection is Key: Removing the explicit rank constraint is crucial. It allows the algorithm to adapt to the true underlying dimensionality of the data, making it more flexible and less prone to errors from incorrect rank assumptions.
  • Normalization is a Hindrance: The requirement for column normalization in Hottopixx can introduce significant distortions. The new model's ability to work without it is a major practical advantage.
  • Parameter $\rho$ Matters: The choice of the parameter $\rho$ in the LP objective significantly impacts performance. The theoretical analysis and experimental results strongly suggest $\rho=1$ is often optimal, offering better robustness than $\rho=2$ (used in Hottopixx).
  • Outlier Handling: The LP framework can be extended to identify and mitigate the impact of outliers by analyzing the off-diagonal entries of the solution matrix $X$.

Key Results

  • Superior Robustness: The proposed LP model consistently outperforms Hottopixx in terms of index recovery (correctly identifying the basis columns) and residual error across various noise levels and data models.
  • Rank Detection Success: The algorithm successfully identifies the correct factorization rank in experiments, unlike Hottopixx which requires it as input.
  • Competitive Performance: The new LP model (especially with $\rho=1$) performs comparably to or better than state-of-the-art methods like SPA and XRAY, particularly in challenging "sparse" and "pointwise" noise scenarios.
  • Computational Cost: While LP-based methods are generally slower than SPA and XRAY, the paper notes that the complexity of solving the LP is a significant factor, and further research into faster solvers is warranted. Table 2 shows Hottopixx is about 10x faster than the new LP model, but the new model offers significant advantages in robustness and flexibility.

Limitations and Future Work

  • Computational Complexity: Solving the LP can be computationally expensive, especially for very large datasets. The authors acknowledge that implementing and evaluating algorithms for large-scale problems is a topic for future research.
  • Theoretical Bounds: While theoretical bounds on noise tolerance are provided, they are often up to a constant multiplicative factor. Improving these bounds, especially for cases with duplicates, is an area for further investigation.
  • Practical Implementation: The paper focuses on theoretical understanding and synthetic experiments. Developing practical, robust, and computationally efficient algorithms for real-world, large-scale applications remains an open challenge.
  • Outlier Handling Generalization: The paper discusses outlier handling but notes that a more general case (beyond $\rho=2$ and absence of duplicates) is a topic for further research.

Summary updated

Abstract

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é 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 data sets that it outperforms Hottopixx while competing favorably with two state-of-the-art methods.
BibTeX
@article{gillis2014robust,
  author = {Nicolas Gillis and Robert Luce},
  title = {{Robust near-separable nonnegative matrix factorization using linear optimization}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=6PjEGa1J6oip},
}

Loading related content...

Figure