First Order Methods for Robust non-negative matrix factorization for large scale noisy data

Jason Gejie Liu, Shuchin AeronICASSP 2014 · OpenReview

TL;DR

This paper tackles the challenge of Non-negative Matrix Factorization (NMF) on large, noisy datasets where the standard "separability assumption" doesn't hold. They adapt a Linear Programming (LP) approach to handle noise and then employ computationally efficient First-Order Methods (FOMs) to make it scalable, demonstrating its effectiveness on synthetic and real-world hyperspectral data.

What Problem Does This Paper Address?

Non-negative Matrix Factorization (NMF) is a powerful technique for decomposing data into interpretable, non-negative components. A key assumption for NMF to uniquely identify these components (called "extreme rays" of a cone) is the "separability assumption," which states that the data points lie on or within a cone generated by a small subset of the data itself. However, in real-world scenarios, data is often noisy, and this assumption is rarely met. Existing LP-based methods for NMF can identify these extreme rays even with some noise, but they become computationally intractable for large datasets due to a massive number of constraints. This paper aims to bridge this gap by developing a robust NMF method that can handle both noise and large-scale data.

Methods

The authors build upon existing LP-based reformulations of NMF that aim to find the extreme rays of the data's convex cone. To address noise, they introduce a "buffer area" or tolerance (parameter $\epsilon$) in their LP formulation, allowing for some deviation from the ideal cone. The core innovation lies in tackling the computational bottleneck of these LP formulations for large-scale data. Instead of relying on computationally expensive interior-point methods, they adopt First-Order Methods (FOMs). FOMs are known for their efficiency in handling large-scale optimization problems by focusing on cheap computations per iteration, even if they require more iterations. They propose a specific FOM-based algorithm (Algorithm 1) that uses a 1-memory approach and incorporates a proximity function based on a strictly convex function to handle the non-negativity constraints.

Datasets

  • Synthetic Data: Generated data with varying sizes and Signal-to-Noise Ratios (SNRs) to evaluate the algorithm's performance under controlled noise conditions.
  • Urban HSI Dataset: A real-world hyperspectral imaging dataset (Urban HSI) containing 162 spectral bands and dimensions of 307x307 pixels. This dataset is composed of 6 material types (road, dirt, trees, roof, grass, metal) and serves as a benchmark for evaluating the algorithm on complex, real-world data.

Key Insights and Ideas

  • Separability Assumption is Fragile: The paper highlights that the strict separability assumption, crucial for exact NMF, is often violated in practice due to noise and the presence of "approximate duplicates" of extreme rays in the data.
  • LP for Robustness, FOMs for Scale: The LP reformulation provides a principled way to handle noise by defining a buffer region. However, its scalability is limited. The paper's key contribution is demonstrating that FOMs can effectively overcome this scalability issue, making robust NMF practical for large datasets.
  • Off-Diagonal Entries in C Matter: In noisy or non-separable cases, the localization matrix C (which ideally has 1s on the diagonal) can have significant off-diagonal entries. These entries, while not directly indicating extreme rays, still represent potential candidates and can be leveraged with post-processing.
  • Post-processing for Endmember Identification: For real-world data like hyperspectral images, where exact separability is unlikely, a post-processing step on the computed matrix C is necessary to identify the true endmembers, especially when dealing with approximate duplicates.

Key Results

  • The proposed FOMs-based algorithm successfully handles noisy synthetic data across various SNRs, achieving good performance as indicated by the results in Table I (e.g., achieving 25/25 correct identifications for a 25x100 dataset at 50dB SNR).
  • When applied to the Urban HSI dataset, the algorithm was able to identify potential endmembers. Although the localization matrix C showed significant off-diagonal entries (as seen in Fig. 4), a post-processing step allowed for the identification of 6 unique spectral signatures, aligning with the known endmembers of the dataset.

Limitations and Future Work

  • Threshold Sensitivity: The paper acknowledges that the pre- and post-processing steps, particularly the choice of thresholds (e.g., $\gamma$ for data reduction, and thresholds for identifying endmember candidates from C), can influence the accuracy of the results, potentially leading to false positives or negatives.
  • Lipschitz Constant Computation: Computing the Lipschitz constant for the objective function can be computationally expensive for very large datasets, which is an area for future research.
  • Constraint Handling for Large-Scale Problems: The paper mentions that extending the LP formulation to strictly enforce diagonal dominance (e.g., $C_{ii} \ge C_{ij}$) for large-scale data remains a challenge due to the sheer number of constraints. Future work could explore efficient ways to handle these constraints.

Summary updated

Abstract

Nonnegative matrix factorization (NMF) has been shown to be identifiable under the separability assumption, under which all the columns(or rows) of the input data matrix belong to the convex cone generated by only a few of these columns(or rows) [1]. In real applications, however, such separability assumption is hard to satisfy. Following [4] and [5], in this paper, we look at the Linear Programming (LP) based reformulation to locate the extreme rays of the convex cone but in a noisy setting. Furthermore, in order to deal with the large scale data, we employ First-Order Methods (FOM) to mitigate the computational complexity of LP, which primarily results from a large number of constraints. We show the performance of the algorithm on real and synthetic data sets.
BibTeX
@inproceedings{liu2014first,
  author = {Jason Gejie Liu and Shuchin Aeron},
  title = {{First Order Methods for Robust non-negative matrix factorization for large scale noisy data}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  url = {https://openreview.net/forum?id=B5dsl_Gyl1N},
}
Figure