Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization

Abstract

Nonnegative matrix factorization (NMF) is a data analysis technique used in a great variety of applications such as text mining, image processing, hyperspectral data analysis, computational biology, and clustering. In this paper, we consider two well-known algorithms designed to solve NMF problems, namely the multiplicative updates of Lee and Seung and the hierarchical alternating least squares of Cichocki et al. We propose a simple way to significantly accelerate these schemes, based on a careful analysis of the computational cost needed at each iteration, while preserving their convergence properties. This acceleration technique can also be applied to other algorithms, which we illustrate on the projected gradient method of Lin. The efficiency of the accelerated algorithms is empirically demonstrated on image and text datasets, and compares favorably with a state-of-the-art alternating nonnegative least squares algorithm.

17 pages, 10 figures. New Section 4 about the convergence of the accelerated algorithms; Removed Section 5 about efficiency of HALS. Accepted in Neural Computation

Cited by in corpus (34)

• On Tensors, Sparsity, and Nonnegative Factorizations
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization
• Efficient Nonnegative Tucker Decompositions: Algorithms and Uniqueness
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• On the Geometric Interpretation of the Nonnegative Rank
• Randomized Nonnegative Matrix Factorization
• Improved SVD-based Initialization for Nonnegative Matrix Factorization using Low-Rank Correction
• Coordinate Descent Methods for Symmetric Nonnegative Matrix Factorization
• Algorithms and Comparisons of Non-negative Matrix Factorization with Volume Regularization for Hyperspectral Unmixing
• Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation
• Generalized Separable Nonnegative Matrix Factorization
• Heuristics for Exact Nonnegative Matrix Factorization
• Exact and Heuristic Algorithms for Semi-Nonnegative Matrix Factorization
• Sparse and Non-Negative BSS for Noisy Data
• An AO-ADMM approach to constraining PARAFAC2 on all modes
• A Fast Gradient Method for Nonnegative Sparse Regression with Self Dictionary
• A Flexible Optimization Framework for Regularized Matrix-Tensor Factorizations with Linear Couplings
• Sequential Dimensionality Reduction for Extracting Localized Features
• NMF with Sparse Regularizations in Transformed Domains
• Dictionary-based Tensor Canonical Polyadic Decomposition
• Algorithms for Positive Semidefinite Factorization
• Multiplicative Updates for NMF with $\beta$-Divergences under Disjoint Equality Constraints
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• Semi-Blind Source Separation with Learned Constraints
• PARAFAC2 AO-ADMM: Constraints in all modes
• Least-squares methods for nonnegative matrix factorization over rational functions
• Nonnegative OPLS for Supervised Design of Filter Banks: Application to Image and Audio Feature Extraction
• Smoothed Separable Nonnegative Matrix Factorization
• Spectral Unmixing with Multiple Dictionaries
• Joint deconvolution and unsupervised source separation for data on the sphere
• Machine Learning for automatic identification of new minor species
• Bounded Simplex-Structured Matrix Factorization: Algorithms, Identifiability and Applications
• Conic-Optimization Based Algorithms for Nonnegative Matrix Factorization