Nonnegative Matrix Factorization Requires Irrationality

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. 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.

Tasks

Reproductions