Lower bound computations for the nonnegative rank

Samuel Fiorini, Krystal Guo, Marco Macchia, Matthias Walter

Research output: Contribution to conferencePaperAcademicpeer-review

Abstract

The nonnegative rank of a matrix is the smallest inner dimension when writing it as a product of two nonnegative matrices. Such nonnegative matrix factorizations have numerous applications in machine learning and data mining, where one usually allows inexact factorizations. The exact counterpart is related to the so-called extension complexity of a polytope, an important parameter in combinatorial optimization. We implemented different algorithms for computing lower bounds on the nonnegative rank of a matrix. In this extended abstract we focus on results that relate our best algorithms' performance to the size of the matrix.

Original languageEnglish
Pages41-44
Number of pages4
Publication statusPublished - 1 Jan 2019
Event17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 - U-Parkhotel, Enschede, Netherlands
Duration: 1 Jul 20193 Jul 2019
Conference number: 17
http://wwwhome.math.utwente.nl/~ctw/

Workshop

Workshop17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019
Abbreviated titleCTW 2019
CountryNetherlands
CityEnschede
Period1/07/193/07/19
Internet address

Fingerprint Dive into the research topics of 'Lower bound computations for the nonnegative rank'. Together they form a unique fingerprint.

Cite this