{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-21","reactions":{}}