Majorization-minimization for Sparse Nonnegative Matrix Factorization with the β-divergence

Arthur Marmin, José Henrique de Morais Goulart, Cédric Févotte

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

Abstract

This article introduces new multiplicative updates for nonnegative matrix factorization with the $\beta$-divergence and sparse regularization of one of the two factors (say, the activation matrix). It is well known that the norm of the other factor (the dictionary matrix) needs to be controlled in order to avoid an ill-posed formulation. Standard practice consists in constraining the columns of the dictionary to have unit norm, which leads to a nontrivial optimization problem. Our approach leverages a reparametrization of the original problem into the optimization of an equivalent scale-invariant objective function. From there, we derive block-descent majorization-minimization algorithms that result in simple multiplicative updates for either $\ell_{1}$-regularization or the more "aggressive" log-regularization. In contrast with other state-of-the-art methods, our algorithms are universal in the sense that they can be applied to any $\beta$-divergence (i.e., any value of $\beta$) and that they come with convergence guarantees. We report numerical comparisons with existing heuristic and Lagrangian methods using various datasets: face images, an audio spectrogram, hyperspectral data, and song play counts. We show that our methods obtain solutions of similar quality at convergence (similar objective values) but with significantly reduced CPU times.
BibTeX
@article{marmin2023majorization,
  author = {Arthur Marmin and José Henrique de Morais Goulart and Cédric Févotte},
  title = {{Majorization-minimization for Sparse Nonnegative Matrix Factorization with the β-divergence}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  url = {https://openreview.net/forum?id=aZhHeCuvz3},
}
Figure