Conference item
On Rationality of Nonnegative Matrix Factorization
- Abstract:
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 485.2KB, Terms of use)
-
- Publisher copy:
- 10.1137/1.9781611974782.84
Authors
- 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 More from this journal
- Pages:
- 1290-1305
- Publication date:
- 2017-01-01
- Acceptance date:
- 2016-10-05
- DOI:
- ISBN:
- 9781611974782
- Pubs id:
-
pubs:659135
- UUID:
-
uuid:397b3974-704f-400f-8086-60382cf463a5
- Local pid:
-
pubs:659135
- Source identifiers:
-
659135
- Deposit date:
-
2016-11-13
Terms of use
- Copyright holder:
- Copyright © by SIAM
- Copyright date:
- 2017
- Notes:
- Copyright © by SIAM. Conference proceeding to be presented at the ACM-SIAM Symposium on Discrete Algorithms, Barcelona Spain, January 16-19, 2017
If you are the owner of this record, you can report an update to it here: Report update to this record