Randomized Nonnegative Matrix Factorization
arXiv:1711.02037 · doi:10.1016/j.patrec.2018.01.007
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.
arXiv commentThis is an extended and revised version of the paper which appeared in JPRL
References in corpus (14)
- Scikit-learn: Machine Learning in Python
- The Why and How of Nonnegative Matrix Factorization
- Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization
- Sparse Principal Component Analysis via Variable Projection
- Algorithms, Initializations, and Convergence for the Nonnegative Matrix Factorization
- Improving CUR Matrix Decomposition and the Nyström Approximation via Adaptive Sampling
- Randomized Matrix Decompositions using R
- Compressed Nonnegative Matrix Factorization is Fast and Accurate
- Introduction to Nonnegative Matrix Factorization
- An implementation of a randomized algorithm for principal component analysis
- RSVDPACK: An implementation of randomized algorithms for computing the singular value, interpolative, and CUR decompositions of matrices on multi-core and GPU architectures
- Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
- A randomized algorithm for principal component analysis
- Why are Big Data Matrices Approximately Low Rank?
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