Monotonous (semi-)nonnegative matrix factorization

Nirav Bhatt, Arun Ayyar

TL;DR

This paper introduces "monotonous NMF," a novel extension of Nonnegative Matrix Factorization (NMF) that explicitly accounts for the monotonic nature of source signals. By incorporating this constraint, the authors demonstrate improved source signal recovery, particularly in scenarios where standard NMF struggles.

What Problem Does This Paper Address?

Nonnegative Matrix Factorization (NMF) is a powerful technique for decomposing a non-negative data matrix into two non-negative matrices: a mixing matrix and a source signal matrix. It finds applications in various fields, including blind source separation. However, standard NMF suffers from ambiguities in scaling and ordering, and it may not perform optimally when the underlying source signals exhibit a specific characteristic: monotonicity. Many real-world signals, such as those found in chemistry or systems biology, naturally increase or decrease over time. Standard NMF methods, which don't account for this, can fail to accurately recover these signals, leading to suboptimal decompositions. This paper aims to address this limitation by developing a new NMF framework that explicitly enforces monotonicity on the source signals.

Methods

The core contribution of this paper is the formulation of monotonous NMF. This is achieved by adding constraints to the standard NMF optimization problem. Specifically, the authors impose conditions on the rows of the source signal matrix (H) to ensure they are either monotonically increasing or decreasing.

To solve this constrained optimization problem, they propose an alternating least-squares (ALS) approach. This involves decomposing the problem into two subproblems: one where the mixing matrix (W) is updated while keeping the source matrix (H) fixed, and another where the source matrix (H) is updated while keeping the mixing matrix (W) fixed. Both subproblems are formulated as quadratic programming problems, which are known to be convex and can be efficiently solved using standard optimization techniques.

Furthermore, the authors extend their approach to monotonous semi-NMF. This relaxes the non-negativity constraint on the mixing matrix (W), allowing it to contain negative entries. This extension makes the method applicable to datasets that may have negative values, while still preserving the monotonicity constraint on the source signals.

Datasets

The paper uses synthetic data for evaluation. The authors generate noise-free data matrices by multiplying a mixing matrix (8x3) with source signal matrices. They then add 5% random noise to create noisy datasets for simulation. Two scenarios are considered:

  • Scenario S1: Monotonically increasing source signals.
  • Scenario S2: Mixed monotonous source signals (two increasing, one decreasing).

No new benchmarks are introduced; rather, the proposed methods are compared against existing NMF algorithms.

Key Insights and Ideas

  • Monotonicity is a crucial signal characteristic: The paper highlights that many real-world signals exhibit monotonic behavior, and ignoring this can lead to significant performance degradation in standard NMF.
  • Explicit constraints improve source recovery: By directly incorporating monotonicity constraints into the NMF optimization, the proposed method significantly outperforms standard NMF and other variants when dealing with such signals.
  • ALS provides a viable solution: The alternating least-squares framework effectively breaks down the complex constrained optimization problem into manageable, convex subproblems.
  • Semi-NMF extension broadens applicability: Relaxing the non-negativity constraint on the mixing matrix makes the monotonous NMF approach more versatile, enabling its use with datasets containing negative values.

Key Results

The paper demonstrates the effectiveness of monotonous NMF through simulations on synthetic data.

  • Scenario S1 (Monotonically increasing signals): Monotonous NMF (MNMF) achieved a reconstruction error of 0.1197, significantly better than standard NMF (NNMF) at 0.1564 and a basic NMF implementation (NMF) at 0.9835. MNMF and NNMF successfully factorized the data into three rank-one factors, whereas NMF estimated a rank-deficient matrix (rank 1).
  • Scenario S2 (Mixed monotonous signals): MNMF again showed superior performance with a reconstruction error of 0.1189, compared to NNMF (0.1399) and NMF (0.5736). MNMF was better at capturing both increasing and decreasing monotonous signals. NMF again estimated a rank-deficient matrix, though with a slightly increased rank (rank 2).
  • The paper notes that while NNMF (a multiplicative update rule-based NMF) also attempts to capture source signals, it fails to accurately represent their monotonous behavior.

Limitations and Future Work

  • Convergence Speed: The authors acknowledge that the ALS framework, while guaranteeing convergence, may have a slower convergence speed compared to some other NMF algorithms.
  • Future Work: The paper suggests future research directions, including the incorporation of sparsity constraints and the handling of integer entries in the mixing matrix.

Summary updated

Abstract

Nonnegative matrix factorization (NMF) factorizes a non-negative matrix into product of two non-negative matrices, namely a signal matrix and a mixing matrix. NMF suffers from the scale and ordering ambiguities. Often, the source signals can be monotonous in nature. For example, in source separation problem, the source signals can be monotonously increasing or decreasing while the mixing matrix can have nonnegative entries. NMF methods may not be effective for such cases as it suffers from the ordering ambiguity. This paper proposes an approach to incorporate notion of monotonicity in NMF, labeled as monotonous NMF. An algorithm based on alternating least-squares is proposed for recovering monotonous signals from a data matrix. Further, the assumption on mixing matrix is relaxed to extend monotonous NMF for data matrix with real numbers as entries. The approach is illustrated using synthetic noisy data. The results obtained by monotonous NMF are compared with standard NMF algorithms in the literature, and it is shown that monotonous NMF estimates source signals well in comparison to standard NMF algorithms when the underlying sources signals are monotonous.
BibTeX
@inproceedings{bhatt2015monotonous,
  author = {Nirav Bhatt and Arun Ayyar},
  title = {{Monotonous (semi-)nonnegative matrix factorization}},
  booktitle = {CODS},
  year = {2015},
  url = {https://openreview.net/forum?id=ZSdB3R3e7A},
}
Figure