A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

Ankur Moitra

Here, we give an algorithm for deciding if the nonnegative rank of a matrix $M$ of dimension $m\times n$ is at most $r$ which runs in time $(nm{)}^{O(r^2)}$. This is the first exact…