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



Size of a minimal non-negative conic basis
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. 


