How calculate the trace norm via convex optimization?

Question

_{I am taking the convex optimization course by CMU (though I am not a CMU student), and got stuck on this problem.}

---

Formally, show that computing $\left \| X \right \|_{tr}$ can be expressed as the following convex optimization problem: $$\begin{array}{ll} \underset{{Y \in \mathbb{R}^{m \times n}}}{\text{maximize}} & \mbox{tr} \left( X^T Y \right)\\ \text{subject to} & \begin{pmatrix} I_{m} & Y \\ Y^{T} & I_{n} \end{pmatrix} \succeq 0\end{array}$$ where $I_{p}$ is the $p \times p$ identity matrix.

Any help would be appropriated.

Answer 1

What are the eigenvalues of $$\begin{pmatrix} I_{m} & Y \\ Y^{T} & I_{n} \end{pmatrix}?$$ Well, consider an eigenvector $[p, q].$ Then:

$$ p + Y q = \lambda p,$$ and

$$Y^{T}p + q = \lambda q.$$

We see that $$Y q = (\lambda - 1) p,$$ while $$Y^{T} p = (\lambda - 1) q.$$ Applying $Y$ to the second equation we see that $$YY^{T} p = (\lambda -1)^2.$$

So the block matrix is positive semidefinite if and only if $I\succeq YY^{T},$ which is exactly the condition in the question pointed out by Rodrigo.