Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation

Abstract

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.

19 pages, 6 figures, 6 tables. v2: few typos corrected, additional comparison with the extrapolated projected gradient method of Xu and Yin (SIAM J. on Imaging Sciences, 2013)

References in corpus (2)

• Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering
• Randomized Nonnegative Matrix Factorization

Cited by in corpus (10)

• Deep matrix factorizations
• Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• Multiplicative Updates for NMF with $\beta$-Divergences under Disjoint Equality Constraints
• Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization
• Nesterov Acceleration of Alternating Least Squares for Canonical Tensor Decomposition: Momentum Step Size Selection and Restart Mechanisms
• Block Majorization Minimization with Extrapolation and Application to $\beta$-NMF
• An Alternating Rank-K Nonnegative Least Squares Framework (ARkNLS) for Nonnegative Matrix Factorization
• On the Asymptotic Linear Convergence Speed of Anderson Acceleration, Nesterov Acceleration, and Nonlinear GMRES
• Computing cone-constrained singular values of matrices