




Publications  On Restricted Nonnegative Matrix Factorization





Reference:
Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell. On restricted nonnegative matrix factorization. Technical report, arXiv.org, 2016. Available at https://arxiv.org/abs/1605.07061.
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 NPhard, 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 rank4 matrix for which W and H require irrational entries.
Suggested BibTeX entry:
@techreport{16CKMSWICALPTR,
author = {Dmitry Chistikov and Stefan Kiefer and Ines Marusic and Mahsa Shirmohammadi and James Worrell},
institution = {arXiv.org},
note = {Available at https://arxiv.org/abs/1605.07061},
title = {On Restricted Nonnegative Matrix Factorization},
year = {2016}
}




