By Kaie Kubjas
The rank of a matrix M is a fundamental notion in linear algebra. While usually defined as the dimension of the span of the rows or the span of the columns, it could also be defined as the minimal number r such that the matrix M admits a factorization as M=AB, where A has r columns and B has r rows. If all entries of the matrix M are nonnegative, then such a factorization can be pictured as a pair of nested polytopes: the outer one is given by the inequalities Ax≥0, and the inner one by the convex hull of the columns of B. Up to an affine transformation, this picture is independent of the specific factorization AB.
Figure 1: Two nested polygons corresponding to a rank 3 matrix with 6 rows and 5 columns
In many applications, we are interested in factorizations of a certain particular form. For example, we can study factorizations M=AB where A,B have nonnegative entries. The minimal r as above for which such a factorization exists is called the nonnegative rank. Cohen and Rothblum formulated this definition geometrically: a nonnegative matrix M has nonnegative rank at most r if and only if there exists a polytope with r vertices that can be fitted between two nested polytopes associated with the matrix.
Figure 2: Two quadrangles and a triangle between them
The interest in the nonnegative rank started in the combinatorial optimization community with the work of Yannakakis at the end of the 1980s. A linear program aims to minimize or maximize a linear function over a region that is given by linear constraints, i.e., a polyhedron or a polytope. Yannakakis showed that the minimal number of variables and constraints needed to express a linear program over a polytope is closely related to the nonnegative rank of a matrix associated to this polytope.
One line of research that started with the seminal paper of Yannakakis studies lower bounds on the nonnegative rank, and later also on the positive semidefinite rank, for different polytopes that appear in combinatorial optimization. For example, the Traveling Salesman Problem (TSP) asks: Given a list of cities, what is the shortest cycle that visits every city exactly once? It can be formulated as a linear program over a region which is called the TSP polytope. The TSP problem is NP-hard, and some of the attempts to prove P=NP aimed to give polynomial formulations of the TSP polytope. This motivated Yannakakis to look for superpolynomial lower bounds on the nonnegative rank of the TSP polytope, which was completed by Fiorini et al. in 2012.
The notion of nonnegative rank also appears in statistics: The set of stochastic matrices of nonnegative rank at most r is called the r-th mixture model. It represents the joint probabilities of two random variables that are independent given a third random variable with r possible values. Given a data matrix that is obtained by an opinion poll or a measurement, one would like to estimate the parameters of the true probability distribution that the data come from. Specifically, the maximum likelihood estimate of a data matrix is a matrix in the r-th mixture model that maximizes a specific function, called the likelihood function. There are several ways for numerically solving the maximum likelihood estimation in practice. These methods, however, do not provide a certificate for having found the global optimum.
In my recent research together with Eggermont, Horobeţ, Robeva, and Sturmfels (Robeva and Sturmfels attended the Algebraic Geometry program, and Horobeţ participated in one of the workshops at the Simons Insitute), we have been interested in exact descriptions of the sets of matrices of nonnegative rank at most r. They are semialgebraic sets, which means that they can be characterized by Boolean combinations of polynomial equations and inequalities. Knowing quantifier-free semialgebraic descriptions of these sets would give an exact method for checking if a matrix lies in them. It would be also an essential step towards computing maximum likelihood estimates with certificate.