Suppose $v_1,\dots,v_n \in \mathbb{R}^k$ are entry-wise non-negative (column) vectors with $k<n$. Let $r \leq k$ be the non-negative rank of the matrix $V = [v_1 v_2 \cdots v_n]$ (i.e., the smallest $r$ such that $V$ can be written as the product $V= UW$ where $U \in \mathbb{R}^{k \times r}, W \in \mathbb{R}^{r \times n}$ and $U,W$ are entry-wise non-negative). For any set of vectors $S = \{x_1,\dots,x_m\}$, define the conic convex hull as

$$\text{coni}(S) = \{ y \; |\; y = \sum_{x_i \in S} \alpha_i x_i , \text{ s.t. } \forall i, 0 \leq \alpha_i \in \mathbb{R} \}$$

Then for any subset $S \subseteq \{v_1,\dots,v_n\}$ of size $|S| > r$, one can show that there exists a $v_i \in S$ such that $v_i \in \text{coni}( S \setminus \{v_i\})$. In other words, there will be at least one vector $v_i \in S$ that is a conic combination of the other vectors in $S$. However, this does not imply the existence of a "conic basis" set $B \subset \{v_1,\dots,v_n\}$ with $|B| \leq r$ such that for all $i \in [n]$ we have $v_i \in \text{coni}(B)$.

Define $\text{rank}_+^*(V)$ to be the smallest integer $r^*$ such that there is a submatrix $B$ of $r^*$ columns of $V$ such that every column $v_i$ of $V$ is a conic combination of the columns of $B$. By the fact in the prior paragraph, $\text{rank}_+^*(V) \leq n-1$ is a trivial upper bound. I am interested in a better upper bound in general, especially when $k <<n$. Is it the case that $\text{rank}_+^*(V) \leq r$?

Question: What is the best upper bound that can be given for $\text{rank}_+^*(V)$ in general?

Gillis, Nicolas. "Introduction to nonnegative matrix factorization." arXiv preprint arXiv:1703.00663 (2017).


1 Answer 1


It is not true that $\text{rank}_+^*(V) \leq \text{rank}_+(V) $. In fact, an equivalent definition of the non-negative rank of $V$ is the minimum number of non-negative vectors (not necessarily columns of $V$) such that every column of $V$ is a conic combination of these vectors. Therefore, the opposite inequality $\text{rank}_+^*(V) \geq \text{rank}_+(V) $ holds.

For an explicit example where $\text{rank}_+^*(V) > \text{rank}_+(V) $, consider the matrix

$$ V= \begin{bmatrix} 1 & 0 & 1 & 2 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 1 \end{bmatrix} $$

It is easy to see that $\text{rank}_+^*(V) =4 $ and $\text{rank}_+(V)=3$. This example also shows that your claimed inequality $\text{rank}_+^*(V) \leq n-1 $ does not always hold.

  • 1
    $\begingroup$ Thanks! It seems that this conflicts with the statement: "The non-negative rank is in general strictly greater than the largest number of columns such that no selected column can be written as a nonnegative linear combination of the other selected columns." (en.wikipedia.org/wiki/…). Perhaps strict inequality is not meant here (since 3 is the largest such number in your example). I am wondering now whether any bound can be given in terms of k? For instance, is 4 an upper bound for the case of k=3, or can rank_+^*(V) be arbitrarily large? $\endgroup$ May 16, 2018 at 11:41
  • $\begingroup$ Indeed, that claim in the wikipedia article appears to be fallacious. $\endgroup$
    – Tony Huynh
    May 17, 2018 at 13:01
  • $\begingroup$ Right, I found it suspect to begin with. I managed to find a counter-example to my last question, which shows that even for k=3 we can pick arbitrarily many non-negative vectors such that none is a conic combination of the others. For instance, one can take arbitrarily many distinct vectors on the boundary of a circular cone contained in the positive orthant. $\endgroup$ May 18, 2018 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.