Lower bounds on the nonnegative rank using a nested polytopes formulation

Julien Dewez and François Glineur
Additional contact information
Julien Dewez: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3166, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

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.

Date: 2021-01-01
Note: In: ESANN2020, 28th European Symposium on Artificial Neural Networks - Computational Intelligence and Machine Learning, 2020
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3166

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().