On the geometric interpretation of the nonnegative rank (Q1758469)

A new quantity called the restricted nonnegative rank, whose computation amounts to solving a problem in computational geometry consisting of finding a polytope nested between two given polytopes is introduced. This allows characterizing its computational complexity. The geometric interpretation and the relationship between the nonnegative rank and the restricted nonnegative rank let to derive new improved lower bounds for the nonnegative rank, in particular for slack matrices and linear Euclidean distance matrices. This allows obtaining counter-examples to two conjectures of Beasley and Laffey, namely, it is shown that the nonnegative rank of linear Euclidean distance matrices is not necessarily equal to their dimension, and that the rank of a matrix is not always greater than the nonnegative rank of its square.