TOPICS
Search

Nonnegative Matrix Factorization

A nonnegative matrix factorization of a nonnegative matrix X in R^(m×n) is an expression X=WH with nonnegative matrices W in R^(m×r) and H in R^(r×n). The approximation problem fixes the inner dimension r and minimizes the Frobenius norm ||X-WH||_F over such factors (Vandaele 2026). The abbreviation NMF is used for both settings.

Vandaele (2026) proved that finding a globally best approximation is a strongly NP-hard problem already for r=2, even when X is a symmetric positive definite matrix with nonnegative integer entries of polynomially bounded size. The same hardness holds for the symmetric approximation X approx WW^T. This does not contradict polynomial-time decidability of the existence of an exact factorization for every fixed r (Vandaele 2026).

See also

Frobenius Norm, Matrix Decomposition, Nonnegative Matrix, Singular Value Decomposition

Explore with Wolfram|Alpha

References

Vandaele, A. "Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization." 15 Oct 2026. https://arxiv.org/abs/2610.21874.

Cite this as:

Weisstein, Eric W. "Nonnegative Matrix Factorization." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NonnegativeMatrixFactorization.html

Subject classifications