Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization

Nicolas Gillis, Stephen A. Vavasis

TL;DR

This paper introduces a novel preconditioning technique for near-separable Nonnegative Matrix Factorization (NMF) using Semidefinite Programming (SDP). This method significantly enhances the robustness of existing NMF algorithms, particularly the Successive Projection Algorithm (SPA), against noise, leading to more reliable results on challenging datasets.

What Problem Does This Paper Address?

Nonnegative Matrix Factorization (NMF) is a powerful technique for dimensionality reduction and feature extraction, widely used in areas like document analysis and hyperspectral imaging. A specific, more tractable version is "near-separable NMF," which assumes that the data can be approximated by a linear combination of a small subset of its columns. While efficient algorithms exist for this case, they are often sensitive to noise, leading to degraded performance. The challenge is to make these algorithms more robust to noise without sacrificing their efficiency or accuracy.

Methods

The core contribution is a preconditioning method based on Semidefinite Programming (SDP). The authors propose to transform the input matrix $M$ into a new matrix $QM$ where $Q$ is computed using an SDP formulation that aims to minimize the volume of an ellipsoid containing the data points. This transformation effectively "well-conditions" the matrix, making it more amenable to NMF algorithms. They then demonstrate how this preconditioning can be applied to the Successive Projection Algorithm (SPA), proving that the preconditioned SPA is provably more robust to noise. For large-scale problems, they combine this SDP preconditioning with an active-set method and SVD-based dimensionality reduction.

Datasets

The paper evaluates its proposed method on:

  • Synthetic datasets: Specifically, a "Middle Points Experiment" designed to be challenging for NMF algorithms, where data points lie on the edges of the convex hull of the basis vectors. This experiment is conducted with both uniform and Gaussian noise.
  • Real-world hyperspectral images: The "Hubble Telescope" hyperspectral image dataset is used to demonstrate the applicability of the method to large-scale, real-world scenarios.

Key Insights and Ideas

  • SDP for Preconditioning: The paper establishes a novel link between Semidefinite Programming and preconditioning for NMF. By solving a minimum volume ellipsoid problem via SDP, they can find a transformation that improves the conditioning of the data matrix.
  • Provable Robustness: The theoretical analysis demonstrates that preconditioning SPA with SDP leads to provable improvements in robustness against noise, allowing for higher noise levels before performance degrades.
  • Bridging Theory and Practice: The work not only provides theoretical guarantees but also shows how to apply these techniques to large-scale real-world problems using an active-set method, making it practically relevant.
  • Hierarchy of Algorithms: The experiments reveal a clear hierarchy in performance, with SDP-based preconditioned algorithms consistently outperforming others, especially under noisy conditions.

Key Results

  • Improved Robustness: The preconditioned SPA (Prec-SPA) significantly outperforms standard SPA and other state-of-the-art algorithms (like VCA and XRAY) in terms of robustness to noise on synthetic datasets. For instance, on the "Middle Points" experiment, Prec-SPA can correctly identify all columns of $W$ for noise levels up to $\epsilon = 0.45$, whereas standard SPA fails beyond $\epsilon = 0.01$.
  • Competitive Performance: The proposed preconditioned SPA (Prec-SPA) and its post-processed version (Post-Prec-SPA) achieve the highest robustness across various noise levels.
  • Scalability: The combination of SVD and an active-set method allows the SDP preconditioning to be applied to large-scale hyperspectral images, with the number of active set updates remaining small.
  • Theoretical Guarantees: The paper provides theoretical bounds showing that the preconditioned SPA can tolerate significantly higher noise levels than standard SPA, with the error bound depending less on the condition number of $W$.

Limitations and Future Work

  • Computational Cost: While the active-set method helps manage the scale, solving the SDP can still be computationally intensive, especially for very large $r$ (number of components). The authors note that for very large $r$, alternatives to SDP might be needed.
  • Tightness of Bounds: The authors acknowledge that the tightness of the derived theoretical bounds, particularly concerning the dependence on $r$, is an open question.
  • Future Research Directions:
    • Developing faster SDP solvers or alternative preconditioning methods for extremely large $r$.
  • Exploring other dimensionality reduction techniques beyond SVD, especially for non-Gaussian noise models.
  • Empirically evaluating the performance of preconditioned SPA on a wider range of real-world problems, such as document classification.
  • Investigating the effect of preconditioning on other NMF algorithms.

Summary updated

Abstract

Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyperspectral unmixing. This problem is referred to as near-separable NMF and requires that there exists a cone spanned by a small subset of the columns of the input nonnegative matrix approximately containing all columns. In this paper, we propose a preconditioning based on semidefinite programming making the input matrix well-conditioned. This in turn can improve significantly the performance of near-separable NMF algorithms which is illustrated on the popular successive projection algorithm (SPA). The new preconditioned SPA is provably more robust to noise, and outperforms SPA on several synthetic data sets. We also show how an active-set method allow us to apply the preconditioning on large-scale real-world hyperspectral images.
BibTeX
@article{gillis2013semidefinite,
  author = {Nicolas Gillis and Stephen A. Vavasis},
  title = {{Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization}},
  journal = {SIAM J. Optim.},
  year = {2013},
  doi = {10.1137/130940670},
}
Figure