Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
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.
Related
- Computing Lower Bounds on the Non-negative Rank via SAT Solvers
- Comment on "The polarization hierarchy for polynomial optimization over convex bodies, with applications to nonnegative matrix rank"
- Generation of Custom Solvers in Rust for Convex Optimization
- Low-Thrust Trajectory Optimization with Quantum Computing and Sequential Convex Programming
- Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds
BibTeX
@misc{baeckelant2026computing,
title = {{Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers}},
author = {Timothy Baeckelant and Arnaud Vandaele and Nicolas Gillis},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2605.14058},
eprint = {2605.14058},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.14058},
}
RIS
TY - UNPB
TI - Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
AU - Timothy Baeckelant
AU - Arnaud Vandaele
AU - Nicolas Gillis
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2605.14058
UR - https://arxiv.org/abs/2605.14058
AB - 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.
ER -