Lower bound computations for the nonnegative rank

Samuel Fiorini; Krystal Guo; Marco Macchia; Matthias Walter

Lower bound computations for the nonnegative rank

Samuel Fiorini, Krystal Guo, Marco Macchia, Matthias Walter

Mathematics of Operations Research

Research output: Contribution to conference › Paper › peer-review

1 Citation (Scopus)

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 language	English
Pages	41-44
Number of pages	4
Publication status	Published - 1 Jan 2019
Event	17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019 - U-Parkhotel, Enschede, Netherlands Duration: 1 Jul 2019 → 3 Jul 2019 Conference number: 17 http://wwwhome.math.utwente.nl/~ctw/

Workshop

Workshop	17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019
Abbreviated title	CTW 2019
Country/Territory	Netherlands
City	Enschede
Period	1/07/19 → 3/07/19
Internet address	http://wwwhome.math.utwente.nl/~ctw/

Cite this

@conference{c2066a9ff937408e98f1585998ac81fd,

title = "Lower bound computations for the nonnegative rank",

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.",

author = "Samuel Fiorini and Krystal Guo and Marco Macchia and Matthias Walter",

year = "2019",

month = jan,

day = "1",

language = "English",

pages = "41--44",

note = "17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019, CTW 2019 ; Conference date: 01-07-2019 Through 03-07-2019",

url = "http://wwwhome.math.utwente.nl/\textasciitilde{}ctw/",

}

TY - CONF

T1 - Lower bound computations for the nonnegative rank

AU - Fiorini, Samuel

AU - Guo, Krystal

AU - Macchia, Marco

AU - Walter, Matthias

N1 - Conference code: 17

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85084360074&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:85084360074

SP - 41

EP - 44

T2 - 17th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2019

Y2 - 1 July 2019 through 3 July 2019

ER -

Lower bound computations for the nonnegative rank

Abstract

Workshop

Other files and links

Fingerprint

Cite this