Majorization-Minimization for Sparse Nonnegative Matrix Factorization With the $\beta$-Divergence

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

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.

Introduction

Nonnegative Matrix Factorization (NMF) is a fundamental tool for decomposing a data matrix $V$ into a dictionary $W$ and activations $H$, such that $V \approx WH$. To enhance interpretability or create part-based representations, researchers frequently impose sparsity on $H$. However, adding a sparsity penalty like the $\ell_1$ norm introduces a "scaling ambiguity": the optimization can trivially decrease the penalty by scaling $W$ up and $H$ down without changing the reconstruction error.

To mitigate this, standard practice involves constraining the columns of $W$ to unit norm. Existing approaches to this constrained problem generally fall into two categories: heuristic updates, which lack convergence guarantees and may increase the objective function, and Lagrangian methods, which are computationally intensive and often restricted to specific $\beta$-divergence values.

Methods: A Universal Framework

The authors propose a novel framework that bypasses hard constraints through a scale-invariant reformulation. By incorporating the norm of $W$ directly into the sparsity penalty of $H$, the objective function becomes invariant to individual scaling of the factors.

Majorization-Minimization (MM)

The core of the optimization relies on the MM principle. This involves constructing a surrogate function that upper-bounds the original objective and is easier to minimize. The authors derive specific surrogate functions for the $\beta$-divergence across all values of $\beta$.

Surrogate functions $G_\beta(\mathbf{H}|\tilde{\mathbf{H}})$ for the $\beta$-divergence across different ranges of $\beta$.

As shown in the table above, the framework provides a unified mathematical structure for the surrogate functions, enabling "universal" multiplicative updates. This is a significant departure from previous methods that required separate derivations for specific divergences like Kullback-Leibler ($\beta=1$) or Itakura-Saito ($\beta=0$).

Regularization

The framework supports both standard $\ell_1$-regularization and log-regularization. Log-regularization is particularly effective for "aggressive" sparsity, pushing small activation values more decisively toward zero.

Experimental Results

The algorithms were evaluated on diverse datasets, including Olivetti Faces, audio spectrograms, Moffett Field hyperspectral data, and the large-scale TasteProfile song play counts.

  • Computational Efficiency: The MM algorithms demonstrated significant speedups. On the Olivetti dataset, the proposed method was approximately 9x faster than heuristic alternatives (11.2s vs. 103.4s). On the massive TasteProfile dataset, MM-log was nearly twice as fast as the heuristic version.
  • Convergence Guarantees: Unlike heuristic methods that can exhibit "jitter" in the objective value, the MM approach is a true descent algorithm, guaranteed to improve or maintain the objective at every iteration.
  • Solution Quality: The methods consistently reached objective values comparable to or better than Lagrangian methods but in a fraction of the time.

Conclusion

This work provides a robust and efficient solution for sparse NMF with $\beta$-divergence. By leveraging scale-invariance and the MM principle, the authors deliver a universal algorithm with strong convergence guarantees. While the problem remains non-convex and sensitive to initialization, the speed and reliability of these updates represent a major step forward. Future research may extend this framework to other sparsity measures, such as $\ell_p$ norms for $0 < p < 1$, and explore automated hyperparameter tuning for the sparsity coefficient $\alpha$.

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 $\textbackslash\{\}beta$-Divergence}},
  journal = {IEEE Trans. Signal Process.},
  year = {2023},
  url = {https://openreview.net/forum?id=aZhHeCuvz3},
}
Figure