Lower bounds on the nonnegative rank using a nested polytopes formulation
(2020) ESANN 2020,28th European Symposium on Artificial Neural Networks - Computational Intelligence and Machine Learning — Location: Bruges, Belgium (2.October.2020)
Files
CORE_RP_3166.pdf
Open Access - Adobe PDF
- 750.28 KB
Details
- Authors
- Abstract
- Computing the nonnegative rank of a nonnegative matrix has been proven to be, in general, NP-hard. However, this quantity has many interesting applications, e.g., it can be used to compute the ex- tension complexity of polytopes. Therefore researchers have been trying to approximate this quantity as closely as possible with strong lower and upper bounds. In this work, we introduce a new lower bound on the nonnegative rank based on a representation of the matrix as a pair of nested polytopes. The nonnegative rank then corresponds to the minimum num-er of vertices of any polytope nested between these two polytopes. Using the geometric concept of supporting corner, we introduce a parametrized family of computable lower bounds and present preliminary numerical results on slack matrices of regular polygons.
- Affiliations
Citations
Dewez, J., & Glineur, F. (2020). Lower bounds on the nonnegative rank using a nested polytopes formulation. ESANN2020, 28th European Symposium on Artificial Neural Networks - Computational Intelligence and Machine Learning. Published. ESANN 2020,28th European Symposium on Artificial Neural Networks - Computational Intelligence and Machine Learning, Bruges, Belgium. https://hdl.handle.net/2078.5/273553