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