Icke-negativ matrisfaktorisering (NMF) har blivit en framträdande teknik för analys av bilddatabaser, textdatabaser och andra informationssöknings- och klustertillämpningar. I denna rapport definierar vi en exakt version av NMF. Sedan etablerar vi flera resultat om exakt NMF: (1) att det är likvärdigt med ett problem i polyhedral combinatorics; (2) att det är NP-hård; och (3) att en polynom-tid lokal sökning heuristic finns.
I själva verket har Ref visat att (1) är NP-hård.
On the complexity of nonnegative matrix factorization
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}