Is $f(x) = xx^T$ convex?

Question

Let $x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \in \mathbb{R}^n$

Let $f: \mathbb{R}^n \to \mathbb{R}^{n \times n} \quad f(x) = xx^T$ be its outer product

How to assess convexity of $f(x)$?

In other words, is $f(x) = xx^T$ convex on $\mathbb{R}^n$, if not, is it convex on $\mathbb{R}^n_{\geq 0}$...

Answer 1

Let us say that $f:\mathbb{R}^n\rightarrow M_n$ is convex if $(1-a)f(x)+af(y)-f((1-a)x+ay)$ is a positive semidefinite hermitian matrix for every $x,y\in \mathbb{R}^n$ and $0\leq a \leq1$.

Let us prove that $f(x)=xx^t$ is convex.

Notice that $(1-a)f(x)+af(y)-f((1-a)x+ay)=(x,y)A(x,y)^t$, where $A=\pmatrix{1-a & 0 \\ 0 & a}-\pmatrix{(1-a)^2 & (1-a)a \\ (1-a)a & a^2}$.

Consider $\frac{A}{(1-a)a}=\pmatrix{\frac{1}{a} & 0 \\ 0 & \frac{1}{1-a}}-\pmatrix{\frac{1-a}{a} & 1 \\ 1 & \frac{a}{1-a}}=\pmatrix{1 & -1 \\ -1 & 1}$.

Thus, $(1-a)f(x)+af(y)-f((1-a)x+ay)=(x,y)A(x,y)^t=$

$(1-a)a(x,y)\pmatrix{1 & -1 \\ -1 & 1}(x,y)^t$,

which is positive semidefinite, whenever $0\leq a\leq 1$.

Answer 2

OK, let's try a generic ansatz.

The definition of convexity is:

A function $f:V\to W$ is convex, of vor any $x,y\in V$ and any $\lambda\in [0,1]$ we have $$f(\lambda x+(1-\lambda)y) \le \lambda f(y) + (1-\lambda) f(y)$$

Now since we are working in linear spaces, all operations except the relation $\le$ on $W$ are already defined. However we can say if the definition has to make sense, $\le$ must fulfil some conditions:

• It must be a partial order.
• It must be compatible with addition, that is, for any $a,b,c\in W$ we have $$a \le b \iff a+c \le b+c.$$
• It must be compatible with scalar multiplication, that is, for any $a,b\in W$ and any $\lambda>0$, we have $$a \le b \iff \lambda a \le \lambda b.$$

Note that those conditions are already sufficient to prove that $\{x\in W|x\ge 0\}$ is a convex cone.

Further, we know that $W$ is actually a matrix space, so we have a multiplication of elements in $W$. I think a reasonable minimal condition for $\ge$ is:

• If $x=x^2$, then $x\ge 0$.

Theorem: Under these conditions, the function $f:x\mapsto xx^T$ is convex.

Proof:

We have \begin{aligned} X &:= \lambda f(x) + (1-\lambda) f(y) - f(\lambda x + (1-\lambda) y)\\ &= \lambda xx^T + (1-\lambda) yy^T - (\lambda x + (1-\lambda) y)(\lambda x + (1-\lambda) y)^T\\ &= \left(\lambda - \lambda^2\right) xx^T + \left((1-\lambda)-(1-\lambda)^2\right) yy^T - \lambda(1-\lambda) (xy^T + yx^T)\\ &= \lambda(1-\lambda)\left(xx^T + yy^T + xy^T +yx^T\right)\\ &= \lambda(1-\lambda)(x+y)(x+y)^T \end{aligned} Let's define $N=(x+y)^T(x+y)$ which clearly is a non-negative real number (it's the squared length of $x-y$). Further define $$P = \frac{1}{N}(x+y)(x+y)^T.$$ Then $$P^2 = \frac{1}{N^2}N(x+y)(x+y)^T = P.$$ Therefore from the definition above, $P\ge 0$. Since $N\ge 0$, it follows that $NP = (x+y)(x+y)^T\ge 0$, and since $\lambda(1-\lambda)\ge 0$ it follows that $X\ge 0$. But that's exactly the condition for convexity. $\square$