Chapter 6: Computational complexity of NMF
Nicolas Gillis · Society for Industrial and Applied Mathematics eBooks · 2020
In Chapter 2, we have seen that Exact NMF is easily solvable when rank(X) ≤ 2 (Theorem 2.6), and that it is NP-hard to check whether rank(X) = rank+ (X) (Theorem 2.20). However, Exact NMF can be solved in time O((mn)r2), implying it can be solved in polynomial time when the factorization rank r is not part of the input, that is, when r is assumed to be a fixed constant. However, this has not lead so far to practical algorithms for Exact NMF when r is small; see the discussion that follows Theorem 2.21.