5
$\begingroup$

The definition: cone of completely positive matrices $$ \mathcal{C}=\left\{ \sum_{i=1}^kx_ix_i^T : \text{$x_i\in\mathbb{R}^n_+$ for $i=1,2,\ldots,k$} \right\}. $$

I just don't know how to check whether a matrix belongs to $\mathcal C$. To be more specific, is the following matrix completely positive?

$$\begin{pmatrix}8 & 2& 4+2\sqrt{2}\\ 2&2+\sqrt{2}&2+\sqrt{2}\\ 4+2\sqrt{2}& 2+\sqrt{2} &4+2\sqrt{2}\end{pmatrix}$$

Any thoughts or reference? Thanks very much.

$\endgroup$
  • 1
    $\begingroup$ Your "completely positive" matrices are just symmetric positive matrices. Any textbook will tell you how to check that a given matrix has that property. $\endgroup$ – abx Apr 8 '14 at 20:05
  • 2
    $\begingroup$ For abx: the membership problem on the completely positive cone is NP-hard (optimization-online.org/DB_FILE/2011/05/3041.pdf). $\endgroup$ – Cristóbal Guzmán Apr 8 '14 at 20:17
  • 2
    $\begingroup$ @abx The $x_i$ are required to be $\geq 0$; this is more restrictive than being positive definite. (I was confused by this for quite a while as well.) $\endgroup$ – David E Speyer Apr 9 '14 at 0:26
  • $\begingroup$ I suspect the closers misread this question as the far easier one abx understood; I'm voting to reopen. $\endgroup$ – David E Speyer Apr 9 '14 at 0:27
  • 1
    $\begingroup$ Oops! My mistake, I indeed missed the ${}_+$ on $\mathbb{R}^n$. I apologize, and I vote to reopen. $\endgroup$ – abx Apr 9 '14 at 5:20
10
$\begingroup$

As mentioned by Robert Bryant, in the $n = 3$ case, checking that the matrix is positive semidefinite and has all entries $\geq 0$ is both necessary and sufficient. In fact, the same is true when $n = 4$, but this is only a necessary (not sufficient) test for complete positivity when $n \geq 5$ (see "L. J. Gray and D. G. Wilson. Nonnegative Factorization of Positive Semidefinite Nonnegative Matrices. Linear Algebra Appl., 31:119-127, 1980", for example).

When $n \geq 5$, things get harder (NP-hard), but there are still some things that you can do, at least for small $n$. The usual approach is to approximate the set of completely positive matrices from the outside by other convex cones of matrices:

$\mathcal{K}_0 \supset \mathcal{K}_1 \supset \mathcal{K}_2 \supset\cdots \supset \mathcal{C},$

where $\mathcal{C}$ is the set of completely positive matrices, $\mathcal{K}_0$ is the set of "doubly-nonnegative matrices" (i.e., positive semidefinite matrices that also have all entries $\geq 0$, which were mentioned earlier), and $\mathcal{K}_i$ for $i \geq 1$ are better and better approximations of $\mathcal{C}$ (and in particular, $\lim_{i \rightarrow \infty} \mathcal{K}_i = \mathcal{C}$). Furthermore, the $\mathcal{K}_i$'s are defined in such a way that determining whether or not a matrix is a member of $\mathcal{K}_i$ can be phrased as a semidefinite program, and is thus computationally tractable for small $n$ and small $i$ (the semidefinite program takes more and more effort to solve as $i$ increases). I'm having trouble tracking down the original paper that discusses how the $\mathcal{K}_i$'s are defined, but "J. Povh and F. Rendl. Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optimization, 9:231-241, 2009" goes over these things in Section 3.

The upshot of this is that, in practice, we can determine when a matrix is not completely positive, by showing that is it not a member of $\mathcal{K}_i$ for some $i$. However, I am not aware of any methods for proving that a matrix is completely positive that work very well in practice.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! I had more-or-less convinced myself that $n=4$ worked the same way, but didn't have time to check it completely, and it was clear that the simple nonnegativity of entries wouldn't work for sufficiently large $n$. I'm glad to know that the $n=5$ case is the one where it actually does break down. $\endgroup$ – Robert Bryant Apr 9 '14 at 23:43
6
$\begingroup$

At least for $3$-by-$3$ matrices, the test for complete positivity of a matrix $A$ is not hard. Basically, you need that $A$ be positive-semi-definite and that the off-diagonal entries be non-negative. (I don't think this works for $n$-by-$n$ when $n>3$, though.)

Note: When I was writing the above, I was taking $\mathbb{R}^n_+$ to mean the closed principal $n$-orthant, i.e., the vectors in $\mathbb{R}^n$ with nonnegative entries. However, if you want $\mathbb{R}^n_+$ to be the interior of this orthant, i.e., the vectors with strictly positive entries, then you need (when $n=3$), in addition to $A$ being positive semi-definite, that all of the entries of $A$ are actually positive.

In the case of your particular matrix above, yes, it is completely positive: The entries $a_{ij}=a_{ji}$ are of the form $a_{ij} = v_i\cdot v_j$ where the three $v_i\in\mathbb{R}^3$ are linearly dependent and the greatest angle between any two is less than $\frac12\pi$, so the three vectors $v_i$ can be rotated simultaneously into the principal octant of $\mathbb{R}^3$, and this suffices.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @RobertBrayant I think for $n=3$ the first paragraph of your answer is not a sufficient condition. a more necessary conition is $tr(A)\geq offtr(A)$. $\endgroup$ – Ali Taghavi Apr 9 '14 at 17:06
  • $\begingroup$ @AliTaghavi: Your inequality is a consequence of the inequalities needed for $A$ to be positive semi-definite: When $A$ is positive semi-definite, we can write $a_{ij} = v_i\cdot v_j$ for three vectors $v_i$. Let $r_i = \sqrt{a_{ii}}\ge0$ and note that $a_{11}+a_{22}+a_{33}={r_1}^2+{r_2}^2+{r_3}^2\ge r_1r_2+r_2r_3+r_3r_1$ since the $r_i$ are nonnegative and that $r_1r_2+r_2r_3+r_3r_1\ge a_{12}+a_{23}+a_{31}$ by Cauchy-Schwartz. $\endgroup$ – Robert Bryant Apr 9 '14 at 18:39
0
$\begingroup$

For general CP factorization of 3x3 matrices, you may consult pp.8-9 in

http://www.optimization-online.org/DB_HTML/2009/08/2381.html

| cite | improve this answer | |
$\endgroup$

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.