Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
arXiv:1204.2436
Abstract
Nonnegative matrix factorization (NMF) has become a very popular technique in machine learning because it automatically extracts meaningful features through a sparse and part-based representation. However, NMF has the drawback of being highly ill-posed, that is, there typically exist many different but equivalent factorizations. In this paper, we introduce a completely new way to obtaining more well-posed NMF problems whose solutions are sparser. Our technique is based on the preprocessing of the nonnegative input data matrix, and relies on the theory of M-matrices and the geometric interpretation of NMF. This approach provably leads to optimal and sparse solutions under the separability assumption of Donoho and Stodden (NIPS, 2003), and, for rank-three matrices, makes the number of exact factorizations finite. We illustrate the effectiveness of our technique on several image datasets.
arXiv comment34 pages, 11 figures
References in corpus (6)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
- Two Algorithms for Orthogonal Nonnegative Matrix Factorization with Application to Clustering
- Using Underapproximations for Sparse Nonnegative Matrix Factorization
- On the Geometric Interpretation of the Nonnegative Rank
- Nonnegative Factorization and The Maximum Edge Biclique Problem
Cited by in corpus (27)
- Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
- Linked Component Analysis from Matrices to High Order Tensors: Applications to Biomedical Data
- Efficient Nonnegative Tucker Decompositions: Algorithms and Uniqueness
- Deep matrix factorizations
- Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
- Robust Near-Separable Nonnegative Matrix Factorization Using Linear Optimization
- Renormalization group flows of Hamiltonians using tensor networks
- Sparsity and adaptivity for the blind separation of partially correlated sources
- Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
- A Nonconvex Splitting Method for Symmetric Nonnegative Matrix Factorization: Convergence Analysis and Optimality
- Online Nonnegative Matrix Factorization with Outliers
- Compressed Nonnegative Matrix Factorization is Fast and Accurate
- Heuristics for Exact Nonnegative Matrix Factorization
- Introduction to Nonnegative Matrix Factorization
- Sparse and Non-Negative BSS for Noisy Data
- Sequential Dimensionality Reduction for Extracting Localized Features
- NMF with Sparse Regularizations in Transformed Domains
- Lower bounds on nonnegative rank via nonnegative nuclear norms
- A Characterization of the Non-Uniqueness of Nonnegative Matrix Factorizations
- Provably robust blind source separation of linear-quadratic near-separable mixtures
- Iteration complexity analysis of random coordinate descent methods for regularized convex problems
- Bayesian Allocation Model: Inference by Sequential Monte Carlo for Nonnegative Tensor Factorizations and Topic Models using Polya Urns
- Matrix-wise -constrained Sparse Nonnegative Least Squares
- Adaptive Weighted Multi-View Clustering
- A New Anchor Word Selection Method for the Separable Topic Discovery
- Convex Analysis of Mixtures for Separating Non-negative Well-grounded Sources
- Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization