arXiv:2605.14058 · v4
Computing Lower Bounds on the Nonnegative Rank via Non-Convex Optimization Solvers
摘要
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.
作者备注：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