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 algorithm that runs in time singly-exponential in $r$. This algorithm (and earlier algorithms) are built on ... more >>>

Let us call a matrix $X$ as a linear matrix if its entries are affine forms, i.e. degree one polynomials. What is a minimal-sized representation of a given matrix $F$ as a product of linear matrices? Finding such a minimal representation is closely related to finding an optimal way to ... more >>>