Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing

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.

34 pages, 11 figures

References in corpus (2)

• Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
• Two Algorithms for Orthogonal Nonnegative Matrix Factorization with Application to Clustering

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 ${\ell }_0$ regularized convex problems
• Bayesian Allocation Model: Inference by Sequential Monte Carlo for Nonnegative Tensor Factorizations and Topic Models using Polya Urns
• Matrix-wise ${\ell }_0$-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