3
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 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$
    – Rajesh Jayaram
    Commented May 16, 2018 at 11:41
  • $\begingroup$ Indeed, that claim in the wikipedia article appears to be fallacious. $\endgroup$
    – Tony Huynh
    Commented 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$
    – Rajesh Jayaram
    Commented May 18, 2018 at 18:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .