On Rationality of Nonnegative Matrix Factorization
James Worrell
University of Oxford
SWS Distinguished Lecture Series
James Worrell is a Professor of Computer Science at the University of Oxford. He currently holds on an EPSRC Established Career Fellowship on the subject of Verification of Linear Dynamical Systems.
The nonnegative rank of a nonnegative m x n matrix M is the smallest number d such that M can be written as the product M = WH of a nonnegative m x d matrix W and a nonnegative d x n matrix H. The notions of nonnegative rank and nonnegative matrix factorization have a wide variety of applications, including bioinformatics, computer vision, communication complexity, document clustering, and recommender systems. A longstanding open problem is whether, when M is a rational matrix, the factors W and H in a rank decomposition M=WH can always be chosen to be rational. In this talk we resolve this problem negatively and discuss consequences of this result for the computational complexity of computing nonnegative rank.
This is joint work with Dmitry Chistikov, Stefan Kiefer, Ines Marusic, and Mahsa Shirmohammadi.