The nonnegative rank of a matrix: Hard problems, easy solutions

  • Yaroslav Shitov (National Research University - Higher School of Economics, Moscow)
G3 10 (Lecture hall)


I will explain how, using elementary linear algebra only, one can get solutions of two widely known problems on nonnegative matrices. The first one is a short proof of the known result stating that the nonnegative rank is NP-hard to compute, and the second one is an answer to the question on rational nonnegative factorizations asked by Cohen and Rothblum in 1993. I will explain how to generalize the results on spaces of factorizations and completely describe the algorithmic complexity not only of the nonnegative rank of a matrix but also of the related quantity known as positive semidefinite rank.

Katharina Matschke

MPI for Mathematics in the Sciences Contact via Mail