GAP-Aware Exact Nonnegative Matrix Factorization: A Two-Sided SVD Gauge and a Three-Regime W-Rank Taxonomy

Q: What problem does the paper address in exact NMF?

It studies exact nonnegative matrix factorization in the gap regime r+ > r, extending a cone-ray pipeline beyond the uniform-support case where r+ = r.

Jul 16, 2026

Upload by Eliana

Gap-aware exact nonnegative matrix factorization extends the cone-ray exact-NMF pipeline from the uniform-support setting r+ = r to the gap regime r+ > r. A three-regime taxonomy classifies recoverable nonnegative factorizations by the rank of the W factor. Regime A attains full recovery on dense random gap matrices via a two-sided SVD-gauge formulation. Regime B adds a rank-deficient W column-subset branch. Regime C remains unsolved for non-column-subset W with intermediate rank gaps.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Abstract

Introduction

Uniform-support regime r+ = r

Gap regime r+ > r and SVD gauge

Key words

arXiv :2606 .25715v1 [math .NA] 24 Jun 2026 GAP-AWARE EXACT NONNEGATIVE MATRIX FACTORIZATION: A TWO-SIDED SVD GAUGE AND A THREE-REGIME W-RANK TAXONOMY ∗ MITHIL RAMTEKE† Abstract. We extend the cone-ray exact-NMF pipeline of [1] from the uniform-support regime r+ = r to the gap regime r+ > r and classify the recoverable nonnegative factorisations by the rank of the W-factor into a three-regime taxonomy. Regime A: rank (W) = r+ (full column rank) . Solved by the two-sided SVD-gauge cone-ray pipeline W = Ur + (G) Q, H = P Vr + (K)⊤ with G ∈ St (m−r, r+−r), K ∈ St (n−r, r+−r) and square consistency QP = diag (Sr , 0) ∈ Rr +×r + . On 10 × 10 dense random gap matrices the pipeline achieves 100/100 recovery at r+ = 5 and r+ = 6, beating the 79–87/100 saturation curve of the companion paper’s r+ = r case. The improvement rests on two geometric facts for dense M: slack enclosure (the data cone has codimension r+ − r in the outer cone, so r+-subset selection has generous slack), and NRF-variety thickness (the valid-NRF family covers a positive-measure subset of Gr(r+, m) × Gr(r+, n), so the blind SVD lands at a feasible (G, K) pair with probability one) . Regime B: rank (W) = r and W is a column subset of M. Solved by a rank-deficient W branch that enumerates r+-subsets of M’s columns and tests WH = M column-by-column by LP feasibility. On the block-diagonal family diag (C, Jk) (where C is a certified rank-4 / r+ = 6 circulant), additivity of nonneg rank collapses the valid-NRF variety to a single point, Regime A fails (0/3 at k ∈ {2 , 3 , 4}, and uniform Stiefel restarts, finite-difference Stiefel-GD, Pymanopt SteepestDescent / ConjugateGradient / multi-start, and derivative-free FindMinimum all stall in piecewise-constant cell plateaus) . Regime B’s column-subset branch then restores 4/4 on the same family in milliseconds. Regime C: r < rank (W) < r+, and W is not a column subset of M. Exposed by the regular octagon’sslack matrix S (rank 3, xc ≤ 6 by [8]) . An exact size-6 NRF exists (sklearn NMF finds it at relErr ≤ 10 −13) and is reachable by the symmetric formulation W = Ur + (G)Q, H = P Vr + (K)⊤ with both G ∈ St (m−r, r+−r) and K ∈ St (n−r, r+−r) and the square consistency QP = diag (Sr , 0) ∈ Rr +×r + . The square consistency QP = diag (Sr , 0) imposes no rank ceiling on Q or P individually, so rank (W) and rank (H) can independently range over {r, . . . , r+} . As an oracle feasibility certificate for the formulation, at (G∗ , K∗ ) derived from a known (W∗ , H∗ ) and warm-started by a µwarm that reproduces W∗ , the symmetric alt-LP converges to alt-LP residual 1 .5 × 10 −10 in 11 iterations with ∥S −WH∥F /∥S∥F = 1 .6 × 10 −11 . The blind problem, however, is unsolved: 50 Haar-uniform random restarts (G, K) ∈ St(5 , 3) × St(5 , 3) with default µinit = [I; 0] never approach feasibility (best residual 1.85, ≈ 20% of ∥S∥F ), and a Riemannian gradient descent on the joint manifold via Pymanopt with a random nonneg µ-init does no better (best loss 3 .29 after 5 outer restarts; the optimiser stalls in ≤ 2 steps every time) . The loss is piecewise constant on cells of (G, K)-space (the obtuse-cone rays returned by lcdd are invariant within each cell and jump discretely at cell boundaries), so local descent cannot cross cell walls. A smoother surrogate or a basin-hopping restart scheme is required; we leave both open. A combined toolkit running Regime B then Regime A covers matrices in those two regimes with no regression on dense draws (99/100 via Regime A plus 1/100 via Regime B in a 100-trial sanity check) . Regime C remains open, with the regular octagon as the cleanest unsolved test case. Key words. nonnegative matrix factorization, exact factorization, nonnegative rank gap, polyhedral cones, double description method, Stiefel manifold, Grassmannian, two-sided SVD gauge, slack matrix, extension complexity AMS subject classifications. 15A23, 15A48, 90C05, 90C26, 52B55 1. Introduction. The companion paper [1] de

FAQs

What problem does the paper address in exact NMF?

It studies exact nonnegative matrix factorization in the gap regime r+ > r, extending a cone-ray pipeline beyond the uniform-support case where r+ = r.

How does the paper classify factorizations in the three regimes?

It classifies recoverable nonnegative factorizations by the rank of the W factor, using cases where rank(W)=r+, rank(W)=r with W as a column subset of M, and intermediate rank where W is not a column subset.

Why is Regime C left unsolved, and what obstruction is observed?

Local optimization over the two-sided SVD gauge variables stalls because the loss is piecewise constant over cells of (G,K)-space, preventing descent from crossing cell boundaries; the blind SVD and tested Riemannian methods fail to reach feasibility.

Jul 16, 2026

Upload by Eliana