Heuristics for Exact Nonnegative Matrix Factorization
arXiv:1411.7245 · doi:10.1007/s10898-015-0350-z
Abstract
The exact nonnegative matrix factorization (exact NMF) problem is the following: given an -by- nonnegative matrix and a factorization rank , find, if possible, an -by- nonnegative matrix and an -by- nonnegative matrix such that . In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic -gons and conjecture the exact value of (i) the extension complexity of regular -gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.
arXiv comment32 pages, 2 figures, 16 tables
References in corpus (14)
- The Why and How of Nonnegative Matrix Factorization
- Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization
- Lifts of convex sets and cone factorizations
- Using Underapproximations for Sparse Nonnegative Matrix Factorization
- Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing
- On the Geometric Interpretation of the Nonnegative Rank
- Extended formulations for polygons
- Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
- The matching polytope has exponential extension complexity
- On the Linear Extension Complexity of Regular n-gons
- Computing The Extension Complexities of All 4-Dimensional 0/1-Polytopes
- Nonnegative rank depends on the field II
- Dagstuhl Report 13082: Communication Complexity, Linear Optimization, and lower bounds for the nonnegative rank of matrices
- Rational and real positive semidefinite rank can be different
Cited by in corpus (10)
- Online Nonnegative Matrix Factorization with Outliers
- Introduction to Nonnegative Matrix Factorization
- Simple Information Processing Tasks with Unbounded Quantum Advantage
- Algorithms for Positive Semidefinite Factorization
- Solving the Maximum Clique Problem with Symmetric Rank-One Nonnegative Matrix Approximation
- On the Linear Extension Complexity of Regular n-gons
- On Exact and -Rényi Common Informations
- Conic-Optimization Based Algorithms for Nonnegative Matrix Factorization
- Novel Algorithms based on Majorization Minimization for Nonnegative Matrix Factorization
- Matrix product constraints by projection methods