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](https://zbmath.org/?q=an:1242.65086).



Matrix Completion SDP Relaxation and Duality
The derivation of this dual is provided in example 8.8 "Sum of singular values revisited" of [section 8.6 "Semidefinite duality and LMIs" of Mosek Modeling Cookbook 3.2.1](https://docs.mosek.com/modeling-cookbook/duality.html#semidefinite-duality-and-lmis).


