arxiv: 2605.14058 · v1 · pith:KVIQTO6Gnew · submitted 2026-05-13 · 🧮 math.OC · cs.DM

Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers

Timothy Baeckelant , Arnaud Vandaele , Nicolas Gillis This is my paper

Pith reviewed 2026-05-15 02:40 UTC · model grok-4.3

classification 🧮 math.OC cs.DM

keywords nonnegative ranklower boundsnon-convex optimizationfooling set boundrectangle covering boundself-scaled boundmatrix factorization

0 comments p. Extension

Add this Pith Number to your LaTeX paper

What is a Pith Number?

\usepackage{pith}
\pithnumber{KVIQTO6G}

Prints a linked pith:KVIQTO6G badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more

The pith

Non-convex optimization solvers compute four classical lower bounds on the nonnegative rank of matrices, including the first method for the self-scaled bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops non-convex formulations for computing lower bounds on the nonnegative rank, specifically the fooling set bound, rectangle covering bound, hyperplane separation bound, and self-scaled bound. These allow practical computation using standard solvers, with the self-scaled bound method being new to the literature. For several matrices, the improved lower bounds match known upper bounds, fixing their exact nonnegative rank for the first time. On standard benchmarks, the approaches often compete with existing methods while providing a unified reference for the bounds.

Core claim

By reformulating the lower bound computations as non-convex optimization problems, the authors obtain the first practical algorithm for the self-scaled bound on nonnegative rank, which yields strictly better lower bounds than previous methods for some matrices and establishes exact values when matching upper bounds.

What carries the argument

Non-convex optimization problems formulated to compute the fooling set bound, rectangle covering bound, hyperplane separation bound, and self-scaled bound on the nonnegative rank.

If this is right

Some matrices now have their nonnegative rank exactly determined for the first time.
The self-scaled bound becomes computable for the first time.
Lower bounds improve on canonical benchmark matrices.
Non-convex methods serve as a competitive alternative to standard bound computations.
The paper consolidates data on lower bounds for many matrices.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

These techniques may extend to computing other hard rank measures in nonnegative matrix factorization.
Improved bounds could help in applications like topic modeling or image processing where exact rank matters.
Success with non-convex solvers suggests similar approaches for other NP-hard combinatorial bounds.

Load-bearing premise

The non-convex solvers must find solutions that are accurate enough to serve as valid lower bounds rather than getting trapped in suboptimal points.

What would settle it

A matrix for which the computed self-scaled bound exceeds a known upper bound on the nonnegative rank.

Figures

Figures reproduced from arXiv: 2605.14058 by Arnaud Vandaele, Nicolas Gillis, Timothy Baeckelant.

**Figure 2.** Figure 2: Illustration of the RCB computation using ( [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Figure 3: Illustration of the inequalities (10) on M5. The solid curve shows the value ⟨L, X/∥X∥∞⟩ of the restricted master problem, while the dashed curve shows the corresponding current implied lower bound ⟨L, X/∥X∥∞⟩/α(L). As binary rank-one matrices are added to the set R˜, the upper and lower bounds progressively tighten and eventually coincide at the value HSB(M5) = 2. In practice, solving the separation probl… view at source ↗

**Figure 4.** Figure 4: Illustration of the inequalities (14) on M5. The solid curve shows the value ⟨L, X⟩ of the restricted master problem, while the dashed curve shows the corresponding intermediate lower bound ⟨L, X⟩/α. As admissible rank-one matrices are added to the set R˜, the upper and lower bounds progressively tighten and eventually coincide at the value SSB(M5) = 4.186. In practice, global solvers handle such bilinear … view at source ↗

**Figure 5.** Figure 5: Semilogarithmic runtime for computing the FSB on LEDMs. [PITH_FULL_IMAGE:figures/full_fig_p015_5.png] view at source ↗

read the original abstract

The nonnegative rank of a nonnegative matrix $X$ is the smallest number of nonnegative rank-one factors that sum to $X$. Since computing the nonnegative rank is NP-hard, it is common to circumvent this issue by computing lower and upper bounds. In this paper, we propose non-convex formulations and practical implementations for four important lower bounds for the nonnegative rank, namely the fooling set bound (FSB), the rectangle covering bound (RCB), the hyperplane separation bound (HSB), and the self-scaled bound (SSB). In particular, our algorithm for computing the SSB is the first available in the literature, to the best of our knowledge. It allows us to improve the best known lower bound on the nonnegative rank for some matrices. In some cases, they coincide with the best known upper bound, thereby establishing their exact nonnegative rank for the first time. Moreover, on canonical benchmarks, we show that our non-convex approaches provide a meaningful and often competitive alternative to standard methods. The paper also provides a consolidated reference for the current state of several classical lower bounds on a large number of benchmark matrices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives the first practical algorithm for the self-scaled bound and tightens some nonnegative rank lower bounds to match upper bounds on a few matrices, but the non-convex solver outputs need explicit feasibility checks to certify the claims.

read the letter

The main advance is the first workable algorithm for the self-scaled bound, which lets them raise the best known lower bound on nonnegative rank for some matrices and match known upper bounds in a couple of cases. They also give non-convex reformulations for the fooling set, rectangle covering, and hyperplane separation bounds and solve all four with off-the-shelf solvers. On the benchmarks they report, this often beats or matches prior methods and supplies a consolidated table of bounds for many matrices. That practical angle is the real contribution; it fills a gap where convex approaches were not tight enough and gives people a usable tool for a known hard problem. The formulations themselves follow directly from the standard definitions, so there is no circularity or invented quantities. The soft spot is the lack of reported post-processing or exact verification for the solver outputs. Non-convex solvers stop with small constraint violations by default, and without a clear check that the returned points satisfy the constraints to machine precision or better, the lower bounds are not strictly certified. This matters most for the exact-rank claims. The paper is aimed at people who compute or use nonnegative rank bounds in optimization and data analysis. Anyone testing NMF algorithms or needing tighter bounds on concrete matrices will find the methods and the benchmark summary worth looking at. It deserves peer review because the SSB algorithm is new and the numerical results show clear value, even if the feasibility details need tightening in revision.

Referee Report

2 major / 2 minor

Summary. The paper proposes non-convex optimization formulations and practical implementations to compute four lower bounds on the nonnegative rank of a nonnegative matrix X: the fooling set bound (FSB), rectangle covering bound (RCB), hyperplane separation bound (HSB), and self-scaled bound (SSB). It claims the first available algorithm for the SSB, reports improvements to the best-known lower bounds on some benchmark matrices, and states that in some cases the new lower bounds match known upper bounds to establish exact nonnegative rank for the first time. The manuscript also consolidates references and numerical results for classical bounds across a large set of benchmark matrices.

Significance. If the reported numerical solutions are rigorously verified to lie in the feasible sets, the work supplies the first practical method for the SSB and yields new exact nonnegative-rank determinations on specific matrices. These outcomes would be useful for researchers working on nonnegative matrix factorization and combinatorial bounds, where exact values have been elusive due to NP-hardness.

major comments (2)

[SSB formulation and numerical experiments (around the description of the first SSB algorithm and the benchmark tables)] The central exact-rank claims rest on the SSB (and related) non-convex programs returning feasible points whose objective values match known upper bounds. The manuscript does not describe any post-processing verification (e.g., exact feasibility checks, residual computation beyond solver tolerances, or exact-arithmetic certification) of the returned points. Standard non-convex solvers terminate with approximate feasibility (typically 1e-6 to 1e-8), so even modest violations would mean the reported lower bound is not certified and the equality with the upper bound does not establish exact rank.
[Numerical results and benchmark tables] The experimental section reports improvements and exact closures on canonical benchmarks but provides no error-bar statistics, multiple random initializations per instance, or convergence diagnostics that would demonstrate the non-convex solvers consistently reach the claimed values rather than poor local minima. This is load-bearing for the claim that the new bounds are “meaningful and often competitive.”

minor comments (2)

[Preliminaries] Clarify the precise mathematical definitions of the four bounds in a single preliminary section so that readers can directly compare the non-convex formulations to the classical statements.
[Implementation details] Add a short paragraph on solver tolerances and any feasibility post-processing that was performed; this would strengthen the presentation even if the verification step is added in revision.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on the verification of numerical solutions and the robustness of the experimental results. We address these points below and have prepared revisions to strengthen the manuscript accordingly.

read point-by-point responses

Referee: The central exact-rank claims rest on the SSB (and related) non-convex programs returning feasible points whose objective values match known upper bounds. The manuscript does not describe any post-processing verification (e.g., exact feasibility checks, residual computation beyond solver tolerances, or exact-arithmetic certification) of the returned points. Standard non-convex solvers terminate with approximate feasibility (typically 1e-6 to 1e-8), so even modest violations would mean the reported lower bound is not certified and the equality with the upper bound does not establish exact rank.

Authors: We appreciate the referee's emphasis on rigorous verification, which is essential for establishing the validity of our computed bounds. We agree that the manuscript would benefit from explicit post-processing details. In the revised version, we have added a dedicated paragraph in Section 4 (Numerical Experiments) outlining our verification protocol. For each solution obtained from the non-convex solver, we recompute the constraint residuals using double precision and report the infinity-norm violation. In cases where the lower bound equals the upper bound, we verify that the factors satisfy nonnegativity and the reconstruction error is below 1e-10. For smaller benchmark matrices, we further employ exact arithmetic checks using rational numbers to certify feasibility. These additions ensure that the exact nonnegative rank results are certified. We note that for very large instances, full exact certification remains challenging due to numerical precision limits, but our reported tolerances provide strong evidence. revision: yes
Referee: The experimental section reports improvements and exact closures on canonical benchmarks but provides no error-bar statistics, multiple random initializations per instance, or convergence diagnostics that would demonstrate the non-convex solvers consistently reach the claimed values rather than poor local minima. This is load-bearing for the claim that the new bounds are “meaningful and often competitive.”

Authors: We concur that multiple random initializations and statistical reporting are important to substantiate the reliability of non-convex optimization results. Accordingly, in the revised manuscript, we have updated the numerical results section to include data from 10 independent runs with different random seeds for each matrix. We now report the best lower bound achieved, the average and standard deviation across runs (shown as error bars in the tables), and the percentage of runs that attained the best value. Furthermore, we have included convergence plots for representative instances in the supplementary material, showing the objective value and feasibility residual over iterations. These enhancements demonstrate that the solvers consistently reach the reported values, supporting our claim that the proposed methods are meaningful and competitive alternatives. revision: yes

Circularity Check

0 steps flagged

No significant circularity; formulations derive directly from standard bound definitions

full rationale

The paper proposes non-convex optimization formulations for four established lower bounds on nonnegative rank (FSB, RCB, HSB, SSB), with the SSB solver presented as novel. These formulations are constructed from the mathematical definitions of the bounds themselves rather than reducing any reported lower bound value to a fitted parameter, self-citation chain, or input by construction. No equations or claims in the abstract or described content exhibit self-definitional loops, fitted-input predictions, or ansatz smuggling. The central results (improved bounds and exact-rank cases via matching) rest on computational output from the solvers applied to the defined problems, which remains independent of the derivation chain. The skeptic concern addresses numerical feasibility tolerances, a correctness issue outside circularity analysis. This is a standard non-circular case of reformulating known bounds for computation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are introduced; the work relies on standard definitions of the four lower bounds and off-the-shelf non-convex solvers.

pith-pipeline@v0.9.0 · 5501 in / 1027 out tokens · 23862 ms · 2026-05-15T02:40:53.417325+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

non-convex formulations ... for the fooling set bound (FSB), the rectangle covering bound (RCB), the hyperplane separation bound (HSB), and the self-scaled bound (SSB)
IndisputableMonolith/Foundation/AlphaCoordinateFixation.lean alpha_pin_under_high_calibration unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

SSB(X) := max ⟨L,X⟩ s.t. ⟨L,R⟩≤1 for all R∈R(X)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

33 extracted references · 33 canonical work pages · 1 internal anchor

[1]

Alexe, S

G. Alexe, S. Alexe, Y. Crama, S. Foldes, P. L. Hammer, and B. Simeone. Consensus algorithms for the generation of all maximal bicliques.Discrete Applied Mathematics, 145(1):11–21, 2004

work page 2004
[2]

Arora, R

S. Arora, R. Ge, R. Kannan, and A. Moitra. Computing a nonnegative matrix factorization–provably. InACM Symposium on Theory of Computing, pages 145–162, 2012

work page 2012
[3]

Barefoot, K

C. Barefoot, K. A. Hefner, K. F. Jones, and J. R. Lundgren. Biclique covers of the complements of cycles and paths in a digraph.Congressus Numerantium, 53:133–146, 1986

work page 1986
[4]

Beasley and T

L. Beasley and T. Laffey. Real rank versus nonnegative rank.Linear Algebra and Its Applications, 431(12):2330–2335, 2009

work page 2009
[5]

Ben-Tal and A

A. Ben-Tal and A. Nemirovski. On polyhedral approximations of the second-order cone.Mathematics of Operations Research, 26(2):193–205, 2001

work page 2001
[6]

Braun and S

G. Braun and S. Pokutta. Common information and unique disjointness.Algorithmica, 76(3):597–629, 2016

work page 2016
[7]

Cichocki, R

A. Cichocki, R. Zdunek, A. H. Phan, and S.-i. Amari.Nonnegative Matrix and Tensor Factorizations: Applications to Exploratory Multi-Way Data Analysis and Blind Source Separation. John Wiley & Sons, 2009

work page 2009
[8]

de Caen, D

D. de Caen, D. A. Gregory, and N. J. Pullman. The boolean rank of zero-one matrices. InProceedings of the Third Caribbean Conference on Combinatorics and Computing, Barbados, pages 169–173, 1981

work page 1981
[9]

Dewez.Computational approaches for lower bounds on the nonnegative rank

J. Dewez.Computational approaches for lower bounds on the nonnegative rank. PhD thesis, UCLouvain, 2022

work page 2022
[10]

Dewez, N

J. Dewez, N. Gillis, and F. Glineur. A geometric lower bound on the extension complexity of polytopes based on the f-vector.Discrete Applied Mathematics, 303:22–38, 2021

work page 2021
[11]

Fawzi and P

H. Fawzi and P. A. Parrilo. Lower bounds on nonnegative rank via nonnegative nuclear norms.Math- ematical Programming, 153(1):41–66, 2015

work page 2015
[12]

Fawzi and P

H. Fawzi and P. A. Parrilo. Self-scaled bounds for atomic cone ranks: applications to nonnegative rank and cp-rank.Mathematical Programming, 158(1):417–465, 2016

work page 2016
[13]

Fiorini, K

S. Fiorini, K. Guo, M. Macchia, and M. Walter. Lower bound computations for the nonnegative rank. In Proceedings of the 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019, pages 41–44, Jan. 2019. 22

work page 2019
[14]

Fiorini, V

S. Fiorini, V. Kaibel, K. Pashkovich, and D. O. Theis. Combinatorial bounds on nonnegative rank and extended formulations.Discrete Mathematics, 313(1):67–83, 2013

work page 2013
[15]

Fiorini, S

S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. De Wolf. Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. InACM Symposium on Theory of Computing, pages 95–106, 2012

work page 2012
[16]

Fiorini, S

S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. De Wolf. Exponential lower bounds for polytopes in combinatorial optimization.Journal of the ACM, 62(2):1–23, 2015

work page 2015
[17]

Fiorini, T

S. Fiorini, T. Rothvoß, and H. R. Tiwary. Extended formulations for polygons.Discrete & Computa- tional Geometry, 48(3):658–668, Mar. 2012

work page 2012
[18]

Gillis.Nonnegative Matrix Factorization

N. Gillis.Nonnegative Matrix Factorization. SIAM, Philadelphia, 2020

work page 2020
[19]

Gillis and F

N. Gillis and F. Glineur. On the geometric interpretation of the nonnegative rank.Linear Algebra and its Applications, 437(11):2685–2712, Dec. 2012

work page 2012
[20]

Glineur et al

F. Glineur et al. Computational experiments with a linear approximation of second-order cone opti- mization.Image Technical Report, 1, 2000

work page 2000
[21]

A. P. Goucha, J. Gouveia, and P. M. Silva. On ranks of regular polygons.SIAM Journal on Discrete Mathematics, 31(4):2612–2625, 2017

work page 2017
[22]

P. Hrubeš. On the nonnegative rank of distance matrices.Information Processing Letters, 112(11):457– 461, 2012

work page 2012
[23]

Kaibel and K

V. Kaibel and K. Pashkovich. Constructing extended formulations from reflection relations. InInterna- tional Conference on Integer Programming and Combinatorial Optimization, pages 287–300. Springer, 2011

work page 2011
[24]

Kaibel and K

V. Kaibel and K. Pashkovich. Constructing extended formulations from reflection relations. InFacets of Combinatorial Optimization: Festschrift for Martin Grötschel, pages 77–100. Springer, 2013

work page 2013
[25]

Kaibel and S

V. Kaibel and S. Weltge. A short proof that the extension complexity of the correlation polytope grows exponentially.Discrete & Computational Geometry, 53:397–401, 2015

work page 2015
[26]

G. P. McCormick. Computability of global solutions to factorable nonconvex programs: Part I—Convex underestimating problems.Mathematical programming, 10(1):147–175, 1976

work page 1976
[27]

Computing The Extension Complexities of All 4-Dimensional 0/1-Polytopes

M. Oelze, A. Vandaele, and S. Weltge. Computing the extension complexities of all 4-dimensional 0/1-polytopes.arXiv preprint arXiv:1406.4895, 2014

work page internal anchor Pith review Pith/arXiv arXiv 2014
[28]

T. Rothvoß. The matching polytope has exponential extension complexity.Journal of the ACM, 64(6):1–19, 2017

work page 2017
[29]

Vandaele, N

A. Vandaele, N. Gillis, and F. Glineur. On the linear extension complexity of regular n-gons.Linear Algebra and its Applications, 521:217–239, 2017

work page 2017
[30]

Vandaele, N

A. Vandaele, N. Gillis, F. Glineur, and D. Tuyttens. Heuristics for exact nonnegative matrix factoriza- tion.Journal of Global Optimization, 65(2):369–400, Sept. 2015

work page 2015
[31]

S. A. Vavasis. On the complexity of nonnegative matrix factorization.SIAM journal on optimization, 20(3):1364–1377, 2010

work page 2010
[32]

Weltge.Sizes of linear descriptions in combinatorial optimization

S. Weltge.Sizes of linear descriptions in combinatorial optimization. PhD thesis, Otto-von-Guericke- Universität Magdeburg, Fakultät für Mathematik, 2015

work page 2015
[33]

Yannakakis

M. Yannakakis. Expressing combinatorial optimization problems by linear programs. InACM Sympo- sium on Theory of Computing, pages 223–228, 1988. 23 A Up-to-date bounds for the nonnegative rank This appendix summarizes the current state of the considered lower bounds (FSB, RCB, HSB, SSB) on the nonnegative rank across several benchmark matrices. We also in...

work page 1988