PaperlayerView exact revision on arXiv

Source-linked AI summary

Strong NP-Hardness of Rank-2 Nonnegative Matrix Factorization

Arnaud Vandaele

arXiv:2610.21874v1math.OCcs.CC

TL;DR

With nonnegativity, best rank-2 NMF is nonconvex, and standard algorithms guarantee at most stationary points; its computational complexity was an open question. A polynomial-time reduction from Clique establishes strong NP-hardness, including for symmetric NMF.

  • Problem

    With nonnegativity, rank-2 NMF is nonconvex, and standard algorithms guarantee at most stationary points; whether computing a best rank-2 NMF is NP-hard was an open question.

    Source: §1 · p. 1

  • Method

    A polynomial-time reduction from Clique constructs symmetric positive-definite matrices with nonnegative integer entries to establish rank-2 NMF hardness.

    Source: §4 · p. 15

  • Results

    Computing a best rank-2 NMF in the Frobenius norm is strongly NP-hard, as is rank-2 symmetric NMF.

    Source: §4 · p. 15, §3 · p. 15

  • Takeaways & Limitations

    Unless P = NP, no polynomial-time algorithm can guarantee a globally optimal rank-2 NMF for every input.

    Source: §1.2 · p. 3

    The reduction uses input entries as large as Θ(N^6), leaving open whether hardness holds when entries are bounded by an absolute constant or are binary.

    Source: §4 · p. 16

Abstract

from arXiv · show

Nonnegative matrix factorization (NMF) approximates a nonnegative matrix by the product of two nonnegative matrices with a prescribed inner dimension~$r$. The existence of an exact NMF can be decided in polynomial time for every fixed~$r$, and a best rank-$1$ NMF in the Frobenius norm can be obtained from a truncated singular value decomposition. We prove that computing a best rank-$2$ NMF in the Frobenius norm is strongly NP-hard. Our proof uses a polynomial-time reduction from \textsc{Clique} that produces symmetric positive-definite, completely positive matrices with polynomially bounded integer entries. The same reduction also establishes strong NP-hardness of rank-$2$ symmetric NMF.

1 Introduction

The introduction frames globally optimal rank-2 NMF as the first nontrivial fixed-rank approximation case and establishes its strong NP-hardness. It situates the result against prior complexity guarantees and outlines the reduction, its extensions, and the paper’s notation.

1.1 Known complexity results

  • ExactNMF is polynomial-time solvable for fixed r, while prior fixed-r approximation guarantees do not establish a globally optimal solution.Rank-1-NMF is polynomial-time solvable, and rank-2 is optimal via truncated SVD when the unconstrained approximation is nonnegative.Source: §1.1 · p. 2

1 Introduction

  • Rank-2 is the first nontrivial fixed-rank case: nonnegativity can make truncated SVD infeasible, while alternating methods guarantee only stationary points.Rank-2 NMF also serves as a building block for recursive two-cluster methods in document clustering, hyperspectral imaging, and brain-tumor tissue characterization.Source: §1 · p. 1, §1.2 · p. 3

1.2 Contributions

  • Rank-2-NMF is strongly NP-hard via a polynomial-time Clique reduction, whose perturbation bounds preserve the encoded error gap when both rank-one terms vary.The reduction's matrices are symmetric, completely positive, and have nonnegative integer entries bounded polynomially in the graph size.Source: §1.2 · p. 3

1.3 Organization of the paper

  • Section 2 develops the Clique reduction, and Section 3 proves complete positivity and extends the hardness result to symmetric NMF.The paper describes the construction, error encoding, perturbation bounds, correctness proof, and numerical illustration across Section 2's subsections.Source: §1.3 · p. 4

1.4 Notation

  • The notation defines the Euclidean and Frobenius norms, entrywise matrix inequalities, positive and negative parts, and the graph's clique number.The Frobenius norm is associated with the trace inner product.Source: §1.4 · p. 4

2 NP-hardness of Rank-2-NMF

This section presents a polynomial-time reduction from Clique to establish strong NP-hardness of rank-2 NMF, using a threshold that encodes clique size in the approximation error. A numerical illustration shows how the rank-one correction reflects maximum-clique structure and reveals the clique {1, 3, 4, 6}.

2.1 Construction of the reduction

  • The reduction constructs an (N + 1) × (N + 1) instance in polynomial time, choosing d = 20N^3 and polynomial-size rational entries for X and T.It starts from a simple undirected graph with N vertices and its adjacency matrix.Source: §2.1 · pp. 4–5

2.2 Structure of the instance

  • The clique number determines whether the optimal residual error of C is at most T, with the threshold reached exactly when ω(G) ≥ J.A dominant rank-one term matches X’s last row and column; the remaining matrix C has signs reflecting edges and nonedges, which determine where a nonnegative rank-one correction can reduce error.Source: §2.2 · pp. 5–7

2.3 Bounds for general rank-two approximations

  • A general nonnegative rank-2 approximation can improve on the optimal residual error for C by at most 20N^2, independently of d.This bound lets the proof rule out improvements large enough to cross the gap between residual errors for consecutive clique sizes.Source: §2.3 · p. 9, §2.4 · p. 11

2.4 Correctness of the reduction

  • The reduction is correct in both directions: (X, T) is a yes-instance of Rank-2-NMF exactly when (G, J) is a yes-instance of Clique, establishing strong NP-hardness.The constructed numerical quantities have magnitudes, numerators, and denominators bounded polynomially in the number of vertices.Source: §2.4 · pp. 11–12

2.5 A numerical illustration

  • For N = 6 and J = 4, adjacent residual levels are separated by approximately 1234, exceeding Lemma 4’s maximum improvement of 720.The example illustrates why the gap can withstand improvements from varying both factors of a rank-2 approximation.Source: §2.5 · pp. 12–13, Table 2 · p. 13
  • The numerical error is approximately 2.97 below T because optimizing both rank-one terms can slightly improve on the approximation with vv^T fixed.Source: §2.5 · p. 13
  • For the solution, β is approximately 2.9364 and the Frobenius norm of R is approximately 9.62 × 10^-4.Source: §2.5 · p. 13
  • The entries of S indexed by C × C are approximately 1079.89, while entries involving vertices 2 or 5 have magnitude below 3 × 10^-3.Here C = {1, 3, 4, 6}.Source: §2.5 · p. 14
  • The matrix S = D − pq^T/δ is extremely close to the rank-one correction associated with the maximum clique and reveals clique {1, 3, 4, 6}.Source: §2.5 · pp. 13–14

3 Extension to symmetric NMF

The Clique reduction also proves strong NP-hardness for rank-2 symmetric NMF, without modification. The hardness holds even when the input matrix is completely positive.

3 Extension to symmetric NMF

  • Symmetric NMF approximates a symmetric nonnegative matrix by W W⊤ and is used in graph clustering.For nonnegative inputs, rank 2 is the first nontrivial fixed-rank case.Source: §3 · p. 14
  • The reduction's matrix X is completely positive, so it admits a symmetric nonnegative factorization.The proof establishes complete positivity by decomposing X into completely positive matrices.Source: §3 · pp. 14–15
  • Rank-2 symmetric NMF is strongly NP-hard even when the input matrix is completely positive.The reduction from Section 2 applies without modification.Source: §3 · pp. 14–15
  • The rank-2 symmetric NMF decision instance is equivalent to the original Clique instance.The reduction uses a symmetric factor W W⊤ for the rank-2 construction.Source: §3 · p. 15

4 Conclusion

The paper proves strong NP-hardness for best rank-2 NMF in the Frobenius norm by reducing from Clique, with the same reduction establishing hardness for rank-2 symmetric NMF. It closes with open questions about inputs with bounded entries and unconstrained rank-2 approximations with few negative entries.

4 Conclusion

  • Best rank-2 NMF in the Frobenius norm is strongly NP-hard by a polynomial-time reduction from Clique.The hardness also holds for symmetric positive-definite inputs with nonnegative integer entries bounded polynomially in the graph size.Source: §4 · p. 15
  • The same reduction establishes strong NP-hardness of rank-2 symmetric NMF.The constructed matrices are completely positive.Source: §4 · p. 15
  • When the best unconstrained rank-2 approximation is nonnegative, it is also optimal for the nonnegative problem.The paper identifies the cases with negative entries as a direction for further complexity study.Source: §4 · pp. 15–16
  • The reduction uses entries as large as Θ(N^6), leaving open whether hardness holds for constant-bounded or binary inputs.The paper also asks about the complexity when the best unconstrained rank-2 approximation has a fixed number of negative entries, especially one.Source: §4 · p. 16

A.1 Symmetrization of nonnegative rank-one approximations

For a symmetric positive semidefinite matrix, an optimal nonnegative rank-one approximation can be chosen symmetric. The proof shows that one of two symmetric candidates preserves optimality.

A.1 Symmetrization of nonnegative rank-one approximations

  • The result restricts the rank-one approximation to symmetric nonnegative factors for positive semidefinite inputs.This is the stated purpose of the lemma.Source: §A.1 · p. 19
  • An optimal nonnegative rank-one approximation of a symmetric positive semidefinite matrix can be written as λxx⊤.Here λ ≥ 0, x ≥ 0, and ∥x∥2 = 1.Source: §A.1 · p. 19
  • From an optimal λxy⊤, replacing it with the better of λxx⊤ and λyy⊤ preserves optimality.The argument uses symmetry and positive semidefiniteness of the target matrix.Source: §A.1 · p. 19
Loading 2610.21874v1…