Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization

Nicolas Gillis, Abhishek Kumar

Introduction

Matrix factorization is a fundamental technique in data science, used extensively for dimensionality reduction, feature extraction, and clustering. While standard Nonnegative Matrix Factorization (NMF) requires both the input data and its factors to be strictly non-negative, Semi-Nonnegative Matrix Factorization (Semi-NMF) offers a more flexible alternative. In Semi-NMF, the input matrix $M$ and the basis matrix $U$ (representing cluster centroids) can contain mixed signs, while only the membership matrix $V$ is constrained to be non-negative ($V \ge 0$).

This flexibility makes Semi-NMF particularly useful for tasks like motion segmentation and hyperspectral unmixing, where data often contains negative values. However, despite its utility, the theoretical properties and computational complexity of Semi-NMF have remained under-explored. This paper bridges that gap, proving the NP-hardness of the problem even in the simplest cases, identifying conditions for exact solutions, and proposing highly efficient initialization strategies.

Theoretical Complexity and Challenges

One of the most surprising findings of this research is that rank-1 Semi-NMF is NP-hard. In standard NMF, the rank-1 case is solvable in polynomial time via the Perron-Frobenius theorem. However, because Semi-NMF allows the input matrix $M$ to have mixed signs, the problem of finding the best rank-1 approximation becomes equivalent to maximizing a convex quadratic over a non-negative orthant—a known NP-hard problem.

Furthermore, the authors demonstrate that Semi-NMF can be ill-posed. For certain matrices, an optimal solution may not even exist, as the infimum of the objective function cannot be reached within the feasible set. These theoretical hurdles explain why traditional algorithms, which often rely on simple multiplicative updates or K-means initialization, frequently struggle with slow convergence or local minima.

Proposed Methodology

To address these challenges, the authors move away from traditional multiplicative updates in favor of a Block Coordinate Descent (BCD) approach. This method is numerically stable and guaranteed to converge to a stationary point. The core contribution, however, lies in the initialization of this solver through two novel algorithms:

  1. Algorithm 2 (SVD-based Initialization): This algorithm is based on the proof that any unconstrained rank-$k$ factorization can be transformed into a rank-$(k+1)$ Semi-NMF. It provides a theoretical safety net, guaranteeing that the Semi-NMF error will be at least as good as the best unconstrained rank-$(r-1)$ approximation.
  2. Algorithm 3 (Exact/Heuristic Initialization): This is the paper's most impactful contribution. The authors prove that if the row space of a matrix contains a strictly positive vector, its Semi-NMF can be solved exactly in polynomial time. Algorithm 3 utilizes a truncated Singular Value Decomposition (SVD) combined with a bisection method to find this optimal solution. When the matrix does not perfectly meet the criteria, the algorithm serves as a powerful heuristic initialization.

Experimental Results

The authors evaluated their approach using synthetic data and real-world datasets, including the CBCL Face Dataset, the UCI Ionosphere dataset, and the UCI Waveform dataset.

Convergence and Accuracy

Algorithm 3 (A3) demonstrated exceptional performance. When used to initialize the BCD solver, the model typically converged in fewer than 10 iterations across all real-world datasets. On the CBCL and Waveform datasets, the A3 initialization was so effective that it immediately identified the exact optimal solution, matching the theoretical best possible unconstrained approximation.

Noise Tolerance

In synthetic tests involving Semi-Nonnegative matrices injected with Gaussian noise, Algorithm 3 significantly outperformed random (RD) and K-means (KM) initializations. It consistently recovered optimal or near-optimal solutions even under high-noise conditions. Interestingly, while Algorithm 2 offered strong theoretical guarantees, it proved practically weaker than basic random initialization in most empirical tests.

Conclusion and Future Work

This research provides a rigorous foundation for Semi-NMF, clarifying its complexity and providing tools to solve it more effectively. The discovery that Semi-NMF on strictly non-negative data essentially reduces to an SVD transformation suggests that the method's primary value lies in mixed-sign data or in scenarios where additional constraints are applied.

Future work will focus on Sparse Semi-NMF, where the membership matrix $V$ is forced to be sparse. Adding sparsity constraints could prevent the collapse of the problem into a simple SVD, restoring unique clustering properties and making the algorithm even more versatile for high-dimensional data analysis.

Summary updated

Abstract

Given a matrix $M$ (not necessarily nonnegative) and a factorization rank $r$, semi-nonnegative matrix factorization (semi-NMF) looks for a matrix $U$ with $r$ columns and a nonnegative matrix $V$ with $r$ rows such that $UV$ is the best possible approximation of $M$ according to some metric. In this paper, we study the properties of semi-NMF from which we develop exact and heuristic algorithms. Our contribution is threefold. First, we prove that the error of a semi-NMF of rank $r$ has to be smaller than the best unconstrained approximation of rank $r-1$. This leads us to a new initialization procedure based on the singular value decomposition (SVD) with a guarantee on the quality of the approximation. Second, we propose an exact algorithm (that is, an algorithm that finds an optimal solution), also based on the SVD, for a certain class of matrices (including nonnegative irreducible matrices) from which we derive an initialization for matrices not belonging to that class. Numerical experiments illustrate that this second approach performs extremely well, and allows us to compute optimal semi-NMF decompositions in many situations. Finally, we analyze the computational complexity of semi-NMF proving its NP-hardness, already in the rank-one case (that is, for $r = 1$), and we show that semi-NMF is sometimes ill-posed (that is, an optimal solution does not exist).
BibTeX
@article{gillis2015exact,
  author = {Nicolas Gillis and Abhishek Kumar},
  title = {{Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2015},
  doi = {10.1137/140993272},
}
Figure