If I define $\mathcal{A} = \{ xx^T : x \in \mathbb{R}^d, \| x \|_2 \leqslant 1 \}$, then (assuming I recall correctly) it is known that the convex hull of $\mathcal{A}$ is given by

\begin{align} \text{conv} (\mathcal{A}) = \{ M \in \text{Mat}_{d \times d} (\mathbf{R}): M = M^T, \| M \|_* = 1\}, \end{align}

where $\| \cdot \|_*$ is the nuclear norm.

Suppose I now define $\mathcal{A}_+ = \{ xx^T : x \in \mathbb{R}_+^d, \| x \|_2 \leqslant 1\}$, i.e. I restrict to taking outer products of nonnegative vectors $x$ with themselves.

My question is: Does there exist a similar characterisation of $\text{conv} (\mathcal{A}_+)$ ?

If context is useful: I'm interested in understanding and characterising when it is possible to write a symmetric probability distributions on two variables as a mixture of i.i.d. distributions, i.e. if $p(x,y) = p(y, x)$, when does there exist

  • some parameter space $\Theta$,
  • some family of distributions $\{ p(\cdot | \theta) \}_{\theta \in \Theta}$, and
  • some (prior) distribution $\pi$ such that

\begin{align} p(x, y) = \int_{\Theta} p(x|\theta) \, p(y|\theta) \, \pi(\theta) \, d\theta? \end{align}

I recognise that this has some links to de Finetti's theorem, but I'm not yet sure whether that link can be turned into an answer.


1 Answer 1


Your characterization of $\text{conv} (\mathcal{A})$ needs one additional restriction---that $M$ is positive semidefinite (the equivalence of these two sets follows fairly quickly from the spectral decomposition).

For $\text{conv} (\mathcal{A}_+)$, the convex hull is the exact same, but with the positive semidefiniteness requirement replaced by a complete positivity requirement. Since checking complete positivity is NP-hard, don't expect an easy way of determining membership in this convex hull.

  • $\begingroup$ Perfect - thank you! $\endgroup$
    – πr8
    May 6, 2019 at 9:41
  • $\begingroup$ To add to the completely positive part of the answer: while checking membership of the completely positive cone is NP-hard, you can use the set of doubly non-negative matrices (i.e. positive semidefinite and entry-wise non-negative matrices): this is a valid outer approximation which is semidefinitely representable, and agrees with the copositive cone for $n \leq 4$, see sciencedirect.com/science/article/pii/S002437950900281X. $\endgroup$
    – ryanseadub
    May 7, 2019 at 3:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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