Id: arxiv/2606.22451 Url: https://arxiv.org/abs/2606.22451 Tags: math.NA, cs.CG Score: 0 Title: Exact Nonnegative Matrix Factorization via Cone-Ray Witnesses: Certificates, a One-Sided Solver, and a Findability Phase Transition Domain: math.NA Source: arxiv Authors: Mithil Ramteke Reviews: 0 Subject: math.NA Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-06-21 Page: https://delphi.science/r/arxiv/2606.22451 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; witness feasibility is a certificate 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…