Source-linked AI summary
On the complexity of nonnegative matrix factorization
Stephen A. Vavasis
TL;DR
The paper addresses whether nonnegative matrix factorization can be solved optimally by defining exact NMF and analyzing its computational structure. It proves equivalence with a polyhedral-combinatorics problem, establishes NP-hardness, and derives a polynomial-time local-search step. The formulation assumes rank(A) is known.
Problem
Existing NMF algorithms generally rely on local heuristics without optimality guarantees, leaving the difficulty of solving NMF optimally formally unresolved.
Method
The paper defines exact NMF and proves polynomial-time equivalences through P1, RESTRICTED P1, and INTERMEDIATE SIMPLEX.
Results
Exact NMF is NP-hard, and the equivalence proof also yields a polynomial-time linear-programming approach for a local-search heuristic.
Takeaways & Limitations
Exact NMF is computationally difficult, while certain local-search heuristic steps can be solved with linear programming.
Takeaways & Limitations
The exact-NMF formulation assumes that rank(A) is known.
Abstract
from arXiv · showhide
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.
1 Nonnegative matrix factorization
NMF factors a nonnegative matrix into lower-dimensional nonnegative matrices for clustering and feature discovery, but approximation conventions vary. This paper formalizes exact NMF and proves it is NP-hard, while relating the result to broader formulations.
- Motivation: NMF has been applied to feature discovery in image databases and topic-based document clustering.The passage also cites applications in probability, quantum mechanics, and other fields.
- Problem definition: NMF represents a nonnegative matrix A approximately as WH, where W and H are nonnegative matrices with inner dimension k.Authors may use different approximation senses and may impose sparsity on W, H, or both.
- Motivation: Existing NMF algorithms generally use local-improvement or greedy rank-one-downdating heuristics without optimality guarantees.This lack of guarantees motivates asking whether solving NMF optimally is computationally difficult.
- Contributions: The paper proves that exact NMF is NP-hard and relates the result to approximation versions and nonnegative rank determination.The authors argue that standard approximation NMF generalizes exact NMF, and state that nonnegative rank determination is also NP-hard.
- Exact NMF: Exact NMF requires a nonnegative rank-k matrix A to equal WH exactly, or reports that no such factorization exists.Its decision version answers whether such nonnegative W and H exist.
- Scope: The formalization assumes that rank(A) is known, which can be determined in polynomial time for rational input using row-echelon reduction.In practice, the paper says singular value decomposition would usually be preferred.
2 Equivalence to Intermediate Simplex
The paper proves a polynomial-time equivalence between exact NMF and the polyhedral-combinatorics problem INTERMEDIATE SIMPLEX through matrix transformation problems. The reductions preserve yes-instances and operate polynomially in the matrix dimensions.
- Complexity of reductions: The reductions use polynomially many arithmetic operations in m and n, so they are polynomial-time in both stated computational models.The paper discusses both the usual Turing machine model and the real-number model of Blum et al.
- Equivalence construction: The equivalence proof proceeds through P1, a problem asking for a nonsingular change of basis that makes both transformed factors nonnegative.The unrestricted P1 instance assumes W0 and H0 have rank k and W0H0 is nonnegative.
- Equivalence construction: EXACT NMF is reduced to P1 and P1 is reduced back to EXACT NMF in polynomial time.P1 asks whether a nonsingular Q makes W0Q^-1 and QH0 simultaneously nonnegative.
- Restricted P1: A restricted P1 version requires the last column of W0 to consist entirely of 1s, simplifying the main proof.The paper states this restriction as an intermediate formulation.
RESTRICTED P1
RESTRICTED P1 is polynomial-time equivalent to both P1 and INTERMEDIATE SIMPLEX, linking exact factorization feasibility to simplex containment. The transformations also yield a linear-time exact factorization algorithm when rank(A) = 2.
- RESTRICTED P1: P1 and RESTRICTED P1 are polynomial-time reducible to each other.
- RESTRICTED P1: RESTRICTED P1 is polynomial-time equivalent to INTERMEDIATE SIMPLEX through a bijection computable in polynomial time.The correspondence maps matrix constraints to a polyhedron P and points S, preserving the relevant rank and containment conditions.
- RESTRICTED P1: A simplex T solves INTERMEDIATE SIMPLEX exactly when its vertex matrix G^T solves the corresponding RESTRICTED P1 instance.The equivalence follows by expressing each point in S as a convex combination of T's vertices and requiring nonnegative coefficients, while T ⊂ P becomes nonnegativity of H0G.
- RESTRICTED P1: Rank(A) = 2 always gives a yes-instance of exact NMF.The transformed INTERMEDIATE SIMPLEX instance is one-dimensional, so P is an interval and can itself serve as the simplex.
- RESTRICTED P1: Rank(A) = 2 therefore admits a simple linear-time algorithm for finding an exact nonnegative factorization.This consequence was previously established by Cohen and Rothblum, who also proposed a simple linear-time algorithm.
3 INTERMEDIATE SIMPLEX is NP-hard
INTERMEDIATE SIMPLEX is shown NP-hard by a polynomial-size reduction from 3-SAT. The constructed simplex encodes Boolean assignments through variable-specific vertex configurations, with clause constraints enforcing satisfiability.
- Assignment encoding: The gadget has precisely two feasible simplex solutions, corresponding to the two Boolean settings of a variable.The two solutions are T0 and T1 in the unit square construction.
- Reduction from 3-SAT: The reduction from 3-SAT to INTERMEDIATE SIMPLEX uses polynomially bounded integers, establishing strong NP-hardness.The construction has 3p + q variables representing three coordinates per Boolean variable and one coordinate per clause.
- Reduction from 3-SAT: A 3-SAT instance is satisfiable if and only if the constructed instance has a simplex T satisfying S ⊂T ⊂P.This equivalence is the main correctness statement of the reduction.
- Assignment encoding: Each variable’s three xi coordinates must contribute exactly three xi-positive simplex vertices, allowing the variable to be classified into C0 or C1.The classification determines the corresponding Boolean assignment.
- Clause enforcement: For the assignment derived from C0 and C1, each clause has at most two falsified literals and therefore is satisfied.The quantity mj counts falsified literals in clause cj, and the construction proves mj ≤2.
4 Local-search heuristics
The paper derives a local-search heuristic from the geometry of INTERMEDIATE SIMPLEX. With all but one simplex vertex fixed, feasible positions for the remaining vertex form a polyhedron, enabling convex optimization criteria.
- Feasible vertex positions: With all but one vertex of a solution simplex fixed, feasible positions for the remaining vertex satisfy mk equalities and n + mk inequalities.The constraints come from keeping the simplex inside P and covering the points in S.
- Feasible vertex positions: The remaining-vertex constraints become linear after rearranging the simplex-membership conditions.Points already in the hull of the fixed vertices impose no constraint; other points impose linearized feasibility conditions.
- Local search: A heuristic can start with a large simplex covering S and adjust vertices one at a time toward feasibility.The vertex update can optimize criteria such as 2-norm distance to feasibility.
- Local search: Because each vertex’s feasible positions form a polyhedron, criteria such as 2-norm distance to feasibility are convex programs.This provides the computational basis for the proposed local-search heuristic.