Nonnegative Matrix Factorization Requires Irrationality
This resolves a foundational theoretical problem in linear algebra and optimization, with implications for computational methods relying on rational approximations in NMF.
The paper tackled the longstanding open question of whether a rational matrix always has a nonnegative matrix factorization (NMF) with rational factors at minimal inner dimension, and it answered this negatively by exhibiting a matrix 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$. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix $M$ always has an NMF of minimal inner dimension $d$ whose factors $W$ and $H$ are also rational. We answer this question negatively, by exhibiting a matrix for which $W$ and $H$ require irrational entries.