Computational approaches for lower bounds on the nonnegative rank

Nonnegative matrix factorization (NMF) consists in finding two nonnegative matrices whose product is equal to (or approximates) a nonnegative data matrix. NMF is a powerful data analysis tool used to extract meaningful information when the observed data is nonnegative by nature; for example, in text mining, in hyperspectral unmixing, in audio source separation, and in many more applications. The minimum inner dimension of such a factorization is called the nonnegative rank, and computing this quantity is NP-hard in general. Nevertheless, it has several interesting applications; for example, in combinatorial optimization, the extension complexity of a polytope is equal to the nonnegative rank of its slack matrix. Other uses appear in statistics, in information theory, etc. Therefore, there has been interest in determining strong lower and upper bounds to approximate it as closely as possible. In this thesis, we introduce new lower bounds on the nonnegative rank based on some properties of geometric representations of the matrix. First, we introduce a lower bound for slack matrices of convex polytopes, based on a purely geometrical description of the polytope gathering its numbers of faces in each dimension, and on how it changes under projections. In the second part, we introduce a lower bound based on a representation of the matrix as a pair of nested polytopes. Then, we define a framework, based on a series of mixed integer formulations, in which lower bounds can be computed, and we introduce some dynamic methods to get stronger bounds. We compute these bounds on a collection of matrices and show how they can outperform other approaches from the literature.(FSA - Sciences de l'ingénieur) -- UCL, 202