2016/05/23 by Dmitry Chistikov, Stefan Kiefer, Chistikov, Dmitry +7
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Machine Learning (cs.LG) #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.1605.07061
openalex publication_date 2016/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.