PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithms for nonnegative matrix factorization with the beta-divergence

Cédric Févotte, Jérôme Idier

arXiv:1010.1763v3cs.LG

TL;DR

β-NMF lacked general monotonicity guarantees for heuristic multiplicative updates outside the convexity interval. The paper constructs a majorizing auxiliary function, derives MM and ME algorithms, and proves monotonicity for β ∈ [0, 2], while ME converges faster than MM or heuristic updates in the reported experiments.

  • Problem

    Heuristic β-NMF updates were observed to be monotone outside β ∈ [1, 2], but lacked proofs there, especially for nonconvex β-divergences.

  • Method

    The paper constructs an auxiliary function that majorizes the objective, then derives MM and ME descent algorithms and extensions to penalized and convex-NMF.

  • Results

    The heuristic algorithm is proven monotone for β ∈ [0, 2], and ME shows faster convergence than MM or heuristic updates with equivalent complexity.

  • Takeaways & Limitations

    The auxiliary-function framework unifies β-NMF algorithms and supports parameter-free descent methods, including variants with penalties and convex dictionaries.

  • Takeaways & Limitations

    Monotonicity of the heuristic algorithm remains unproven for β ∉ [0, 2].

Abstract

from arXiv · show

This paper describes algorithms for nonnegative matrix factorization (NMF) with the beta-divergence (beta-NMF). The beta-divergence is a family of cost functions parametrized by a single shape parameter beta that takes the Euclidean distance, the Kullback-Leibler divergence and the Itakura-Saito divergence as special cases (beta = 2,1,0, respectively). The proposed algorithms are based on a surrogate auxiliary function (a local majorization of the criterion function). We first describe a majorization-minimization (MM) algorithm that leads to multiplicative updates, which differ from standard heuristic multiplicative updates by a beta-dependent power exponent. The monotonicity of the heuristic algorithm can however be proven for beta in (0,1) using the proposed auxiliary function. Then we introduce the concept of majorization-equalization (ME) algorithm which produces updates that move along constant level sets of the auxiliary function and lead to larger steps than MM. Simulations on synthetic and real data illustrate the faster convergence of the ME approach. The paper also describes how the proposed algorithms can be adapted to two common variants of NMF : penalized NMF (i.e., when a penalty function of the factors is added to the criterion function) and convex-NMF (when the dictionary is assumed to belong to a known subspace).

1 CNRS LTCI; T´el´ecom ParisTech, France

The paper concerns NMF with the β-divergence and uses multiplicative algorithms, majorization-minimization, and majorization-equalization.

  • The paper addresses nonnegative matrix factorization with the β-divergence.
  • Its keywords identify multiplicative algorithms, majorization-minimization, and majorization-equalization as central methods.

1 Introduction

NMF seeks approximate nonnegative factorizations, while β-divergence provides a parameterized fitting criterion with Euclidean, KL, and IS special cases. The paper develops and analyzes multiplicative algorithms whose monotonicity was previously established only in restricted settings.

  • NMF seeks an approximate factorization V ≈ WH using nonnegative factors W and H, typically reducing dimensionality when FK + KN ≪ FN.
  • The β-divergence is a one-parameter cost family containing Euclidean distance, generalized KL divergence, and IS divergence at β = 2, 1, and 0.
  • Standard β-NMF uses heuristic multiplicative updates derived from a gradient decomposition into nonnegative terms.
  • Before this paper, monotonicity was proven for β ∈ [1, 2], while practice suggested monotonicity outside that convexity interval.
  • The paper constructs an auxiliary function yielding MM updates and proves heuristic monotonicity for β ∈ (0, 1).

2 Preliminaries

The β-divergence extends across β ∈ R, includes IS and KL as limit cases, and is convex in y only for β ∈ [1, 2]. The NMF task alternates updates of nonnegative factors under a separable fit criterion.

  • The β-divergence is defined for β ∈ R and yields IS and KL divergences at β = 0 and β = 1.
  • For every β, the divergence has a single minimum at y = x and increases with |y − x|.
  • The β-divergence is convex in y for β ∈ [1, 2] and admits a convex-concave-constant decomposition outside that interval.
  • The IS divergence at β = 0 is scale-invariant, unlike the other β-divergences.
  • The optimization alternates between solving for H with W fixed and solving for W with H fixed, using a separable criterion.
  • The paper defines monotonicity as nonincreasing criterion values and convergence as reaching a KKT-satisfying limit point.

3 An auxiliary function for β-NMF

The paper builds a separable auxiliary function that majorizes the β-NMF objective and is tight at the current iterate. Its construction combines Jensen majorization of the convex part with tangent majorization of the concave part, enabling MM and other descent updates.

  • 3.1 Definition of auxiliary function: An auxiliary function upper-bounds the objective everywhere and is tight at the current iterate.
  • 3.1 Definition of auxiliary function: Any update satisfying the auxiliary-function decrease condition yields a monotone algorithm, not only the MM minimizer.
  • 3.2 Separable auxiliary function for β-NMF: The β-NMF auxiliary function majorizes the convex part with Jensen’s inequality and the concave part by its tangent.
  • 3.2 Separable auxiliary function for β-NMF: The resulting auxiliary function is separable across coefficients, allowing the optimization to decouple.
  • 3.2 Separable auxiliary function for β-NMF: Its Hessian is diagonal and positive definite under d′′(x|y) ≥ 0, so the auxiliary function is convex.
  • 3.2 Separable auxiliary function for β-NMF: For β ∈ [1, 2], the construction coincides with Kompass’s auxiliary function, while β = 0 recovers Cao et al.’s IS auxiliary function.

4 Algorithms for β-NMF

The paper develops MM and ME algorithms for β-NMF from a shared auxiliary function, clarifies when heuristic updates are monotone, and compares their step sizes and convergence behavior across β ranges.

  • MM algorithm: MM minimization yields multiplicative updates whose β-dependent exponent γ(β) differs from the usual heuristic exponent when β is outside [1, 2].The usual updates correspond to setting γ(β) = 1.
  • General auxiliary-function framework: The auxiliary function supports monotone β-NMF updates, including the MM update and any iterate satisfying the auxiliary-function decrease condition.The construction applies to the sequential factor updates used for β-NMF.
  • Heuristic algorithm: For β ∈(0, 1), the heuristic algorithm is proven to produce nonincreasing criterion values using the proposed auxiliary function.This extends the stated mathematical result beyond the convexity range where earlier monotonicity proofs applied.
  • ME algorithm: ME updates move along auxiliary-function level sets and, when the alternative solution exists, provide steps larger than MM updates while preserving nonincreasing criterion values.Closed-form ME updates are available for specific β values through polynomial root extraction.
  • ME algorithm: For β ∈(1, 2], ME updates do not necessarily exist, whereas for β < 0 they always exist and yield nonincreasing criterion values.For β > 2, ME updates also do not necessarily exist and the analysis is not pursued in detail.
  • Convergence behavior: For β ∈(0, 1), the heuristic update ensures descent, while ME uses the largest admissible learning rate η = 2 near the solution; simulations report faster practical convergence for ME.For β < 0, simulations instead indicate the heuristic algorithm is faster than ME, which is faster than MM.

5 Simulations

The simulations compare heuristic, MM, and ME algorithms across synthetic, audio, and face-data settings. ME generally converges faster while reaching comparable solutions, although heuristic updates can be faster initially in audio experiments.

  • 5.1 Factorization of synthetic data: Synthetic-data costs converge to zero for all tested β values, with KKT residuals confirming convergence and comparable solutions across algorithms for β = 0.5 and β = 1.5.The data admit an exact factorization, so zero divergence is attainable.
  • 5.1 Factorization of synthetic data: A few hundred iterations generally produce sufficiently small fit residuals, although factor iterates need not recover the ground-truth factors because NMF has identifiability ambiguities.The conclusion concerns satisfying solutions rather than exact recovery of W* and H*.
  • 5.2 Audio spectrogram decomposition: On the piano spectrogram, ME converges fastest overall, while musical pitch values reach their ground-truth values after 30, 50, and 580 iterations for ME, heuristic, and MM, respectively.The algorithms were manually checked to recover notes, transients, and residual-noise spectra.
  • 5.2 Audio spectrogram decomposition: The heuristic algorithm can decrease the objective fastest initially, after which ME often becomes faster; MM is generally slower than the other two methods.Some runs instead produced faster pitch convergence with the heuristic algorithm.
  • 5.3 Face data decomposition: On Olivetti face data, experiments with β ∈ {1.5, 2} illustrate faster convergence for ME than MM, while image-quality assessment can favor β = 2 because PSNR is Euclidean-based.Perceptually, β = 3 was often judged more satisfying than β = 2 in the reported interpolation example.

6 Variants of β-NMF

The paper extends β-NMF to penalized and convex variants using auxiliary-function constructions. These extensions preserve monotonicity in some settings, but closed-form updates depend on the penalty and β range.

  • Penalized β-NMF: Penalized β-NMF adds separable penalty terms to factor estimation, allowing regularization or prior beliefs to be incorporated into the objective.The resulting subproblem combines β-divergence reconstruction with a penalty L(h).
  • Penalized β-NMF: Auxiliary functions for penalized objectives can support MM or ME algorithms, with the specific construction handled case by case.The paper illustrates this approach using ℓ1-norm regularization.
  • Penalized β-NMF: For β ≤ 1, ℓ1-regularized β-NMF yields simple MM updates and proven monotonicity for KL-NMF and IS-NMF.The result follows from the proposed auxiliary-function construction.
  • Penalized β-NMF: For β ∈ (1, 2), the penalized MM algorithm lacks a simple closed-form update, whereas β ≥ 2 requires careful handling of the nonnegativity constraint.ME algorithms can still be designed, and the closed-form-update ranges from the unpenalized setting remain applicable for the ℓ1-regularized problem.
  • Convex β-NMF: Convex-NMF constrains the dictionary to a known subspace, including settings where dictionary elements are combinations of data points or narrow-band spectra.This can enforce data-centroid structure, harmonicity, or smoothness.
  • Convex β-NMF: The convex-NMF dictionary update can be reformulated as vectorial nonnegative linear regression, enabling the β-NMF algorithms to produce efficient matricial updates.The paper states that the result extends Euclidean convex-NMF to the general β-divergence and proves monotonicity for some heuristic algorithms.

7 Conclusions

The paper develops auxiliary-function-based descent algorithms for β-NMF, establishes monotonicity results, and reports faster convergence for ME updates. It also extends the framework to penalized and convex-NMF, while leaving broader monotonicity and convergence questions open.

  • Contributions: The auxiliary function majorizes the β-NMF objective and unifies constructions for Euclidean, KL, generalized, and Itakura-Saito divergences.It yields parameter-free descent algorithms, including MM and ME methods.
  • Contributions: MM produces multiplicative algorithms for all β, coinciding with the heuristic algorithm on the convex range β ∈[1, 2].The general MM updates are described by Eq. (38), while the heuristic correspondence is established for β ∈[1, 2].
  • Contributions: Monotonicity of the heuristic algorithm is proven for β ∈(0, 1), extending the known result to β ∈[0, 2].The extension combines the new proof on (0,1) with existing results for β = 0 and β ∈[1,2].
  • Contributions: ME algorithms provide faster convergence than MM or heuristic updates for selected β values with equivalent complexity.For β ∈{0.5, 1.5, 2}, the ME updates solve polynomial equations of order 1 or 2; for β = 0, ME coincides with the heuristic algorithm.
  • Extensions: The framework handles penalized NMF and convex-NMF, including simple multiplicative algorithms for ℓ1-regularized KL or IS NMF.For convex-NMF, the paper generalizes and proves monotonicity of existing algorithms.
  • Open questions: Monotonicity remains unproved for the heuristic algorithm when β ∉[0, 2], and general convergence of β-NMF iterates to stationary points is still lacking.The paper also notes scale ambiguity as a difficulty in studying convergence and identifies extensions of newer algorithms as future work.
Loading 1010.1763v3…