Abstract Nonnegative Matrix Factorization (NMF) is a cornerstone of modern data analysis, enabling the compression and interpretation of nonnegative data through parts-based representations. This paper investigates a broader class of problems termed Nonnegative Factorization (NF), where a not necessarily nonnegative matrix is approximated by the product of two nonnegative matrices. We prove that NF is NP-hard for any fixed factorization rank $r \ge 1$ by establishing a reduction to the Maximum Edge Biclique Problem (MBP). This theoretical framework provides a mathematical explanation for the superior performance of Hierarchical Alternating Least Squares (HALS) over Multiplicative Updates (MU) and introduces a novel, efficient $O(|E|)$ algorithm for biclique detection in large-scale graphs.
Introduction
Since the seminal work of Lee and Seung in 1999, NMF has been widely adopted for its ability to decompose data into intuitive, additive components. However, many practical implementations, such as HALS, iteratively solve subproblems involving "residual" matrices that contain negative entries. This paper formalizes these subproblems as Nonnegative Factorization (NF). By analyzing the complexity of NF, we bridge the gap between continuous matrix factorization and discrete graph theory.
The Complexity of Nonnegative Factorization
A significant finding of this work is the "hardness jump" associated with NF. In standard NMF, rank-1 and rank-2 problems can be solved in polynomial time using techniques like Singular Value Decomposition (SVD) or the Perron-Frobenius theorem. In contrast, we demonstrate that for NF, even the rank-1 case is NP-hard.
This hardness stems from the negative values in the target matrix, which introduce combinatorial choices absent in purely nonnegative data. We prove this by reducing the Maximum Edge Biclique Problem—a known hard problem in graph theory—to a rank-1 NF problem. This connection reveals that finding the optimal rank-1 NF approximation is equivalent to identifying the largest biclique in a corresponding bipartite graph.
Algorithmic Insights: MU vs. HALS
The paper provides a mathematical "post-mortem" on the performance disparity between the two most popular NMF algorithms:
- Multiplicative Updates (MU): Originally proposed by Lee and Seung, MU is essentially a gradient-descent approach. We generalize MU to handle NF by splitting the target matrix into positive and negative components ($M = P - N$).
- Hierarchical Alternating Least Squares (HALS): HALS is shown to be significantly more efficient because it effectively solves the rank-1 NF subproblem optimally at each iteration, whereas MU takes "lazy," suboptimal steps.
Geometric Interpretation
The geometry of NF can be visualized as finding a low-rank subspace and a nonnegative cone within that subspace that best approximates the data points.
As shown in the figure above, the factorization seeks to project data points onto a plane (for rank-2) where they are bounded by rays representing the nonnegative basis vectors. The presence of negative values in the original matrix $M$ means that points may lie outside the first quadrant, complicating the search for the optimal cone.
Finding Bicliques in Large Graphs
By linking NF stationary points with feasible solutions of the biclique problem, we developed a new algorithm for graph mining. By employing a homotopy-like approach—starting with a low penalty for negative approximations and gradually increasing it—we force the NF stationary points to converge toward maximal bicliques.
Experimental Results
- Convergence: On the CBCL face database (2,429 images), HALS reached lower error rates significantly faster than generalized MU rules.
- Biclique Performance: On DIMACS benchmark graphs and synthetic random graphs, our $O(|E|)$ algorithm consistently identified larger bicliques than the established Motzkin-Strauss formalism.
- Biclustering: On a 'Classic' text mining dataset (7,094 texts, 41,681 words), the algorithm demonstrated robust biclustering capabilities, identifying dense submatrices even when perfect bicliques were not present.
Conclusion
This research establishes NF as a powerful framework that unites matrix factorization and graph theory. While the NP-hardness of NF implies that global optima are difficult to guarantee, the proposed NF-based algorithms offer a scalable and robust alternative to existing methods for both data compression and discrete graph analysis. Future work will explore more sophisticated penalty update schedules to further mitigate the risk of local optima.
Summary updated