Abstract
This paper addresses the challenge of sparse Nonnegative Matrix Factorization (NMF) using the $\beta$-divergence family of cost functions. While sparsity is often desired in the activation matrix ($H$), standard formulations are frequently ill-posed due to the scale ambiguity between the dictionary ($W$) and activation factors. We introduce a novel framework that leverages a scale-invariant reparameterization of the objective function, allowing for the derivation of universal multiplicative updates via Majorization-Minimization (MM). Our approach provides simple, computationally efficient updates for both $\ell_1$ and log-regularization across all $\beta$-divergences, backed by formal convergence guarantees. Experimental results across audio, image, and recommendation datasets demonstrate that our methods achieve state-of-the-art convergence speeds, significantly outperforming traditional Lagrangian and heuristic approaches.
Introduction
Nonnegative Matrix Factorization (NMF) is a fundamental tool in signal processing and machine learning, used to decompose a data matrix $V$ into two lower-rank nonnegative matrices: a dictionary $W$ and an activation matrix $H$. In many practical scenarios, such as source separation or feature extraction, we seek a sparse representation where $H$ contains many zeros.
However, adding a sparsity penalty to $H$ introduces a mathematical instability. Because the product $WH$ is invariant to reciprocal scaling (multiplying $W$ by a constant and dividing $H$ by the same constant), an optimization algorithm can artificially minimize the sparsity penalty by driving the entries of $H$ toward zero while allowing $W$ to grow infinitely. To prevent this, researchers typically constrain the columns of $W$ to a unit norm. While effective, this constraint complicates the optimization landscape, often leading to algorithms that are either computationally expensive or limited to specific types of data.
Methodology
1. Scale-Invariant Reformulation
The core innovation of this work is a reparameterization that bypasses the need for hard constraints on $W$. By rewriting the objective function to be scale-invariant, the authors bake the norm of the dictionary columns directly into the regularization term of the activation matrix. This transforms a difficult constrained optimization problem into an unconstrained one, simplifying the derivation of update rules.
2. Majorization-Minimization (MM) Framework
To solve the reformulated objective, the authors employ the Majorization-Minimization principle. At each iteration, a surrogate function (a majorizer) is constructed that upper-bounds the original objective and is tangent to it at the current estimate. Minimizing this simpler surrogate ensures that the original objective function value never increases.
This framework yields Universal Multiplicative Updates. Unlike previous methods that required different derivations for different error metrics (e.g., Squared Frobenius vs. Kullback-Leibler), these updates are "plug-and-play" for any value of $\beta$ in the $\beta$-divergence family. The paper provides specific updates for:
- $\ell_1$-regularization: For standard sparse coding.
- Log-regularization: For more aggressive sparsity requirements.
Experimental Evaluation
The proposed MM-SNMF algorithms were tested against four diverse datasets to demonstrate their versatility and efficiency:
- Olivetti Faces: Used for part-based feature learning in computer vision.
- Audio Spectrogram: Source separation using a recording of Wes Montgomery’s "Four on Six."
- Moffett Field: Hyperspectral remote sensing data for mineral mapping.
- TasteProfile: A large-scale, sparse dataset of song play counts for recommendation systems.
Key Results
Computational Efficiency
The MM-based approach demonstrated significant speed advantages. On the large-scale TasteProfile dataset, the MM-SNMF-log algorithm completed its task in 6,704 seconds, nearly twice as fast as the 12,613 seconds required by the heuristic alternative. In the Olivetti face dataset tests, the MM approach reached convergence in a similar number of iterations as complex Lagrangian methods but with much lower CPU overhead per iteration, as it avoids expensive projection sub-routines.
Stability and Convergence
A critical contribution of this work is the formal proof of convergence. While many NMF updates used in the field are heuristic and can lead to oscillating objective values, the MM framework guarantees monotonic descent. The authors proved that the sequence of iterates produced by their algorithm converges to the set of stationary points of the objective function, providing a level of mathematical rigor often missing in sparse NMF literature.
Conclusion
By combining scale-invariant reparameterization with the Majorization-Minimization principle, this research provides a robust and universal solution for sparse NMF. The resulting algorithms are not only faster and more stable than existing methods but also easier to implement across different data modalities. Future work may explore the extension of this framework to joint regularization of both $W$ and $H$, as well as automated methods for hyperparameter selection ($\alpha$ and $\beta$).
Summary updated