Reference:

Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell. On restricted nonnegative matrix factorization. In Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 103:1–103:14, 2016.

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.

Suggested BibTeX entry:

@inproceedings{16CKMSW-ICALP,
    author = {Dmitry Chistikov and Stefan Kiefer and Ines Marusic and Mahsa Shirmohammadi and James Worrell},
    booktitle = {Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
    pages = {103:1--103:14},
    series = {Leibniz International Proceedings in Informatics (LIPIcs)},
    title = {On Restricted Nonnegative Matrix Factorization},
    volume = {55},
    year = {2016}
}