Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NONNEGATIVE RANK:
Reports tagged with nonnegative rank:
TR12-053 | 30th April 2012
Ankur Moitra

#### A Singly-Exponential Time Algorithm for Computing Nonnegative Rank

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 >>>

ISSN 1433-8092 | Imprint