### On Rationality of Nonnegative Matrix Factorization

James Worrell

University of Oxford

SWS Distinguished Lecture Series

02 May 2017, 10:30 am - 1:30 pm

Saarbrücken building E1 5, room 002

simultaneous videocast to Kaiserslautern building G26, room 112

simultaneous videocast to Kaiserslautern building G26, room 112

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.

This is joint work with Dmitry Chistikov Stefan Kiefer Ines Marusic and Mahsa Shirmohammadi.