On restricted nonnegative matrix factorization

Conference item

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.

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

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl
• Host title: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
• Pages: 103:1-103:14
• Series: Leibniz International Proceedings in Informatics
• Series number: 55
• Publication date: 2016-08-23
• Acceptance date: 2016-04-15
• Event title: International Colloquium on Automata, Languages and Programming 2016 (ICALP 2016)
• Event location: Rome, Italy
• Event website: https://www.easyconferences.eu/icalp2016/
• Event start date: 2016-07-11
• Event end date: 2016-07-15
• DOI: 10.4230/LIPIcs.ICALP.2016.103
• ISSN: 1868-8969
• Language: English
• Keywords: nonnegative rank; nonnegative matrix factorization; probabilistic automata; labelled Markov chains; minimization