Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation
This work addresses efficiency issues for researchers and practitioners using NMF in data analysis, though it is incremental as it builds on existing optimization techniques.
The paper tackled the problem of slow convergence in nonnegative matrix factorization (NMF) algorithms by proposing an extrapolation framework, resulting in significant acceleration of state-of-the-art methods like A-HALS and ANLS on synthetic, image, and document datasets.
In this paper, we propose a general framework to accelerate significantly the algorithms for nonnegative matrix factorization (NMF). This framework is inspired from the extrapolation scheme used to accelerate gradient methods in convex optimization and from the method of parallel tangents. However, the use of extrapolation in the context of the two-block exact coordinate descent algorithms tackling the non-convex NMF problems is novel. We illustrate the performance of this approach on two state-of-the-art NMF algorithms, namely, accelerated hierarchical alternating least squares (A-HALS) and alternating nonnegative least squares (ANLS), using synthetic, image and document data sets.