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).

up vote 2 down vote accepted

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
    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? – Rajesh Jayaram May 16 at 11:41
  • Indeed, that claim in the wikipedia article appears to be fallacious. – Tony Huynh May 17 at 13:01
  • 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. – Rajesh Jayaram May 18 at 18:43

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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