On Rationality of Nonnegative Matrix Factorization

Conference item

Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n x m matrix M into a product of a nonnegative n x d matrix W and a nonnegative d x m matrix H. NMF has a wide variety of applications, in- cluding bioinformatics, chemometrics, communication com- plexity, machine learning, polyhedral combinatorics, among many others. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether every rational matrix M has an NMF with minimal d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix M for which W and H require irrational entries. As an application of this result, we show that state minimization of labeled Markov chains can require the introduction of irrational transition probabilities. We complement these irrationality results with an NP- complete version of NMF for which rational numbers suffice.

Authors: Chistikov, D; Kiefer, S; Marusic, I; Shirmohammadi, M; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona Spain, January 16-19, 2017
• Journal: Symposium on Discrete Algorithms
• Pages: 1290-1305
• Publication date: 2017-01-01
• Acceptance date: 2016-10-05
• DOI: 10.1137/1.9781611974782.84
• ISBN: 9781611974782