Fixed-rank NP-hardness conjecture for nonnegative rank

About 16 years old · traced to

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.

References

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.