I am studying the matrix Completion problem, as well as its SDP relaxation. However, I am having trouble deriving the final SDP form of the matrix completion problem. I will give some background, which mainly comes from (ZHA) below.
Nuclear Norm Minimization
The matrix completion rank minimization form can be relaxed as a nuclear norm minimization problem, as the nuclear norm is the convex envelope of the rank of a matrix (ZHA).
$$ \label{eq:nuc_min_raw} \underset{X \in \mathbf{R}^{m \times n}}{\text{minimize}} \quad ||X||_* \\ \text{subject to} \quad X_{i,j} = M_{i,j} \; \forall i, j \in \Omega $$
We can rewrite the nuclear norm using its dual norm, the operator norm
$$ \label{eq:op_norm} \underset{X \in \mathbf{R}^{m \times n}}{\text{min}} \quad \underset{Y \in \mathbf{R}^{m \times n}}{\text{max}} \langle X , Y \rangle \\ \text{subject to} \quad ||Y||_{\text{op}} \leq 1 \\ \text{and} \quad X_{i,j} = M_{i,j} \; \forall i, j \in \Omega $$
The operator norm constraint can be written as the Linear matrix inequality $\begin{pmatrix} I_m & Y \\ Y' & I_n \end{pmatrix} \succeq 0$. To understand this, consider the following equivalencies, and then using a schur complement like argument.
$$||Y||_{\text{op}} \leq 1 \iff \\ \frac{||Yx||}{||x||} \leq 1 \quad \forall x \iff \\ \langle Yx, Yx \rangle \; \leq \; \langle x, x \rangle \; \forall x \iff \\ \langle(YY^* - I)x, x \rangle \; \leq 0 \iff \\ (I - YY^*) \succeq 0 $$
Now we need to consider the dual of the resulting SDP:
$$ \label{eq:matcomp_sdp} \underset{X, Y \in \mathbf{R}^{m \times n}}{\text{max}} \quad \text{tr}( X Y ) \\ \text{subject to} \quad \begin{pmatrix} I_m & Y \\ Y' & I_n \end{pmatrix} \succeq 0 \\ \text{and} \quad X_{i,j} = M_{i,j} \; \forall i, j \in \Omega $$
Zhao claims the dual of this SDP is
$$ \label{eq:matcomp_dual} \underset{W_1, W_2 \in \mathbf{R}^{m \times n}}{\text{min}} \quad \frac{1}{2} (\text{tr}( W_1 ) + \text{tr}( W_2 )) \\ \text{subject to} \quad \begin{pmatrix} W_1 & X \\ X' & W_2 \end{pmatrix} \succeq 0 \\ \text{and} \quad X_{i,j} = M_{i,j} \; \forall i, j \in \Omega $$
How is this dual problem derived? What am I missing? It would be greatly appreciate if you could either reference a derivation, or explain the dual variables that are introduced, etc.
[ZHA]: Zhao, Yun-Bin, [An approximation theory of matrix rank minimization and its application to quadratic equations] (http://dx.doi.org/10.1016/j.laa.2012.02.021), Linear Algebra Appl. 437, No. 1, 77-93 (2012). ZBL1242.65086.
