2026-08-01T02:20:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6238 2024-03-06T10:37:51Z ddc:004 open_access

On Restricted Nonnegative Matrix Factorization Chistikov, Dmitry Kiefer, Stefan Marusic, Ines Shirmohammadi, Mahsa Worrell, James nonnegative matrix factorization nonnegative rank probabilistic automata labelled Markov chains minimization 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dmitry Chistikov and Stefan Kiefer and Ines Marusic and Mahsa Shirmohammadi and James Worrell 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.103 urn:nbn:de:0030-drops-62389 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.103 eng https://creativecommons.org/licenses/by/3.0/legalcode