Paperlane

no. 13 · Wednesday 11 November 2026

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

Timothy Baeckelant, Arnaud Vandaele and Nicolas Gillis

math.OC · v4

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, to the best of our knowledge, our algorithm for computing the SSB is the first available in the literature. We compute the SSB for several matrices for which its value had not previously been reported. In some cases, the SSB provides the best known upper bound, while the other three bounds do not. Moreover, on canonical benchmarks, we show that our non-convex approaches are often competitive with existing methods. The paper also provides a consolidated reference for the current state of several classical lower bounds on a large number of benchmark matrices.

comments
Added a proof that the hyperplane separation bound equals 2 for the linear Euclidean distance matrices studied here. Improved the lower bound on the nonnegative rank of the slack matrix of the icosidodecahedron from 10 to 11. Clarified how the self-scaled bound recovers the known nonnegative rank of 7 for both M11 and M12
fields
Optimization and Control
pdf ↗ page arXiv:2605.14058 ↗