Fixed-rank NP-hardness conjecture for nonnegative rank
Fixed-rank NP-hardness conjecture for nonnegative rank
For a nonnegative matrix , its nonnegative rank is the least inner dimension of a factorization of into two nonnegative matrices. The ordinary rank is the usual matrix rank. Fixed-rank NP-hardness conjecture. Computing and a corresponding nonnegative factorization is NP-hard when is fixed and at least , and possibly even when it is fixed at . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.