A nonnegative matrix factorization of a nonnegative matrix is an expression
with nonnegative matrices
and
. The approximation problem fixes the
inner dimension
and minimizes the Frobenius
norm
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 , even when
is a symmetric positive
definite matrix with nonnegative integer
entries of polynomially bounded size. The same hardness holds for the symmetric approximation
. This does not contradict polynomial-time
decidability of the existence of an exact factorization for every fixed
(Vandaele 2026).