# Size of a minimal non-negative conic basis

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

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.