1
$\begingroup$

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.

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

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.

$\endgroup$
  • $\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$ – lennart Jan 31 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$ – Mark L. Stone Jan 31 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.