Nonnegative rank of a matrix and projections onto a polyhedron

In LinAlg, NnegRk, Research, Xpository on January 5, 2011 at 17:22

For a nonnegative matrix ${(m\times n)}$ -matrix ${A}$ , its nonnegative rank ${\mbox{rk}_+(A)}$ is the smallest integer ${q}$ for which there exist nonnegative matrices ${B}$ and ${C}$ with ${q}$ columns such that ${A = BC^T}$ . Expanding the product, this is the same as the minimum number of nonnegative rank-1 matrices which sum up to ${A}$ :

$\displaystyle A = B C^T = \sum_{j=1}^q B_{\cdot,j} C_{\cdot,j}^T. \ \ \ \ \ (1)$

The expression ${BC^T}$ is called a nonnegative factorization of size ${q}$ of ${A}$ .

Recall that the extension complexity of a (convex) polyhedron is the minimum number of facets of a polyhedron ${Q}$ for which there exists a projective mapping ${\pi}$ which maps ${Q}$ onto(!) ${P}$ .

In this post I would like to cover the relationship between the nonnegative rank ${\mbox{rk}_+(A)}$ of a nonnegative matrix ${A}$ and extension complexity ${\mbox{xc}(P)}$ of a polyhedron ${P}$ . As it turns out, the extension complexity of ${P}$ is just the nonnegative rank of the so-called slack matrix of ${P}$ (or, more accureately, any slack matrix).

This essentially goes back to Yannakakis’ 1991 paper Expressing combinatorial optimization problems by linear programs.

The slack matrix

The central object linking extension complexity of polyhedra and nonnegative rank is the slack matrix. Let the polyhedron ${P\subset{\mathbb R}^d}$ be given by a system of linear inequalities

$\displaystyle f_k(x) - \beta_k \ge 0 \qquad\forall k=1,\dots,m, \ \ \ \ \ (2)$

where each ${f_k}$ is an affine function ${{\mathbb R}^d\rightarrow {\mathbb R}}$ , and the ${\beta_k}$ are in ${{\mathbb R}}$ ; and also by a set of points ${x_1,\dots,x_{n_1} \subset {\mathbb R}^d}$ and vectors ${y_1,\dots,y_{n_2} \in {\mathbb R}^d}$ , i.e.,

$\displaystyle P = \mbox{cvx}\{x_1,\dots,x_{n_1}\} +\mbox{cvxcone}\{y_1,\dots,y_{n_2}\}, \ \ \ \ \ (3)$

where ${\mbox{cvx} X}$ denotes the convex set generated by ${X}$ and ${\mbox{cvxcone} Y}$ denotes the convex cone generated by ${Y}$ . Let ${n := n_1+n_2}$ , and consider the ${(n\times m)}$ -matrix ${S}$ defined by

$\displaystyle S_{k,\ell} = \left\{\begin{array}{ll} f_k(x_\ell) - \beta_k & \text{ if } \ell\le n_1\\ f_k(y_{\ell-n_1}) & \text{ if } \ell > n_1 \end{array}\right. \ \ \ \ \ (4)$

This matrix is called a slack matrix of ${P}$ with respect to the systems (2) and (3).

Nonnegative factorizations of the slack matrix and extensions of the polyhedron

The following is the central fact of this post.

Theorem 1

Every nonnegative factorization of ${S}$ of size ${q}$ gives rise to an extension of ${P}$ with at most ${q}$ facets.
Every extension of ${P}$ with ${q}$ facets gives rise to a nonnegative factorization of ${S}$ of size at most ${q}$ .

In particular, $\mbox{rk}_+(S) = \mbox{xc}(P)$ .

Some remarks about the nonnegative factorization

In the “linear” case, we know that row- or column-operations does not change the rank of a matrix. The same is true for the nonnegative rank — but only “nonnegative” row- and column-operations are allowed. A nonnegative column operation is one of the following:

multiplying a row by a strictly positive scalar,
adding a nonnegative multiple of one row to another row,
adding a new row to the matrix, all of whose entries are 0.

Nonnegative column-operations are defined similarly. The following is an easy exercise.

Lemma 2 If the matrix ${A'}$ results from ${A}$ by a series of nonnegative row- and column-operations, then for every nonnegative factorization of ${A}$ of size ${q}$ , there is a nonnegative factorization of ${A'}$ of size ${q}$ , and vice versa.

In particular, ${\mbox{rk}_+ A' = \mbox{rk}_+ A}$ .

A (projective) extension gives a factorization

We now prove the first part of Theorem 1. We first deal with the basic case when ${P}$ is a polyhedral cone, the $\beta_k$ are all zero, and the projections are required to be linear. After that, we will reduce the general cases to this one.

Suppose that ${P}$ is a polyhedral cone which is not a point. This implies that ${0}$ must be among the points ${x_1,\dots,x_{n_1}}$ , and ${\beta_k=0}$ for all ${k}$ . By Lemma 2, we may assume that ${n_1=1}$ and ${x_1 = 0}$ . Deleting the corresponding 0-column, we arrive at ${n=n_2}$ and we are interested in nonnegative factorizations of the ${(m\times n)}$ -matrix ${S}$ defined as ${S_{k,\ell} = f_k(x_\ell)}$ .

We first prove that an extension with linear projection mapping gives rise to a nonnegative factorization of appropriate size. Suppose that there is a polyhedron ${Q \subset {\mathbb R}^{d'}}$ and a linear mapping ${\pi\colon {\mathbb R}^{d'}\rightarrow {\mathbb R}^d}$ which maps ${Q}$ onto ${P}$ . By a translation, we may assume that ${0\in Q}$ . Denoting by ${\pi^*}$ the adjoint linear mapping, the linear inequalities ${\pi^*(f_k)(z) \ge 0}$ are valid for ${Q}$ . Moreover, since these inequalites are satisfied with equality by the point ${0\in Q}$ , for example, by Farkas’ Lemma, ${\pi^*(f_k)}$ is a nonnegative linear combination of linear functions ${g_j}$ for which the inequality ${g_j(z) \ge 0}$ define a facet of ${Q}$ :

$\displaystyle \pi^*(f_k) = \sum_{j=1}^q \lambda_{k,j} g_j. \ \ \ \ \ (6)$

Choosing for every ${\ell}$ a ${z_\ell \in Q}$ with ${\pi(x_\ell) = x_\ell}$ , we conclude

$\displaystyle f_k(x_\ell) = f_k(\pi(z_\ell)) = \pi^*(f_k)(z_\ell) = \sum_{j=1}^q \lambda_{k,j} g_j(z_\ell) = (\Lambda T)_{k,\ell}$

if we let ${\lambda_{k,j} = \lambda_{k,j}}$ and ${T_{j,\ell} := g_j(z_\ell)}$ . Thus we have a nonnegative factorization whose size ${q}$ is no larger than the number of facets of ${Q}$ .

Secondly, we need to show that the general case ( ${P}$ a polyhedron and the projection allowed to be projective) is implied by the cone/linear case. This is done easily by homogenization. Saying that ${\pi\colon {\mathbb R}^{d'} \rightarrow {\mathbb R}^d}$ is projective with ${\pi(Q) = P}$ is the same as saying that ${\pi}$ arises from a linear mapping ${\bar\pi\colon{\mathbb R}^{d'+1}\rightarrow{\mathbb R}^{d+1}}$ which maps ${Q\times\{1\}}$ onto ${P\times\{1\}}$ . But then ${\bar\pi}$ also maps the homogenization ${\bar Q}$ of ${Q}$ onto the homogenization ${\bar P}$ of ${P}$ . A factorization of a slack matrix of ${P}$ is also a slack matrix of ${\bar P}$ .

A factorization gives an affine extension

Here we prove that every nonnegative factorization of the slack matrix of a polyhedron gives rise to an extension. Indeed, if ${S = CZ^T}$ , then define the polyhedron

$\displaystyle Q := \left\{ (x,z) \mid f_k(x) - B_{k,\cdot}z = \beta_k \forall k, \; z\ge 0 \right\}, \ \ \ \ \ (7)$

and the projection ${\pi\colon (x,z) \mapsto x}$ . Clearly, if ${(x,z)\in Q}$ then ${By \ge 0}$ and so ${\pi(x,z) = z}$ satisfies ${f_k(x) \ge \beta_k}$ for all ${k}$ , which implies that ${x \in P}$ (because the system (2) defines ${P}$ ).

To see that ${\pi}$ maps ${Q}$ onto ${P}$ , denote the rows of ${Z}$ by ${z_1,\dots,z_n}$ . Then, for ${\ell=1,\dots,n_1}$ we have

$\displaystyle f_k(x_\ell) -\beta_k = C_{k,\cdot} z_\ell, \ \ \ \ \ (8)$

whereas for ${\ell'=1,\dots,n_2}$ , the equation is

$\displaystyle f_k(y_\ell') = C_{k,\cdot} z_{n_1+\ell'}. \ \ \ \ \ (9)$

To show that ${\pi(Q)}$ contains ${P}$ , we prove that that ${x_\ell \in \pi(Q)}$ for all ${\ell}$ , and ${x_1+ t y_\ell \in \pi(Q)}$ for all ${\ell}$ and ${t > 0}$ . But ${z_\ell\in Q}$ for ${\ell=1,\dots,n_1}$ by (8), and ${z_1+z_{n_1+\ell'} \in Q}$ follows form the linearity of ${f_k}$ and ${C_{k,\cdot}}$ by (8) for ${\ell=1}$ and (9).