On Restricted Nonnegative Matrix Factorization
This addresses theoretical computational complexity and algebraic properties in matrix factorization, with incremental contributions to foundational mathematics and automata theory.
The paper tackled the problem of restricted nonnegative matrix factorization (NMF), showing it is related to a question about minimal probabilistic automata from 1971, and negatively answered Paz's question, falsifying a prior claim. It also investigated rational factorizations, proving existence for rank up to 3 and providing a rank-4 counterexample requiring irrational entries.
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative $n \times m$ matrix $M$ into a product of a nonnegative $n \times d$ matrix $W$ and a nonnegative $d \times 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.