2026/06/21 by Mithil Ramteke
#math.NA #cs.CG #cs.NA
We study exact nonnegative matrix factorization (NMF) of small exact-rank-r matrices through the polyhedral cones of nonnegative preimages of the truncated SVD. Restricting each factor to an r-subset of a cone's extreme rays collapses the factorization constraint to the entrywise nonnegativity of a single r x r witness matrix; feasibility of the witness certifies that an exact size-r NMF exists, decided in one matrix inverse. A single-coupling completeness theorem shows every size-r NMF is representable this way, for every m, and a one-sided relaxation gives a closed-form solver that provably dominates the two-sided witness, with an explicit criterion for its strict gain. Our main result concerns findability: at a fixed search budget, witness recoverability undergoes a sharp conic phase transition whose width collapses to a step as r grows. We rule out both a universal-constant explanation and a statistical-dimension explanation -- the cones' statistical dimension is flat across the transition, while the intrinsic-volume profile's variance tracks it. The transition is not an existence boundary: by completeness a ray-economical witness always exists and persists past the threshold, so what decays with m is its density among r-subsets. The threshold is thus budget-relative -- moving logarithmically as the candidate pool grows -- and combinatorial rather than smooth-conic; a single budget law bridges this finite-budget threshold to the budget-free existence limit. Obtuseness ranking surfaces a feasible witness near the top of astronomically many subsets; a two-sided union of one-sided relaxations recovers more than multi-start HALS on average across six distributions, while being deterministic, machine-exact, 8-160x faster, and a certifier. The theme: exact NMF always exists and is representable; only ray-economical findability, relative to a budget, transitions.