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.

  • $\begingroup$ What is $\mathbf{tr}(X,Y)$? $\endgroup$
    – Dirk
    Jan 29, 2020 at 12:27
  • $\begingroup$ sorry that should just be $\textbf{tr}(XY)$ $\endgroup$ Jan 29, 2020 at 15:48

1 Answer 1


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.

  • $\begingroup$ Thanks for the reference, however I am still having trouble deriving the relationship. Would you mind explaining how they "go back from the dual" and what variables are introduced? $\endgroup$ Jan 31, 2020 at 10:29
  • $\begingroup$ Read from the beginning of section 8.6 so that you understand how to take the dual of a semidefinite program (LMI problem). It is then a straightforward matter. $\endgroup$ Jan 31, 2020 at 13:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .