On the complexity of nonnegative matrix factorization

Stephen A. Vavasis

On the complexity of nonnegative matrix factorization

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 0708.4149 v2 pith:LBFBY36L submitted 2007-08-30 cs.NA cs.IRcs.NA

Stephen A. Vavasis This is my paper

classification cs.NAcs.IR

keywords databasesexactfactorizationmatrixnonnegativeanalysisapplicationsbecome

verification ladder T0 review T1 audit T2 compute T3 formal

0 comments

read the original abstract

Nonnegative matrix factorization (NMF) has become a prominent technique for the analysis of image databases, text databases and other information retrieval and clustering applications. In this report, we define an exact version of NMF. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a polynomial-time local search heuristic exists.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Bayesian Non-Negative Matrix Factorization with Correlated Mutation Type Probabilities for Mutational Signatures
q-bio.QM 2025-06 reject novelty 6.0 of 10

A Bayesian NMF model with a correlated multivariate normal prior for mutational signatures is proposed, but the claimed accuracy gain is only demonstrated in favorable simulations.

Pith tools