The Why and How of Nonnegative Matrix Factorization

Abstract

Nonnegative matrix factorization (NMF) has become a widely used tool for the analysis of high-dimensional data as it automatically extracts sparse and meaningful features from a set of nonnegative data vectors. We first illustrate this property of NMF on three applications, in image processing, text mining and hyperspectral imaging --this is the why. Then we address the problem of solving NMF, which is NP-hard in general. We review some standard NMF algorithms, and also present a recent subclass of NMF problems, referred to as near-separable NMF, that can be solved efficiently (that is, in polynomial time), even in the presence of noise --this is the how. Finally, we briefly describe some problems in mathematics and computer science closely related to NMF via the nonnegative rank.

25 pages, 5 figures. Some typos and errors corrected, Section 3.2 reorganized

Cited by in corpus (39)

• Deep matrix factorizations
• On Identifiability of Nonnegative Matrix Factorization
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• Factorizer: A Scalable Interpretable Approach to Context Modeling for Medical Image Segmentation
• Randomized Nonnegative Matrix Factorization
• Improved SVD-based Initialization for Nonnegative Matrix Factorization using Low-Rank Correction
• Learning From Hidden Traits: Joint Factor Analysis and Latent Clustering
• 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
• Recommendations and User Agency: The Reachability of Collaboratively-Filtered Information
• Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective
• A Fast Gradient Method for Nonnegative Sparse Regression with Self Dictionary
• A literature survey of matrix methods for data science
• Sequential Dimensionality Reduction for Extracting Localized Features
• Adaptive Nonnegative Matrix Factorization and Measure Comparisons for Recommender Systems
• A universality theorem for nonnegative matrix factorizations
• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
• Beyond Alternating Updates for Matrix Factorization with Inertial Bregman Proximal Gradient Algorithms
• Probabilistic Simplex Component Analysis
• Algorithms for Positive Semidefinite Factorization
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization
• Nonnegative Rank vs. Binary Rank
• Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization
• Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
• Non-negative Sparse and Collaborative Representation for Pattern Classification
• Contextual Bandits with Latent Confounders: An NMF Approach
• An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems
• Inertial Block Proximal Methods for Non-Convex Non-Smooth Optimization
• Sensing Cox Processes via Posterior Sampling and Positive Bases
• Time series forecasting from partial observations via Non-negative Matrix Factorization
• Convergence to Second-Order Stationarity for Non-negative Matrix Factorization: Provably and Concurrently
• Multiplicative Updates for Polynomial Root Finding
• A Non-monotone Alternating Updating Method for A Class of Matrix Factorization Problems
• Fast Parallel Randomized Algorithm for Nonnegative Matrix Factorization with KL Divergence for Large Sparse Datasets
• Is There Any Recovery Guarantee with Coupled Structured Matrix Factorization for Hyperspectral Super-Resolution?
• An L0-Norm Constrained Non-Negative Matrix Factorization Algorithm for the Simultaneous Disaggregation of Fixed and Shiftable Loads
• On Application of Block Kaczmarz Methods in Matrix Factorization