{"id":"ab787b07-8b2e-4361-8666-fc592a6f40fb","arxiv_id":"2606.22451","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"An elementary closed-form witness test (M_T = R_T^{-1}(R_K^T)^{-1} ≥ 0) certifies exact NMF on small random instances, but the abstract's promised completeness theorem and findability phase transition are not in the body.","lead":"The body of this preprint develops a cone-ray 'witness' test that finds exact nonnegative matrix factorizations of tiny random matrices in microseconds (99/95/75 successes at r=4/5/6, m=n=10). The arXiv abstract instead advertises theorems about a findability phase transition, provable solver dominance, and 8-160x speedups that do not appear anywhere in the full text.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract's completeness theorem (every size-r NMF has a uniform-support witness) is absent from the body and contradicted by Remark 3.2; the phase-transition and 'structural ceiling' claims rest on this unproven premise.","rationale":"The reader's weakest assumption—that exact NMF instances are representable in the restricted uniform-support form the solver searches—is exactly the load-bearing gap. I agree with the reader's assessment. The body's mathematics (Prop 3.1) is internally correct, and the Monte Carlo is carefully seeded and internally consistent; the hybrid's empirical gains (+20/+10/+17) are plausible. However, the manuscript's abstract promises a completeness theorem that the full text never states or proves. This is not a minor omission: the phase-transition narrative ('by completeness a ray-economical witness always exists and persists past the threshold') and the claim that residual failures are 'structural, not budget-limited' both depend on the premise that every exact NMF admits an r-subset witness. The body's own Remark 3.2 explicitly concedes the uniform-support restriction is restrictive, and for r≥3 with m>r a polyhedral cone can have more than r extreme rays, so an NMF whose W-columns fall in different simplicial subcones cannot be captured by any single r-subset T. The saturation tables only explore the top-400 ranking, not the full candidate space, so 'structural' is an inference. A single exhaustive-search counterexample—using an instance the authors themselves generated as an exact NMF—would settle the completeness question for that instance. If such a counterexample exists, the abstract's central claim is false and the paper's advertised contribution (a certifying microsecond test for exact NMF) applies only to a restricted subclass. The 'one-sided relaxation provably dominates' and 'budget law' claims in the abstract are also absent, compounding the mismatch. I therefore maintain the REJECT verdict: the body is a useful empirical study, but the paper as submitted overclaims a universality result it does not prove and that its own remark suggests is false.","tokens_in":11424,"tokens_out":15028,"duration_ms":131552,"concrete_test":"Pick one or more of the r=4, m=n=10 Monte Carlo seeds that failed in Table 5.2 (e.g., the first failing seed from the released JSON). Run the released svd_obtuse toolkit with maxTries enlarged to the full binomial count C(k1,r)×C(k2,r) (or, if k_i > 50, uniformly sample ≥10^6 subset pairs per side) to test M_T ≥ 0 for every reachable (T,K). Since these instances are exact NMFs by construction (A=WH^T), a single instance with no feasible M_T over the exhaustive set would directly refute the abstract's completeness theorem and validate the 'structural' reading for that seed; a feasible pair beyond rank 400 would instead show the failures are budget-limited and that the saturation-curve interpretation is wrong.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Proposition 3.1 is correct as a special-case collapse, but the paper's central claim—stated in the abstract as a 'single-coupling completeness theorem shows every size-r NMF is representable this way, for every m'—does not appear anywhere in the body. No theorem statement, proof, or even a precise definition of 'this way' is given. More importantly, the body itself concedes the opposite: Remark 3.2 states that uniform support 'forces all r atoms in W to live in a single r-face' of cone(Aorth). That is a genuine restriction: for r≥3 and m>r, the preimage cone can have more than r extreme rays, and an exact NMF whose W-columns lie in distinct simplicial subcones cannot be represented with one common r-subset T on the Q side. The empirical saturation curves (Tables 5.2, 6.1) only show that the obtuseness-ranked walk at top-200/top-400 finds no feasible M_T; they do not enumerate all r-subsets, so the label 'structural, not budget-limited' is an inference, not a proof. Without the completeness theorem, there is no reason to believe that a ray-economical witness 'always exists and persists past the threshold'; the findability phase transition becomes merely a property of the heuristic, not of NMF instances. The hybrid's alt-LP fallback (Section 7) mitigates this by relaxing to r×(r+2) supports, but it is an approximate slack-LP solve (residual <1e-10), not a certificate, and it does not rescue the completeness claim for the r-subset form.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a cone-ray pipeline for exact nonnegative matrix factorization (NMF) of small exact-rank matrices. After a truncated SVD and an extreme-ray enumeration of the preimage cone via cddlib, it restricts the two factor matrices to common r-subsets of cone rays and shows, in Proposition 3.1, that feasibility then reduces to componentwise nonnegativity of a single r×r witness matrix M_T. It ranks r-subsets by an obtuseness score, searches the top of the ranking, and reports Monte Carlo saturation curves at m=n=10 and m=n=15. When M_T is infeasible, the paper augments both supports by k=2 rays and solves a slack-LP alternation, raising the m=n=10 success counts from 79/85/58 to 99/95/75 at r=4,5,6. The abstract further claims a completeness theorem for the uniform-support representation, a sharp findability phase transition, and an analysis in terms of statistical dimension and intrinsic volumes.","tokens_in":11707,"tokens_out":8170,"duration_ms":86767,"significance":"If the advertised completeness theorem and phase-transition results were established, the paper would be significant: a one-inverse test for exact size-r NMF under a uniform-support restriction, plus a deterministic certifying solver, would be a useful contribution to the small-scale exact NMF literature. The paper also has genuine strengths: Proposition 3.1 is mathematically correct and gives a cheap sufficient certificate; the experiments are seeded, the residual values are reported transparently, and the executable toolkit and per-trial JSON results are released. However, the central theoretical claims in the abstract are not present in the body, and the body itself contains statements that contradict them. As it stands, the paper is an empirical study of a restricted heuristic, not the claimed exact-NMF completeness/findability theory.","major_comments":[{"comment":"The abstract promises a 'single-coupling completeness theorem' showing 'every size-r NMF is representable this way, for every m' and a 'one-sided relaxation' that 'provably dominates' the two-sided witness. No such theorem, proof, or even precise statement appears in the body. Remark 3.2 admits the opposite: uniform support 'forces all r atoms in W to live in a single r-face' of cone(Aorth). For r≥3, a cone can have more than r extreme rays, and Carathéodory gives per-column supports, not a common r-subset across all columns. Because the later findability claims rely on the existence of a ray-economical witness, this absence is load-bearing, not a presentation issue.","section":"Abstract; §1; §3, Remark 3.2"},{"comment":"The claim that residual failures are 'structural, not budget-limited' is an inference, not a proof. Tables 5.2 and 6.1 compare only three budgets (top-5, top-200, top-400). Moreover, Algorithm 1 explicitly samples 5,000 subsets when the pool exceeds 5,000, so 'top-200' and 'top-400' refer to a sampled pool, not to an exhaustive ranking of all r-subsets. The median best obtuseness on failed trials does not establish nonexistence of a feasible M_T. The later success of the alt-LP path at earlier-ranked pairs (Table 7.1) shows that failure of one restricted branch does not imply structural infeasibility.","section":"§5.2, §6.1; Algorithm 1"},{"comment":"The abstract's 'findability phase transition' claims—width collapsing to a step, flat statistical dimension, intrinsic-volume variance tracking, and a single budget law—are not supported by anything in the body. There is no section on statistical dimension or intrinsic volumes, no transition-curve fit, no threshold estimate, and no width computation. The data consist of success counts at two or three budgets for a handful of (m,n,r) combinations. This is a saturation curve for a heuristic, not a phase transition for NMF instances.","section":"Abstract; §5.2; §6.1"},{"comment":"The alt-LP fallback is not an exact certificate in the sense promised by the abstract and introduction. Algorithm 2 accepts a solution when the final residual is below 10^-10, and Section 7.4 reports reconstruction errors as large as 4×10^-13 and 1.2×10^-11 on successful trials. The 'machine-exact, certifier' language is therefore overstated for the alt-LP path. A rigorous post-processing step or a rounded-exactness argument is needed before the output can be called a certificate.","section":"§7, Algorithm 2, §7.4"}],"minor_comments":[{"comment":"The proof of Proposition 3.1 only treats the direction ν=I_r. The statement 'iff' is correct, but the proof should explicitly argue necessity: any feasible μ,ν gives μν^T = R_T^{-1}(R_K^T)^{-1}, so M_T ≥0 is necessary as well as sufficient.","section":"§3, Proposition 3.1"},{"comment":"Section 8 is titled 'Computational Cost Summary' but contains no text; Table 8.1 appears after Section 9. The section numbering and placement should be fixed.","section":"§8"},{"comment":"Several abstract phrases—'single-coupling completeness', 'one-sided relaxation', 'provably dominates', 'budget law'—do not appear in the body or in the list of contributions in Section 1. The abstract should be aligned with the actual content.","section":"Abstract vs. body"},{"comment":"The breakdown '32 Mt-path + 67 alt-LP-path' is presented as evidence of alt-LP 'stealing' wins, but the same table shows the Mt-only top-200 count is 79; the decrease to 32 is a consequence of the hybrid returning earlier alt-LP successes. This should be stated more carefully so readers do not infer a discrepancy in the underlying datasets.","section":"§7.4, Table 7.1"}],"recommendation":"reject","confidential_remarks":"The paper has a useful special-case collapse (Proposition 3.1) and a reproducible empirical algorithm, but the advertised completeness theorem and phase-transition analysis are absent, and at least one body statement (Remark 3.2) directly contradicts the abstract. These are not minor gaps; they are the paper's central claims. If the authors later resubmit a scaled-down version that either proves the completeness theorem or clearly reframes the work as a heuristic empirical study with no existence/findability overreach, I would be willing to reconsider."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: read the body, not the abstract. The body is a small, honest empirical study of a genuinely new prefilter for exact NMF, with reproducible code and documented scaling walls. The abstract sells a theory the body does not contain.\n\nWhat is actually new and good: Proposition 3.1 is correct as far as it goes — under uniform support, the joint constraint forces the witness matrix M_T = R_T^{-1}(R_K^T)^{-1}, and componentwise nonnegativity is necessary as well as sufficient, though the proof only writes the sufficient direction. The obtuseness ranking over cone-ray subsets is a sensible heuristic, and the saturation experiments (top-5, top-200, top-400) plus the hybrid alt-LP fallback tell a coherent story. The Monte Carlo is seeded, the breakdowns sum correctly, and the m=n=15 collapses and Olivetti DDM timeout are reported rather than hidden. The alt-LP hybrid lifting success from 79/85/58 to 99/95/75 is a defensible measurement, modulo the missing confidence intervals and the 1e-10 tolerance caveat.\n\nThe soft spots are real and structural. The abstract's completeness theorem — that every size-r NMF has a uniform-support witness — appears nowhere in the body. No statement, no proof, not even a precise definition of \"this way.\" And the body's own Remark 3.2 concedes the opposite: uniform support forces all r atoms of W to lie in a single r-face. This is not implied by Caratheodory, which bounds per-column supports without forcing one common r-subset. So the paper's headline findability phase transition is not an established property of NMF instances; it is a property of this heuristic on the tested distributions. Likewise, the \"structural, not budget-limited\" label is an inference from saturation curves, not a proof: the paper does not enumerate all r-subsets, so it cannot rule out better rankings finding a witness deeper in the list.\n\nThe abstract also promises a budget law, a provably dominant one-sided solver, six-distribution benchmarks, and 8-160x speedups. None of those appear in the body. That is not a minor omission; it is the abstract describing a different paper than the one submitted.\n\nWho is this for? Someone working on exact or separable NMF heuristics will find the witness prefilter and the alt-LP augmentation worth knowing, and the released toolkit is a plus. But the paper needs major revision before it is publishable: either the completeness theorem must be proved or removed, the phase-transition language must be downgraded to an empirical heuristic, and the structural-ceiling claims need qualification. The reader's REJECT is fair if the abstract is taken at face value; a serious referee could help the author separate the genuine empirical contribution from the unsupported theory.\n\nI would send this to peer review, but with a clear request to fix the mismatch between claims and evidence.","headline":"Honest empirical body, overreaching abstract: the uniform-support witness is a real but elementary contribution, while the completeness theorem and phase transition are promised but never derived.","tokens_in":12362,"tokens_out":1594,"would_cite":false,"duration_ms":18899,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["15A23","15A48","90C05","90C26","52B55"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact nonnegative matrix factorization on small matrices can be certified by checking the nonnegativity of a single witness matrix per candidate support pair.","keywords":["nonnegative matrix factorization","exact NMF","polyhedral cone","cone rays","witness matrix","obtuseness ranking","alternating linear program","certificate"],"falsifier":"Find a single random 10×10 rank-4 nonnegative matrix for which an exact NMF is known to exist (e.g., constructed by a known factorization) but the hybrid algorithm with top-200 walk and k=2 augmentation returns 'no feasible'. Alternatively, for any failed trial, exhaustively check all (T,K) pairs for M_T ≥ 0; a single such pair would contradict the claim that failures are structural rather than budget-limited.","tokens_in":11095,"feed_emoji":"✅","tokens_out":6797,"duration_ms":56361,"temperature":0.7,"pith_summary":"The paper studies exact nonnegative matrix factorization (NMF) on small exact-rank-r matrices. It shows that if the two factor matrices are restricted to each draw their columns from a fixed set of r cone rays (one set per factor), the entire factorization condition collapses to a single r×r matrix whose entrywise nonnegativity certifies an exact factorization. The paper then ranks candidate ray-subsets by a geometric near-orthogonality score ('obtuseness') and walks the top of the ranking; when the closed-form witness fails, it augments the support by two extra rays and runs a short alternating linear program. On 100-trial random 10×10 instances this hybrid recovers 99, 95, and 75 of 100 exact factorizations for r=4,5,6, up from 79,85,58 with the witness alone. The residual failures are argued to be structural — the cones lack a near-orthogonal r-subset — rather than a matter of search budget.","feed_headline":"One matrix inverse certifies exact NMF","feed_subtitle":"A cone-ray witness plus obtuseness search recovers 99/95/75 of random 10×10 instances at r=4,5,6.","key_machinery":"The central object is the witness matrix M_T = R_T^{-1}(R_K^T)^{-1}, where R_T and R_K are the r×r sub-matrices of extreme-ray matrices of the nonnegative-preimage cones, indexed by r-subsets T and K. The supporting machinery is the obtuseness score, |det(R_T)|/∏‖R_T[:,i]‖, which measures how near-orthogonal a ray subset is and drives the order in which candidates are tested; and the augmented-support alternating linear program, which solves for nonnegative coefficients on r×(r+2) supports when the closed-form witness is infeasible. The one-line mechanism: feasibility of the factorization is decided by componentwise nonnegativity of a single matrix inverse.","core_discovery":"The central claim, stated on its own terms: for an exact-rank-r nonnegative matrix A, write A = A_orth Q = A_orth1 P with QP^T = I_r. Restricting each column of Q (resp. P) to be a nonnegative combination of r fixed extreme rays of the associated polyhedral cone, the joint constraint reduces to the single matrix equation R_T μ ν^T R_K^T = I_r. With ν = I_r, this forces μ = M_T = R_T^{-1}(R_K^T)^{-1}, and the pair (T,K) is feasible exactly when M_T ≥ 0 entrywise. The paper's finding is that on small random instances this witness is recoverable by an obtuseness-ranked search most of the time, and that an augmented r×(r+2) support with an alternating slack LP rescues nearly all remaining cases.","pith_inferences":["The abstract promises a completeness theorem (every size-r NMF is representable in this form) and a findability phase transition; the body does not supply either. If the completeness theorem were proven, it would imply that the difficulty of exact NMF shifts from existence to the combinatorial search for a ray-economical support — the paper's empirical saturation curve is consistent with that lens","The reported failure of the exact double-description step on a 400×4096 face dataset suggests that the method's practical ceiling is the enumeration of cone rays, not the witness test; replacing exact ray enumeration by sampling could be a testable extension.","The 'structural failure' claim — that no near-orthogonal r-subset exists on at least one side — is testable independently: one can check, for a failed instance, whether any (T,K) pair has M_T ≥ 0, and whether the best-obtuseness score correlates with existence. If failures are found that do have a feasible pair, the structural ceiling claim would be weakened."],"forward_implications":["If correct, exact NMF on small instances (e.g., 10×10, r≤6) can be certified deterministically in microseconds per candidate pair, returning a machine-precision factorization rather than an approximation.","The success rates 99/95/75 at r=4,5,6 on random nonnegative inputs show that the structural ceiling of the closed-form witness can be broken by a modest augmentation (k=2), motivating deeper augmentation for harder regimes.","The saturation at top-200 implies that additional search budget does not help beyond a point; improving recovery requires lifting the uniform-support restriction rather than enumerating more subsets.","The method provides a certificate of exactness (reconstruction error at machine precision) whenever it succeeds, which alternating least squares and multiplicative updates do not."],"fun_headline_variants":["Exact NMF: one inverse, one witness","Cone-ray witness certifies exact NMF","Findability phase transition in exact NMF","NMF always exists; only findability transitions"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is that every exact NMF of a tested instance can be written with all r columns of each factor supported on a single fixed r-subset of cone rays (or rescued by adding two rays per side); if an exact factorization exists only with supports spread across more rays, the witness will not be found and the search will report 'no feasible'.","fun_headline_variants_meta":{"raw":{"variants":["Exact NMF: one inverse, one witness","Cone-ray witness certifies exact NMF","Findability phase transition in exact NMF","NMF always exists; only findability transitions"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000449,"raw_usage":{"total_tokens":2203,"prompt_tokens":946,"completion_tokens":1257,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":690,"completion_tokens_details":{"reasoning_tokens":1198}},"tokens_in":690,"tokens_out":1257,"duration_ms":10590,"temperature":1.0,"reasoning_tokens":1198,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T10:35:06.274918+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a single random 10×10 rank-4 nonnegative matrix for which an exact NMF is known to exist (e.g., constructed by a known factorization) but the hybrid algorithm with top-200 walk and k=2 augmentation returns 'no feasible'. Alternatively, for any failed trial, exhaustively check all (T,K) pairs for M_T ≥ 0; a single such pair would contradict the claim that failures are structural rather than budget-limited.","supporting_citations":[],"review_version":2}