Factoring nonnegative matrices with linear programs

Abstract

This paper describes a new approach, based on linear programming, for computing nonnegative matrix factorizations (NMFs). The key idea is a data-driven model for the factorization where the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C such that X approximately equals CX and some linear constraints. The constraints are chosen to ensure that the matrix C selects features; these features can then be used to find a low-rank NMF of X. A theoretical analysis demonstrates that this approach has guarantees similar to those of the recent NMF algorithm of Arora et al. (2012). In contrast with this earlier work, the proposed method extends to more general noise models and leads to efficient, scalable algorithms. Experiments with synthetic and real datasets provide evidence that the new approach is also superior in practice. An optimized C++ implementation can factor a multigigabyte matrix in a matter of minutes.

17 pages, 10 figures. Modified theorem statement for robust recovery conditions. Revised proof techniques to make arguments more elementary. Results on robustness when rows are duplicated have been superseded by arxiv.org/1211.6687

References in corpus (3)

• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• A geometric analysis of subspace clustering with outliers
• A convex model for non-negative matrix factorization and dimensionality reduction on physical space

Cited by in corpus (45)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• A Practical Algorithm for Topic Modeling with Provable Guarantees
• Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
• Efficient Nonnegative Tucker Decompositions: Algorithms and Uniqueness
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• On Identifiability of Nonnegative Matrix Factorization
• Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization
• Self-Dictionary Sparse Regression for Hyperspectral Unmixing: Greedy Pursuit and Pure Pixel Search are Related
• Minimizing Latency for Secure Coded Computing Using Secret Sharing via Staircase Codes
• Compressed Nonnegative Matrix Factorization is Fast and Accurate
• Generalized Separable Nonnegative Matrix Factorization
• Noisy Matrix Completion under Sparse Factor Models
• CYCLADES: Conflict-free Asynchronous Machine Learning
• Topic Discovery through Data Dependent and Random Projections
• A Fast Gradient Method for Nonnegative Sparse Regression with Self Dictionary
• Convex relaxations of structured matrix factorizations
• A universality theorem for nonnegative matrix factorizations
• Dictionary-based Tensor Canonical Polyadic Decomposition
• Ellipsoidal Rounding for Nonnegative Matrix Factorization Under Noisy Separability
• Scalable methods for nonnegative matrix factorizations of near-separable tall-and-skinny matrices
• Stochastic Low-Rank Bandits
• Probabilistic Simplex Component Analysis
• An Oracle Inequality for Quasi-Bayesian Non-Negative Matrix Factorization
• Intersecting Faces: Non-negative Matrix Factorization With New Guarantees
• Matrix factorization with Binary Components
• Necessary and Sufficient Conditions for Novel Word Detection in Separable Topic Models
• Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
• Spectral Unmixing with Multiple Dictionaries
• Penalized matrix decomposition for denoising, compression, and improved demixing of functional imaging data
• Quantum Divide-and-Conquer Anchoring for Separable Non-negative Matrix Factorization
• Adaptive Estimation in Structured Factor Models with Applications to Overlapping Clustering
• A New Geometric Approach to Latent Topic Modeling and Discovery
• Optimal estimation of sparse topic models
• Interactive Topic Modeling with Anchor Words
• Necessary and Sufficient Conditions and a Provably Efficient Algorithm for Separable Topic Discovery
• How to Fake Multiply by a Gaussian Matrix
• A Unified Convergence Analysis of the Multiplicative Update Algorithm for Regularized Nonnegative Matrix Factorization
• Speeding up Linear Programming using Randomized Linear Algebra
• A fast algorithm with minimax optimal guarantees for topic models with an unknown number of topics
• Time series forecasting from partial observations via Non-negative Matrix Factorization
• Near-separable Non-negative Matrix Factorization with ${\ell }_1$- and Bregman Loss Functions
• Likelihood estimation of sparse topic distributions in topic models and its applications to Wasserstein document distance calculations
• An Empirical Comparison of Sampling Quality Metrics: A Case Study for Bayesian Nonnegative Matrix Factorization
• Rapid Posterior Exploration in Bayesian Non-negative Matrix Factorization
• Spectral Learning for Supervised Topic Models