11
$\begingroup$

Consider the Stiefel manifold

$$\mathrm{St}(n,k) :=\{X \in \mathbb{R}^{n\times k} : X^TX = I_k\},$$

where $I_k$ is the $k$-dimensional identity matrix. It is well known that

$$\mathrm{conv} \left( \mathrm{St}(n,k) \right) = \{X \in \mathbb{R}^{n\times k} : \|X\|_2 \leq 1\}$$

where $\|\cdot\|_2 $ is induced $2$-norm.

Question: Is there a characterization for the convex hull of the Stiefel manifold with non-negativity constraints:

$$\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+)$$

where $\mathbb{R}^{n \times k}_+$ is the set of all $n \times k$ matrices with non-negative elements?

$\endgroup$
  • 1
    $\begingroup$ In the special case k=1 it seems to be the intersection of the unit sphere with the halfspace \sum_i x_i>=1. $\endgroup$ – user35593 Apr 4 '18 at 14:07
  • $\begingroup$ In the special case k=n, the Stiefel manifold with non-negativity constraints is equal to the set of all permutation matrices, and it is known that the convex hull of permutation matrices yields exactly the stochastic matrices. $\endgroup$ – Mahdi Apr 6 '18 at 11:02
  • 1
    $\begingroup$ @ Mahdi The convex hull of permutation matrices yields exactly the doubly stochastic matrices, not the stochastic matrices. $\endgroup$ – Mark L. Stone Jun 5 '18 at 1:19
3
$\begingroup$

Here we consider the case $k=1$. Then $\text{St}(n,1)=\{x\in\mathbb{R}^n:x^Tx=1\}$ represents the unit sphere in $\mathbb{R}^n$. It follows $$\text{St}(n,1)\cap\mathbb{R}^n_+=\{x\in\mathbb{R}^n_+:x^Tx=1\}$$ represents the part of the unit circle in the first quadrant of $\mathbb{R}^n$. Let $a^T:=(1,1,...,1)$ define $$V:=\{x\in\mathbb{R}^n_+: x^Ta\geqslant 1\}$$ Hence the set $V$ represents whatever is in the first quadrant not below the simplex. First we show that $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)=\text{convSt}(n,1)\cap V$$ By definition $\text{convSt}(n,1)=\{x\in\mathbb{R}^n:x^Tx\leqslant 1\}$ is a convex set (the closed unit ball) so is the set $V$. Hence $\text{convSt}(n,1)\cap V$ is a convex set because it is the intersection of two such sets. Moreover $\text{St}(n,1)\cap\mathbb{R}^n_+\subseteq \text{convSt}(n,1)\cap V$ since $x\in\text{St}(n,1)\cap\mathbb{R}^n_+$ would imply $x^Tx=1$ and $1\geqslant x_m\geqslant 0$ for all $m=1,2,...,n$ which in turn yields $$1=x^Tx=x_1^2+...x^2_n\leqslant x_1+...+x_n=x^Ta$$ and hence $x\in \text{convSt}(n,1)\cap V$. On the other hand $\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)$ is the smallest convex set which includes $\text{St}(n,1)\cap\mathbb{R}^n_+$ thus we get $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)\subseteq \text{convSt}(n,1)\cap V$$ By definition of a convex hull we have $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)\\=\{y\in\mathbb{R}^n_+: y=\sum_k\lambda_kx_k,\hspace{0.1cm}\lambda_k\geqslant 0, \sum_k\lambda_k=1, x_k\in \text{St}(n,1)\cap\mathbb{R}^n_+\}$$ From this definition it follows that the simplex $$V_0:=\{x\in\mathbb{R}^n_+: x^Ta= 1\}\subseteq \text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)$$ as well as any line segment joining any two points in $\text{St}(n,1)\cap\mathbb{R}^n_+$. Therefore by construction we get the equality $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)= \text{convSt}(n,1)\cap V$$ So for the case $k=1$ we get the characterization $$\text{conv}(\text{St}(n,1)\cap\mathbb{R}^n_+)=\{x\in\mathbb{R}^n_+:x^Tx\leqslant 1, x_1+....+x_n\geqslant 1\}$$ For $k>1$ one needs to find an appropriate definition for a simplex. The above idea should work.

$\endgroup$
  • $\begingroup$ Thanks, but k=1 is very special case of the problem. $\endgroup$ – Mahdi Apr 6 '18 at 7:03
2
$\begingroup$

@Arian has supplied the solution for $k = 1$. It is a known result that for $k = n$, the desired convex hull is the set of all $n$ by $n$ doubly stochastic matrices.

I offer this conjecture for the solution for general $k$, as the following extension of the answer by @Arian .The remainder of this post is conjecture:

$$\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+) = \{X\in\mathbb{R}^{n\times k}_+:\|X\|_2 \le 1, \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$$

$\{X\in\mathbb{R}^{n\times k}_+:\|X\|_2 \le 1, \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$ implies $\|X\|_2 \ge \sqrt{\frac{k}{n}}$ and $\sqrt{n-k+1} \ge \Sigma_{j=1}^n X_{ij}, \forall i$.

So putting it altogether, we can state $\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+) =$ $$\{X\in\mathbb{R}^{n\times k}_+: \sqrt{\frac{k}{n}} \le \|X\|_2 \le 1, \sqrt{n-k+1} \ge \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$$

When $k = n$, $\|X\|_2 = 1, \Sigma_{j=1}^n X_{ij} = 1\ \forall i$ must hold, and this reduces exactly to the set of all $n$ by $n$ doubly stochastic matrices, thereby matching the known result for square $X$.

$\endgroup$
  • $\begingroup$ Thanks, Mark. that conjecture can be a constructive progress in solving the problem. $\endgroup$ – Mahdi Jun 9 '18 at 20:15
  • $\begingroup$ $$\mathrm{conv}(\mathrm{St}(n,k) \cap \mathbb{R}^{n\times k}_+) = \{X\in\mathbb{R}^{n\times k}_+:\|X\|_2 \le 1, \Sigma_{j=1}^n X_{ij} \ge 1\ \forall i\}$$ is conjecture (low confidence). However, I am very confident based on semidefinite optimization results that the RHS of that implies all the following claims made in the post., even though I haven't proved those claims. I can state quite confidently that my conjectured convex hull is convex - do you have a way to try to test whether it is correct for some 1 < k < n cases? Maybe @Arian can give it a try? $\endgroup$ – Mark L. Stone Jun 9 '18 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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