Block Majorization Minimization with Extrapolation and Application to
  $β$-NMF
Le Thi Khanh Hien Valentin Leplat Nicolas Gillis
We propose a Block Majorization Minimization method with Extrapolation (BMMe)
for solving a class of multi-convex optimization problems. The extrapolation
parameters of BMMe are updated using a novel adaptive update rule. By showing
that block majorization minimization can be reformulated as a block mirror
descent method, with the Bregman divergence adaptively updated at each
iteration, we establish subsequential convergence for BMMe. We use this method
to design efficient algorithms to tackle nonnegative matrix factorization
problems with the $\beta$-divergences ($\beta$-NMF) for $\beta\in [1,2]$. These
algorithms, which are multiplicative updates with extrapolation, benefit from
our novel results that offer convergence guarantees. We also empirically
illustrate the significant acceleration of BMMe for $\beta$-NMF through
extensive experiments.