Conference item
On restricted nonnegative matrix factorization
- Abstract:
-
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n × m matrix M into a product of a nonnegative n × d matrix W and a nonnegative d × m matrix H. Restricted NMF requires in addition that the column spaces of M and W coincide. Finding the minimal inner dimension d is known to be NP-hard, both for NMF and restricted NMF. We show that restricted NMF is closely related to a question about the nature of minimal probabilistic automata, posed by Paz in his seminal 1971 textbook. We use this connection to answer Paz’s question negatively, thus falsifying a positive answer claimed in 1974.
Furthermore, we investigate whether a rational matrix M always has a restricted NMF of minimal inner dimension whose factors W and H are also rational. We show that this holds for matrices M of rank at most 3 and we exhibit a rank-4 matrix for which W and H require irrational entries.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 650.1KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2016.103
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- ICALP 2016: 43rd International Colloquium on Automata, Languages and Programming
- Journal:
- ICALP2016: 43rd International Colloquium on Automata, Languages and Programming More from this journal
- Volume:
- 103
- Pages:
- 103:1-103:14
- Publication date:
- 2016-07-01
- Acceptance date:
- 2016-04-15
- DOI:
- EISSN:
-
1868-8969
- ISSN:
-
1868-8969
- Keywords:
- Pubs id:
-
pubs:623536
- UUID:
-
uuid:7308840d-83fb-4759-b803-9cb412fbb70d
- Local pid:
-
pubs:623536
- Source identifiers:
-
623536
- Deposit date:
-
2016-05-23
Terms of use
- Copyright holder:
- Chistikov et al
- Copyright date:
- 2016
- Notes:
- Copyright © Chistikov et al.; licensed under Creative Commons License CC-BY. This article was presented at the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) and is available online at [http://www.eatcs.org/icalp2016/103/paper.pdf].
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record