Is $f(H)=H^TH$ convex? $H$ is a $m\times n$ matrix

Question

I tried to prove $f(H)=H^TH$ convex, where $H$ is a matrix. We know when $h$ is a vector, then $f(h)=h^Th$ is convex. Can I prove it using the following equation? $[\theta H_1 + (1-\theta) H_2]^T[\theta H_1 + (1-\theta) H_2] \leq \theta H_1^TH_1 + (1-\theta)H_2^TH_2$

In the convex analysis textbook, the definition of a convex function is $f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta) f(y)$ where $f(x):R^n\rightarrow R$. But for my case, $f(H)=H^TH$ is $R^{m\times n} \rightarrow R^{n\times n}$. Please help to prove or disprove it? Thanks

What do you mean by "$H^TH$ is convex"? Do you mean $f(x)=x^TH^THx$ is convex? — Nitish, Mar 22 '14 at 21:33
Where did this problem come from? There's no explanation there of what is meant by a convex multi-valued function? — user7530, Mar 22 '14 at 21:47
Yes, but it is very hard to get the Hessian matrix of $f(H)$, right? — E.J., Mar 22 '14 at 21:48
How to get the Hessian matrix? I checked the some matrix derivative materials, but cannot find how to get the Hessian matrix for $H^TH$. I cannot even get the first derivative of $H^TH$. Please help:) — E.J., Mar 22 '14 at 21:53

score 2 · Accepted Answer · answered Mar 22 '14 at 22:14

For symmetric matrices $A$ and $B$, the inequality $A \leq B$ means that $B-A$ is positive semi-definitive:

$$((B-A)x, x) \geq 0 \quad \text{for any } x.$$

So we fix $x \in \Bbb{R}^{n}$ and check if

$$ (f(\theta H_{1} + (1-\theta)H_{2})x, x) \leq \theta ( f(H_{1}) x, x) + (1-\theta) (f(H_{2})x, x)$$

holds. That is, the convexity of $f$ is equivalent to the convexity of $H \mapsto (f(H)x, x)$ for any $x$. But since $(f(H)x, x) = (H^{T}Hx, x) = \| Hx \|^{2}$, it follows that

\begin{align*} (f(\theta H_{1} + (1-\theta)H_{2})x, x) &= \| \theta H_{1}x + (1-\theta)H_{2}x \|^{2} \\ {\scriptsize (\because \text{ triangle inequality})} \quad &\leq \left( \| \theta H_{1}x \| + \|(1-\theta)H_{2}x \| \right)^{2} \\ &= \left( \theta \| H_{1}x \| + (1-\theta) \|H_{2}x \| \right)^{2} \\ {\scriptsize (\because \text{ convexity of } t \mapsto t^{2})} \quad &\leq \theta \|H_{1}x\|^{2} + (1-\theta) \|H_{2}x\|^{2} \\ &= \theta (f(H_{1})x, x) + (1-\theta) (f(H_{2})x, x). \end{align*}

This proves the convexity of $f$ as desired.

Is $f(H)=H^TH$ convex? $H$ is a $m\times n$ matrix

1 Answers1