{"id":"af75b8eb-9979-4510-97b5-c6c34a10af9f","arxiv_id":"2606.25715","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":3,"one_line_summary":"A two-sided SVD-gauge cone-ray pipeline plus a column-subset LP branch recovers exact NMF for regimes A and B in the gap setting; regime C (intermediate W-rank) stays open, with the regular octagon as the clean test case.","lead":"This paper extends exact nonnegative matrix factorization to the gap regime where nonnegative rank exceeds ordinary rank, using a two-sided SVD gauge and a three-regime taxonomy by W-rank. A combined toolkit recovers exact factorizations for full-rank and column-subset cases, while intermediate-rank cases remain open.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"The NRF-variety thickness argument for almost-sure blind-SVD success on dense generators is informal and does not rigorously establish that the SVD gauge map hits the positive-measure set.","rationale":"The reader's weakest_assumption correctly isolates the softest link in the strongest claim. Empirical recovery rates, released code, the geometric slack-enclosure intuition, the sharp block-diagonal counter-example that collapses the variety to a point, and the honest open status of Regime C are all solid; the three-regime taxonomy is a useful organising device. No deeper inconsistency, algorithmic error, or experimental artefact is visible. The CONDITIONAL verdict (accept the A/B toolkit once the probability-one statement is either proved or clearly labelled empirical) therefore stands; the present concern is essentially identical, so no verdict adjustment is warranted.","tokens_in":17884,"tokens_out":570,"duration_ms":23016,"concrete_test":"Draw 1000 independent matrices from the identical dense generator (m=n=10,r=4,r+=5), form the SVD-induced Ur+(G) exactly as in Algorithm 1 lines 1–2, and run only the closed-form witness phase; record the fraction of successes. If any trial fails, the probability-one claim is false for this generator. (Alternatively, exhibit a positive-measure set of generator parameters on which the SVD gauge is invalid.)","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central Regime-A claim (100/100 recovery on the Unif[0,1] generator at r+=5,6 via closed-form witness alone) is explained in Section 4 by slack enclosure plus NRF-variety thickness: a strictly-positive generator pair (W*,H1 H2) can be perturbed while remaining nonnegative and product-preserving, so the induced map to Gr(r+,m)\times Gr(r+,n) has positive-dimensional image and the valid-gauge set therefore has positive measure; hence 'the blind SVD lands \to with probability one.' This shows openness/positive measure of the valid set, but does not prove that the concrete (almost-everywhere continuous) map sending a random generator triple to the SVD-induced gauge (Ur,U\top, then any orthonormal completion of the null-space block) lands inside that set almost surely. The SVD gauge could a priori concentrate on a null set even if the ambient valid set is thick. The 100-trial Monte-Carlo is strong empirical corroboration, yet finite; the companion r+=r saturation was only 79–87/100, so the gap helps, but the probability-one language overstates the formal support.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper extends the author's cone-ray exact-NMF pipeline from the uniform-support case r+=r to the gap regime r+>r via a two-sided SVD gauge W=U_{r+}(G)Q, H=P V_{r+}(K)^T with square consistency QP=diag(S_r,0). It organises recoverable factorisations into a three-regime taxonomy by rank(W): Regime A (rank(W)=r+) solved by the blind SVD-gauge cone-ray pipeline; Regime B (rank(W)=r and W a column subset of M) solved by enumerating r+-column subsets with per-column LP tests; Regime C (intermediate rank(W), W not a column subset) left open. Empirically, the pipeline recovers 100/100 exact factorisations on 10×10 dense random rank-4 matrices at r+=5 and 6 (closed-form witness only); the rank-deficient branch restores recovery on the block-diagonal family diag(C,J_k) where additivity collapses the valid-gauge set to a point and blind SVD fails; the regular octagon's slack matrix is shown to admit an exact size-6 NRF reachable at an oracle gauge but not by blind Haar restarts or Riemannian GD, because the alt-LP residual is piecewise constant on cells of gauge space. A combined B-then-A toolkit covers A and B with no regression on dense draws.","tokens_in":18251,"tokens_out":1775,"duration_ms":24536,"significance":"If the empirical claims hold, the work is a useful and carefully scoped algorithmic extension of exact NMF into the gap regime, with a clean geometric diagnosis of when blind SVD succeeds (dense generators) versus fails (block-diagonal additivity). Strengths include: fully reproducible code release; concrete Monte-Carlo tables (100/100 dense recovery; 0/50 Stiefel restarts on M_k; 4/4 rank-def recovery in milliseconds; oracle alt-LP residual 1.5e-10 vs blind ~1.85 on the octagon); honest separation of oracle feasibility from the unsolved blind Regime-C problem; and standard external foundations (Cohen–Rothblum additivity, FRT extension complexity, cddlib). The three-regime taxonomy and the slack-enclosure intuition are clarifying even if Regime C remains open. The contribution is incremental relative to the companion paper but addresses the practically more interesting r+>r setting and documents a genuine structural obstruction rather than papering over it.","major_comments":[{"comment":"Section 4 ('The thickness of the valid-NRF variety') and the abstract claim that valid gauges form a positive-measure set 'so the blind SVD lands on one with probability one.' The interior-perturbation argument correctly suggests that the valid-gauge set is open/positive-measure in the product Grassmannian for strictly positive generators, but positive measure alone does not imply that the concrete map from a random generator triple (W*,H1,H2) through the SVD (and any orthonormal null-space completion) hits that set almost surely. The SVD-induced gauge could a priori concentrate on a null set. The 100/100 Monte-Carlo is strong empirical support, yet the probability-one language overstates the formal argument. Soften to 'generically / with high empirical frequency' or supply a measure-theoretic argument that the SVD gauge is absolutely continuous w.r.t. Haar measure on the relevant Grassm","section":"Section 4, NRF-variety thickness"},{"comment":"The central Regime-A success (Table 4.1: 100/100 at r+=5,6 by closed-form witness alone) is demonstrated only for the specific dense generator M=W*(H1 H2) with Unif[0,1] entries on 10×10 rank-4 matrices. The geometric explanation (slack enclosure + thickness) is tied to strictly positive factors. The manuscript should either (i) state clearly that Regime-A guarantees are claimed only for this generator class, or (ii) add at least one additional dense family (e.g. exponential or truncated-Gaussian entries, or mild sparsity) to test whether 100/100 is generator-specific. Without that, the abstract's unqualified 'on 10×10 dense random gap matrices' risks over-generalisation from a single generative model.","section":"Section 4, Table 4.1"},{"comment":"Proposition 6.1 and the Mk analysis correctly use Cohen–Rothblum additivity to show the valid-gauge set is a single point (measure zero), explaining 0/50 Stiefel restarts. However, the paper's claim that the combined toolkit 'covers regimes A and B' (abstract, Section 8) treats Regime B as 'rank(W)=r and W a column subset of M.' Section 9 and the limitations note that intermediate-rank NRFs that are not column subsets (Regime C, and potentially other structured matrices) are missed by both branches. The coverage claim should be restated more precisely: the toolkit covers (i) full-column-rank NRFs when the blind gauge is feasible and (ii) column-subset NRFs of rank r; it does not cover all matrices that admit some size-r+ NRF with rank(W)≤r. This is already implicit in the octagon discussion but should be explicit in the abstract and Algorithm 3 claims.","section":"Abstract; Section 8; Section 9.4"}],"minor_comments":[{"comment":"Notation: the abstract and title use r_+ and W-rank; the body mixes r+, r_+, and r +. Pick one and use it consistently, including in algorithms and tables.","section":"Throughout"},{"comment":"Algorithm 1 line 7 writes H ← R_T^{-1} diag(S_r,0) V_{r+}^T; the subsequent paragraph correctly notes independence of K. A one-line remark inside the algorithm box ('H independent of K in closed-form phase') would prevent readers from missing this.","section":"Section 3, Algorithm 1"},{"comment":"Table 5.1 column 'Gr' is dimension of the Grassmannian of gauge choices; spell this out in the caption (currently easy to misread as a status flag).","section":"Table 5.1"},{"comment":"Section 9.3: the sklearn NMF recovery of an exact octagon factorisation is important; report the random seed / init index or release the (W*,H*) pair in the repository so the oracle-gauge experiment is bit-reproducible without re-running 500 NMF trials.","section":"Section 9.2–9.3"},{"comment":"Related work cites the companion [1] and standard NMF/extension-complexity sources; a brief pointer to recent exact-NMF / nonnegative-rank computational work beyond Arora–Ge–Kannan–Moitra and Vavasis would help place the cone-ray approach relative to other exact solvers.","section":"Section 11"},{"comment":"Typos / style: 'three-regimeW-rank' missing space in title block; 'ok subset' / 'ok altlp' status strings are fine in code but read better as 'ok_subset' or quoted in prose; 'FindMinimum' should be identified as Wolfram Language.","section":"Title; Sections 6–7"}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is tightly coupled to the author's companion arXiv:2606.22451; novelty is real but incremental. Fit for a computational linear-algebra / numerical-analysis venue is reasonable if the probability-one language is toned down and coverage claims are sharpened. Code release is a genuine plus. I do not see load-bearing mathematical errors—only overstatement of the measure argument and slightly broad wording of coverage—which is why I recommend minor rather than major revision."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is a clean methods extension of the author's own uniform-support cone-ray pipeline to r+ > r. The new pieces that matter are the two-sided Stiefel gauge with square consistency QP = diag(Sr, 0), the rank-deficient-W column-subset branch, the three-regime taxonomy by rank(W), and the honest diagnosis that the regular octagon sits in Regime C and is still open for blind search.\n\nWhat works: on dense 10x10 rank-4 generators the closed-form witness alone hits 100/100 at r+=5 and 6 (median relErr ~1e-15), better than the companion's r+=r saturation. On the block-diagonal family diag(C, Jk) where additivity collapses the valid gauge to a point, Regime A fails and the column-subset branch restores 4/4 in milliseconds. The combined orchestrator (B then A) shows no regression. The octagon section is the best part: sklearn finds an exact size-6 NRF, the symmetric formulation recovers it from an oracle gauge (residual 1.5e-10), yet 50 Haar restarts and Riemannian GD on Stiefel/Grassmann all stall because the alt-LP residual is piecewise constant on combinatorial cells. That diagnosis is sharp and useful. Code is released.\n\nSoft spots are real but limited. The NRF-variety thickness argument shows the valid-gauge set is open/positive-measure under interior perturbation of a strictly positive generator; it does not rigorously prove that the concrete SVD-induced gauge map hits that set almost surely. The 100-trial Monte-Carlo is strong corroboration, not a theorem, so the 'probability one' phrasing should be dialed back to empirical. Subset enumeration is combinatorial and will not scale; the paper already flags this. Regime C is left open, which is fine.\n\nCitations are standard (Cohen–Rothblum, Fiorini–Rothvoss–Tiwary, cddlib, Absil et al.). This is for people who care about exact NMF, nonnegative rank, and extension complexity of small polytopes. It is not a complexity breakthrough, but it is reproducible and clarifying. I would send it to referees; they will ask for the probability language to be tightened and for clearer scaling caveats, not for a rewrite of the core claims.","headline":"Solid, honest extension of the author's cone-ray NMF pipeline to the gap regime, with a useful three-regime taxonomy and a clean open benchmark; the dense 'probability one' language is a bit strong but the experiments and code are real.","tokens_in":18892,"tokens_out":601,"would_cite":true,"duration_ms":5869,"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":"grok-4.5","headline":"Exact NMF in the gap regime splits into three W-rank cases; a two-sided SVD gauge plus a column-subset branch recovers the first two, while intermediate-rank factorizations stay open.","keywords":["nonnegative matrix factorization","exact factorization","nonnegative rank gap","polyhedral cones","double description method","Stiefel manifold","two-sided SVD gauge","extension complexity"],"falsifier":"Generate a new batch of 10\times10 dense Unif[0,1] gap matrices at r=4, r+=5 or 6; if the closed-form witness phase of the two-sided pipeline fails on a non-negligible fraction of trials, the thickness claim is false for that generator.","tokens_in":18740,"feed_emoji":"📐","tokens_out":1222,"duration_ms":9400,"temperature":0.7,"pith_summary":"Exact nonnegative matrix factorization asks for nonnegative factors W and H whose product equals a given nonnegative matrix M and whose inner dimension equals the nonnegative rank. When that nonnegative rank is strictly larger than the ordinary rank (the gap regime), the earlier cone-ray pipeline no longer applies directly. This paper lifts the pipeline by introducing a two-sided SVD gauge: orthonormal frames that extend the ordinary singular subspaces by free directions chosen on Stiefel manifolds, together with a square consistency condition that replaces the old identity constraint. On dense random matrices the blind choice of gauge succeeds in every trial, because the data cone sits with positive codimension inside a larger outer cone (slack enclosure) and because the set of valid gauges itself has positive measure (NRF-variety thickness). Structured block-diagonal matrices collapse the valid gauges to a single point, so the same pipeline fails; a complementary branch that simply tests whether an r+-subset of M’s own columns already spans the remaining columns restores exact recovery in milliseconds. Between these two extremes lies a third regime, illustrated by the regular octagon’s slack matrix, in which the correct W has intermediate rank and is not a column subset; the formulation can represent such a factorization once the right gauge is supplied, yet blind search stalls because the residual is piecewise constant on combinatorial cells of gauge space. The practical result is a two-phase toolkit that covers the first two regimes without regression on dense data, while leaving the intermediate-rank case as the clean open test problem.","feed_headline":"Exact NMF with a rank gap splits into three cases","feed_subtitle":"Two-sided SVD gauge plus column subsets recover two regimes; intermediate-rank factorizations stay open","key_machinery":"The two-sided SVD gauge: W = U_{r+}(G) Q and H = P V_{r+}(K)^T with G, K on Stiefel manifolds and square consistency QP = diag(S_r, 0). It lets the cone-ray / obtuseness / alt-LP machinery run at any target r+ > r, while the rank of Q and P can independently range over {r,…,r+}, thereby covering both full-rank and intermediate-rank factorizations once a feasible gauge is known.","core_discovery":"Exact nonnegative factorizations with a rank gap fall into three regimes according to the rank of W. Regime A (full column rank r+) is solved by a two-sided SVD-gauge cone-ray pipeline that recovers 100/100 dense 10\times10 instances at gaps of 1 and 2. Regime B (rank(W)=r and W a column subset of M) is solved by exhaustive subset enumeration plus per-column LP tests, restoring recovery on the block-diagonal family where the gauge collapses to a point. Regime C (intermediate rank, non-column-subset W) is representable by the same symmetric formulation at an oracle gauge, but remains unsolved for blind search because the alternating-LP residual is piecewise constant on cells of gauge space.","pith_inferences":["Any practical exact-NMF solver that wants complete coverage must eventually replace pure local Riemannian descent with a cell-crossing or combinatorial enumeration strategy over the finite set of ray configurations.","The same three-regime taxonomy is likely to reappear for other exact cone-membership problems (e.g., exact nonnegative tensor factorization or extension-complexity certification) whenever the target inner dimension exceeds the algebraic rank.","Scaling the column-subset branch beyond n≈10 will require pruning to the extreme rays of the data cone rather than all column subsets, turning the method into a separable/vertex-NMF preprocessor."],"forward_implications":["A combined toolkit (column-subset branch first, then blind SVD-gauge) recovers exact size-r+ factorizations for every matrix that lives in Regime A or B, with no regression on dense random draws.","On block-diagonal families whose nonnegative rank is additive, the column-subset branch finds exact factorizations in milliseconds even when every continuous gauge search stalls.","The regular octagon’s slack matrix becomes the cleanest public test case for any future method that claims to solve Regime C blindly.","Slack enclosure explains why increasing the target dimension past the ordinary rank makes the obtuseness heuristic strictly more reliable than in the uniform-support case."],"fun_headline_variants":["Exact NMF rank gap splits by W-rank into three regimes","Two-sided SVD recovers full-rank gap NMF on dense 10x10 draws","Column-subset LP restores exact NMF when gauges collapse to one point","Intermediate-rank gap NMF open despite oracle-gauge recovery","Gap exact-NMF taxonomy: SVD for A, subsets for B, C unsolved"],"cache_read_input_tokens":128,"weakest_assumption_plain":"For dense strictly positive generators the set of valid two-sided gauges has positive measure in the product Grassmannian, so a blind SVD lands on a feasible gauge with probability one.","fun_headline_variants_meta":{"raw":{"variants":["Exact NMF rank gap splits by W-rank into three regimes","Two-sided SVD recovers full-rank gap NMF on dense 10x10 draws","Column-subset LP restores exact NMF when gauges collapse to one point","Intermediate-rank gap NMF open despite oracle-gauge recovery","Gap exact-NMF taxonomy: SVD for A, subsets for B, C unsolved"]},"model":"grok-4.5","effort":"low","cost_usd":0.005836,"raw_usage":{"total_tokens":1752,"prompt_tokens":1073,"num_sources_used":0,"completion_tokens":103,"cost_in_usd_ticks":58360000,"prompt_tokens_details":{"text_tokens":1073,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":576,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":1073,"tokens_out":103,"duration_ms":6628,"temperature":1.0,"reasoning_tokens":576,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T17:19:43.475963+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Generate a new batch of 10\times10 dense Unif[0,1] gap matrices at r=4, r+=5 or 6; if the closed-form witness phase of the two-sided pipeline fails on a non-negligible fraction of trials, the thickness claim is false for that generator.","supporting_citations":[],"review_version":2}