I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Publications - Nonnegative Matrix Factorization Requires Irrationality


Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell. Nonnegative matrix factorization requires irrationality. SIAM Journal on Applied Algebra and Geometry (SIAGA), 1(1):285–307, 2017.


Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative nxm matrix M into a product of a nonnegative nxd matrix W and a nonnegative dxm 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.

Suggested BibTeX entry:

    author = {Dmitry Chistikov and Stefan Kiefer and Ines Marusic and Mahsa Shirmohammadi and James Worrell},
    journal = {SIAM Journal on Applied Algebra and Geometry (SIAGA)},
    number = {1},
    pages = {285--307},
    publisher = {SIAM},
    title = {Nonnegative Matrix Factorization Requires Irrationality},
    volume = {1},
    year = {2017}

PDF (439 kB)
See doi.org ...