PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing a Nonnegative Matrix Factorization -- Provably

Sanjeev Arora, Rong Ge, Ravi Kannan, Ankur Moitra

arXiv:1111.0952v1cs.DScs.LG

TL;DR

The paper studies when exact and approximate nonnegative matrix factorization can be solved efficiently, especially for small inner-dimension r. It gives algorithms for constant r and separable inputs, while establishing strong hardness against substantially faster exact algorithms.

  • Problem

    NMF is computationally difficult in general, motivating a rigorous study of polynomial-time solvability when the inner-dimension r is small.

  • Method

    The paper combines algorithms for fixed r, a singly-exponential approach for simplicial factorization, a hardness reduction, and a polynomial-time algorithm under separability.

  • Results

    The Exact NMF algorithm runs in time O((nm)r2^2r), while no (nm)o(r)-time exact algorithm is possible under the Exponential Time Hypothesis.

  • Takeaways & Limitations

    The results rule out significant worst-case improvements for fixed r and identify separability as a condition enabling polynomial-time factorization.

  • Takeaways & Limitations

    The noise-tolerant separability result relies on benign assumptions, including allowing negligible nonzero entries and approximately satisfied separability.

Abstract

from arXiv · show

In the Nonnegative Matrix Factorization (NMF) problem we are given an $n \times m$ nonnegative matrix $M$ and an integer $r > 0$. Our goal is to express $M$ as $A W$ where $A$ and $W$ are nonnegative matrices of size $n \times r$ and $r \times m$ respectively. In some applications, it makes sense to ask instead for the product $AW$ to approximate $M$ -- i.e. (approximately) minimize $\norm{M - AW}_F$ where $\norm{}_F$ denotes the Frobenius norm; we refer to this as Approximate NMF. This problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where $A$ and $W$ are computed using a variety of local search heuristics. Vavasis proved that this problem is NP-complete. We initiate a study of when this problem is solvable in polynomial time: 1. We give a polynomial-time algorithm for exact and approximate NMF for every constant $r$. Indeed NMF is most interesting in applications precisely when $r$ is small. 2. We complement this with a hardness result, that if exact NMF can be solved in time $(nm)^{o(r)}$, 3-SAT has a sub-exponential time algorithm. This rules out substantial improvements to the above algorithm. 3. We give an algorithm that runs in time polynomial in $n$, $m$ and $r$ under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings. To the best of our knowledge, this last result is the first example of a polynomial-time algorithm that provably works under a non-trivial condition on the input and we believe that this will be an interesting and important direction for future work.

1 Introduction

The paper asks when NMF can be computed efficiently, especially for small inner-dimension r, and develops algorithms, hardness results, and a separability-based polynomial-time method.

  • NMF seeks nonnegative A and W with M = AW, where r is the inner-dimension and the smallest feasible r is the nonnegative rank.
  • Small-r NMF is important because hidden-variable interpretations are meaningful when r is much smaller than the numbers of documents or observations.
  • Polynomial-time algorithms solve exact NMF for every constant r, addressing the question of efficient computation in the small-inner-dimension regime.
  • O((nm)^r2^r) time is sufficient for Exact NMF, using first-order theory of the reals and a variable-reduction structure theorem.The general algorithm expresses feasibility as a semi-algebraic decision problem; the structure theorem reduces the number of variables to r2^r.
  • O((nm)^r2) time suffices for Exact Simplicial Factorization, where A is required to have linearly independent columns.The smaller system of equations may permit heuristic solvers whose solutions can then be checked for validity.
  • If exact NMF or Simplicial Factorization runs in (nm)^o(r) time, then 3-SAT has a 2^o(n)-time algorithm under the stated reduction.
  • Under separability, an exact factorization can be computed in time polynomial in n, m, and r, and the method can tolerate approximate separability and noise.Separability asserts that r rows of A can be permuted to form the identity matrix.
  • For approximate NMF, the paper gives an algorithm whose running time is singly exponential in r log(1/ϵ) and polynomial in n and m.

2 Simplicial Factorization

Simplicial Factorization restricts NMF to rank-r instances with full-column-rank A, making topic representations nonambiguous in the relevant convex-geometric sense.

  • Simplicial Factorization targets inner-dimension r while requiring rank(M) = r, so A has full column rank and M has full row rank.
  • After rescaling to unit ℓ1 norm, each column of M is a convex combination of the topic columns in A, with weights given by W.
  • If A lacks full column rank, Radon’s Lemma yields disjoint topic sets whose convex hulls intersect, allowing one document to have incompatible topic representations.
  • The simplicial problem can be solved in (nm)^O(r2) time using a reduction to finding a point in a semi-algebraic set with polynomially many constraints and O(r2) variables.
  • Pseudoinverses recover W from A+M and A from MW+, supporting the transformation-based characterization.
  • A structure lemma characterizes simplicial factorizations through basis-coordinate matrices and transformations whose products recover M while remaining nonnegative.

3 General NMF

The paper extends the fixed-r algorithmic framework to general NMF by reducing factorizations to polynomial systems with few variables, using minimal choices and simplicial partitions. This yields deterministic algorithms whose dependence on n and m is polynomial for fixed r, including exact factorization and rational approximation.

  • General NMF: The resulting deterministic algorithm outputs an inner-dimension-r factorization in O((nm)^(cr^2 2^r)) time when one exists.The same framework gives an algorithm for deciding nonnegative rank r in O((nm)^(O(r^2 2^r))) time and rational approximation in polynomial time in L, that bound, and log 1/δ.
  • General NMF: Fixing the choice functions reduces NMF to polynomial inequalities with O(r^2g(r)) variables, degree at most four, and O(mn) constraints.The remaining unknowns are r × r linear transformations satisfying factorization and nonnegativity constraints.
  • Minimality: A nonnegative factorization can be transformed into a proper chain with minimal-basis choices for columns and rows.The construction replaces a factorization by A′ and W′ while preserving inner dimension r and records minimal supports through choice functions.
  • Minimality: The factors’ columns and rows can be recovered from M using at most 2^r linear transformations.The transformations are determined by subsets of columns of A and rows of W′, so their number is constant when r is fixed.
  • Simplicial Partitions: Choice functions arising from proper chains are realizable as simplicial partitions, making their enumeration polynomially bounded for constant r.The partition class has small VC-dimension, which controls the number of relevant partitions.
  • Simplicial Partitions: Hyperplane and simplicial partitions can be enumerated algorithmically, including without additional conditions on M.The enumeration procedures provide the partition candidates needed by the general structure theorem, with the unrestricted version slightly slower.

4 Strong Intractability of Simplicial Factorization

The section reduces d-SUM to Simplicial Factorization through geometric Intermediate Simplex gadgets, establishing hardness parameterized by the inner dimension. The construction proves completeness and soundness: feasible simplices correspond exactly to d values summing to d/2.

  • Hardness reduction: If d-SUM instances with N distinct O(d log N)-bit values were solvable in N^o(d) time, then 3-SAT would have a sub-exponential algorithm.This conditional lower bound transfers to Simplicial Factorization through the reduction.
  • Intermediate Simplex: Intermediate Simplex asks for r affinely independent points in a polyhedron whose simplex contains all specified points.Vavasis showed this problem is polynomially equivalent to Simplicial Factorization while preserving r.
  • The gadget: The two-dimensional gadget encodes each input value s_i as a triangle A_iC_iE_i, with the constructed intersection polygon supplying the required points.The gadget uses a hexagonal polygon and points placed on three edges at distances proportional to ϵs_i.
  • The gadget: The gadget has exactly N valid triangles: every solution must be one of the triangles A_iC_iE_i.Lemma 4.6 establishes uniqueness when ϵ < 1/1000.
  • Completeness and soundness: Completeness maps any d values summing to d/2 to an Intermediate Simplex solution, while soundness recovers such a choice from every solution.Soundness requires ϵ < N^-Cd for a sufficiently large constant C; bit-length bounds force the recovered sum to equal d/2 exactly.

5 Fully-Efficient Factorization under Separability

Under separability, NMF can be recovered in time polynomial in n, m, and r by identifying factor rows hidden among the input rows. The method extends to noisy inputs under robust simpliciality and bounded perturbations.

  • Exact recovery: Separability requires each column of A to have a row with exactly one nonzero entry in that column.This condition makes certain rows of the input matrix equal to rows of W.
  • Exact recovery: A simplicial W has no row in the convex hull of the remaining rows, while robust simpliciality enforces a positive ℓ1 separation α.The noisy algorithm requires robust rather than ordinary simpliciality.
  • Exact recovery: Polynomial-time recovery finds a separable factorization of inner-dimension at most r whenever one exists.The algorithm uses linear programming to identify exactly r distinct loner rows, which recover W up to row permutation.
  • Exact recovery: A row is a loner if and only if it equals a row of W, enabling recovery of W from M.Simpliciality makes the rows corresponding to W precisely the loner rows.
  • Adding Noise: For noisy inputs, if 20ϵ/α + 13ϵ < α, a polynomial-time algorithm returns a same-dimension factorization whose rowwise residuals are at most 10ϵ/α + 7ϵ.The input is formed by perturbing each row of an exactly separable M by ℓ1-norm at most ϵ.

6 Approximate Nonnegative Matrix Factorization

Approximate NMF is addressed without structural assumptions on A and W by decomposing W into an approximation-relevant part and a nonnegativity-correcting part. Enumeration and convex programming then yield an approximate factorization with running time exponential only in r and log(1/ϵ).

  • Problem and guarantee: Approximate NMF seeks a nonnegative factorization AW close to M in Frobenius norm, without assumptions on A or W.The section handles matrices satisfying ∥M − AW∥F ≤ ϵ∥M∥F.
  • Algorithm: The algorithm decomposes W = W0 + W1, where W0 preserves approximation quality and W1 helps ensure nonnegativity.W0 is approximated using the span of M, while W1 is handled through convex programming.
  • Algorithm: The method uses truncated SVD, exhaustive enumeration over an ϵ-net, convex programming, and least squares to construct A′ and W′.The convex program separates across columns, and least squares chooses A′ after W′ is fixed.
  • Guarantee: 2^poly(r log(1/ϵ))poly(n, m) time suffices to find the required approximate components.The exponential dependence is confined to the inner dimension and accuracy parameter.
  • Guarantee: The resulting factorization satisfies ∥M − A′W′∥F ≤ O(ϵ^1/2 r^1/4)∥M∥F.The bound combines the approximation error from W0, the truncated-SVD contribution, and the convex-program objective.

Concluding Remarks

The paper initiates a rigorous study of NMF algorithms and identifies separability as a promising route to polynomial-time factorization. It frames this result as motivation for studying additional realistic conditions on the factors.

  • Concluding Remarks: The authors present their work as initiating a rigorous study of nonnegative matrix factorization.They seek greater rigor for solution concepts often approached heuristically in machine learning.
  • Concluding Remarks: The polynomial-time separable-factorization algorithm is offered as evidence that some machine-learning solution concepts may be tractable under suitable conditions.The conclusion poses identifying other plausible conditions on real-life factors as future work.

A Extended Discussion

NMF represents documents using nonnegative topics and topic mixtures, unlike SVD-based representations that use orthogonal vectors with positive and negative entries. This topic interpretation supports document-analysis tasks but can still be ambiguous.

  • SVD and NMF: In a term-by-document matrix, SVD uses orthogonal vectors, whose entries may be positive or negative.The rows represent observed variables and columns represent examples such as documents.
  • SVD and NMF: Negative SVD coordinates can make topic interpretations inconsistent with documents being mixtures of meaningful topics.Documents about distinct subjects may share negative correlations with unrelated words.
  • SVD and NMF: Probabilistic latent semantic indexing represents each document as a distribution over a small set of word-distribution topics, equivalent after renormalization to nonnegative factorization.The topic columns form A and document topic mixtures form W.
Loading 1111.0952v1…