Abstract
Nonnegative matrix factorization (NMF) is the problem of approximating an input nonnegative matrix, $V$, as the product of two smaller nonnegative matrices, $W$ and $H$. In this paper, we introduce a general framework to design multiplicative updates (MU) for NMF based on $\beta$-divergences ($\beta$-NMF) with disjoint equality constraints, and with penalty terms in the objective function. By disjoint, we mean that each variable appears in at most one equality constraint. Our MU satisfy the set of constraints after each update of the variables during the optimization process, while guaranteeing that the objective function decreases monotonically. We showcase this framework on three NMF models, and show that it competes favorably the state of the art: (1) $\beta$-NMF with sum-to-one constraints on the columns of $H$, (2) minimum-volume $\beta$-NMF with sum-to-one constraints on the columns of $W$, and (3) sparse $\beta$-NMF with $\ell_2$-norm constraints on the columns of $W$.
Introduction
Nonnegative Matrix Factorization (NMF) is a fundamental technique in data science, used to decompose a nonnegative input matrix $V \in \mathbb{R}^{m \times n}_+$ into two smaller nonnegative matrices: $W \in \mathbb{R}^{m \times r}_+$ (the basis or features) and $H \in \mathbb{R}^{r \times n}_+$ (the weights or abundances). While standard NMF is powerful, many real-world applications require the factors to satisfy additional physical or structural constraints. For instance, in hyperspectral unmixing, the columns of $H$ represent the fractional abundances of materials in a pixel and must sum to exactly one.
Traditionally, solving NMF with such constraints using Multiplicative Updates (MU) has been challenging. Researchers often resort to heuristic "a posteriori" fixes, such as projecting variables back onto the constraint set or renormalizing columns after each iteration. However, these methods frequently destroy the mathematical guarantee of monotonicity—the assurance that the objective function decreases at every step. This paper introduces a rigorous framework to design MU for $\beta$-NMF that strictly satisfies disjoint equality constraints while ensuring monotonic convergence.
The Majorization-Minimization Framework
The core of the proposed method lies in the Majorization-Minimization (MM) principle. Instead of minimizing the complex $\beta$-divergence objective function directly, the authors construct a "majorizer"—a simpler surrogate function that upper-bounds the objective and coincides with it at the current estimate.
The framework introduces three key mathematical innovations:
- Separable Majorizers: By choosing a majorizer that is separable with respect to the variables, the high-dimensional optimization problem is decomposed into independent subproblems.
- Lagrangian Duals for Disjoint Constraints: The authors focus on "disjoint" constraints, where each variable appears in at most one equality constraint. This allows for the introduction of Lagrange multipliers that can be solved for efficiently.
- Newton-Raphson Optimization: To find the optimal Lagrange multiplier for each update, the algorithm employs the Newton-Raphson method. The authors prove that this sub-step converges quadratically, meaning it adds negligible computational overhead compared to the heavy matrix multiplications ($VH^T$ and $W^TV$) that dominate NMF runtimes.
This approach is versatile, supporting the entire family of $\beta$-divergences, which includes squared Euclidean distance ($\beta=2$), Kullback-Leibler divergence ($\beta=1$), and Itakura-Saito divergence ($\beta=0$).
Applications and Experimental Validation
The framework was evaluated across three distinct NMF models using both hyperspectral imaging and audio datasets:
1. Simplex-Structured NMF
This model imposes sum-to-one constraints on the columns of $H$. Tested on hyperspectral datasets like Samson, Jasper Ridge, and Cuprite, the proposed algorithm outperformed the state-of-the-art Group Robust NMF (GR-NMF). For $\beta=1$, the new updates were up to 2.5 times faster and reached lower objective values.
2. Minimum-Volume $\beta$-NMF
Minimum-volume constraints are often used to find the most "pure" basis vectors in $W$. By incorporating sum-to-one constraints on the columns of $W$ within the MM framework, the authors achieved a 2x to 7x speedup compared to traditional methods that rely on backtracking line searches.
3. Sparse $\beta$-NMF
The framework also extends to $\ell_2$-norm (quadratic) constraints on the columns of $W$, which are useful for inducing sparsity or normalizing features. The resulting MU converged more reliably and faster than existing heuristic-based sparse NMF solvers.
Key Insights
The "disjoint" nature of the constraints is the primary enabler of this efficiency. By ensuring a single variable isn't pulled in conflicting directions by multiple equality rules, the authors transformed a massive constrained optimization problem into a series of easily solvable 1D problems. Furthermore, because the constraints are built directly into the update rule, the algorithm remains computationally scalable, maintaining the same complexity as standard NMF.
Conclusion and Future Directions
This work provides a mathematically sound foundation for constrained NMF, moving away from heuristic projections toward guaranteed monotonic updates. The primary limitation remains the requirement for disjoint constraints. Future research aims to extend this framework to non-disjoint constraints, such as those found in doubly stochastic matrices (where both row and column sums are fixed). This would require solving more complex systems of polynomial equations for the Lagrange multipliers, representing a significant next step in the evolution of NMF algorithms.
Summary updated