Randomized Nonnegative Matrix Factorization

Abstract

Nonnegative matrix factorization (NMF) is a powerful tool for data mining. However, the emergence of `big data' has severely challenged our ability to compute this fundamental decomposition using deterministic algorithms. This paper presents a randomized hierarchical alternating least squares (HALS) algorithm to compute the NMF. By deriving a smaller matrix from the nonnegative input data, a more efficient nonnegative decomposition can be computed. Our algorithm scales to big data applications while attaining a near-optimal factorization. The proposed algorithm is evaluated using synthetic and real world data and shows substantial speedups compared to deterministic HALS.

This is an extended and revised version of the paper which appeared in JPRL

References in corpus (1)

• Sparse Principal Component Analysis via Variable Projection

Cited by in corpus (13)

• Accelerating Nonnegative Matrix Factorization Algorithms using Extrapolation
• Projection-based QLP Algorithm for Efficiently Computing Low-Rank Approximation of Matrices
• Randomized methods to characterize large-scale vortical flow network
• Probabilistic methods for approximate archetypal analysis
• PLANC: Parallel Low Rank Approximation with Non-negativity Constraints
• Fast Convolutive Nonnegative Matrix Factorization Through Coordinate and Block Coordinate Updates
• Faster-than-fast NMF using random projections and Nesterov iterations
• An Alternating Rank-K Nonnegative Least Squares Framework (ARkNLS) for Nonnegative Matrix Factorization
• Novel Algorithms based on Majorization Minimization for Nonnegative Matrix Factorization
• Diffusion Maps meet Nyström
• An L0-Norm Constrained Non-Negative Matrix Factorization Algorithm for the Simultaneous Disaggregation of Fixed and Shiftable Loads
• Gaussian Compression Stream: Principle and Preliminary Results
• RetinaMatch: Efficient Template Matching of Retina Images for Teleophthalmology