Fixed-rank NP-hardness conjecture for nonnegative rank

For a nonnegative matrix MM, its nonnegative rank rank+(M)\operatorname{rank}_+(M) is the least inner dimension of a factorization of MM into two nonnegative matrices. The ordinary rank rank(M)\operatorname{rank}(M) is the usual matrix rank. Fixed-rank NP-hardness conjecture. Computing rank+(M)\operatorname{rank}_+(M) and a corresponding nonnegative factorization is NP-hard when rank(M)\operatorname{rank}(M) is fixed and at least 44, and possibly even when it is fixed at 33. The conjecture concerns the computational complexity of nonnegative rank at fixed ordinary rank; the source does not state that this problem has been resolved.

Sources & referencesView supporting material

Primary source

Nicolas Gillis and François Glineur, “On the Geometric Interpretation of the Nonnegative Rank”, arXiv:1009.0880 (2010).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.