How to convert the matrix completion problem to the standard SDP form?

Question

Given the matrix completion problem defined below.

\begin{equation} \begin{array}{ll} \text{minimize }{X \in \mathbb{R}^{m \times n}} & \sum_{(i,j) \in \Omega} ( X_{ij} - Z_{ij} )^2 + \lambda \text{trace}(\sqrt[]{X^TX}) , \end{array} \end{equation} where, $Z$ is the observed matrix, $X$ is a low rank matrix that we want to find, $\Omega$ stores the row and column indices of the observed set. with tuning parameter $\lambda > 0$.

However it is a SDP problem and could be formulated as, \begin{equation*} \begin{array}{ll} \text{minimize }{x \in \mathbb{R}^p} & c^T x \\ \text{subject to } & x_1 A_1 + \cdots + x_p A_p \preceq B, \end{array} \end{equation*} for some fixed $c, B, A_i, \; i=1,\ldots,p$.

As the matrix completion problem utilizes the trace norm, F.Y.I, there are two ways of formulating the trace norm through optimization, \begin{equation} \begin{array}{ll} \max_{Y \in \mathbb{R}^{m \times n}} & \text{trace}(X^T Y) \\ \text{subject to} & \left[ \begin{array}{cc} I_m & Y \\ Y^T & I_n \end{array} \right] \succeq 0, \end{array} \label{eq:aa:primal} \end{equation} and its alternative dual, \begin{equation} \begin{array}{ll} \min_{\substack{W_{1} \in \mathbb{S}^{m}, \\ W_{2} \in \mathbb{S}^{n}}} & \text{trace}(W_{1}) + \text{trace}(W_{2}) \\ \text{subject to} & \left[ \begin{array}{cc} W_{1} & (1/2) X \\ (1/2) X^T & W_{2} \end{array} \right] \succeq 0, \end{array} \label{eq:aa:dual} \end{equation}

What I have achieved so far,

\begin{align*} \min_{X \in \mathbb{R}^{m \times n}} \|P_\Omega(X-Z)\|_F^2 + \lambda \| X \|_{\text{tr}} \\ = \text{trace}(\left(P_\Omega(X-Z)\right)^TP_\Omega(X-Z)) + \lambda \| X \|_{\text{tr}}\\ = \|\left(P_\Omega(X-Z)\right)^TP_\Omega(X-Z)\|_{tr} + \lambda \| X \|_{\text{tr}} \end{align*}

$$\| X \|_{\text{tr}} = \text{trace}(\sqrt[]{X^TX})$$

Answer 1

As indicated in the comments, this is the standard nuclear-norm optimization problem.

With a modelling layer such as YALMIP or CVX, you would simply do something along the lines of (here YALMIP in MATLAB)

X = sdpvar(m,n,'full');
E = Z - X;
optimize([],E(:)'*E(:) + lambda*norm(X,'nuclear'));

If you manually want to get the quadratic expression into a form supported by standard SDP solvers, you would, e.g., write it using a second-order cone constraint by replacing the quadratic term with a new variable $t$ and add an SOCP model of $||vec(E)||^2\leq t$. With $e = vec(E)$, this is equivalent to $\left|\left|\begin{bmatrix}2e\\1-t\end{bmatrix} \right|\right|\leq 1+t$

A horrible way to model it (from a performance view) would be as the SDP constraint $\begin{bmatrix}t& e^T \\e &I \end{bmatrix} \succeq 0.$

Your second expression is the nuclear norm, which can be written as the minimal value of $\text{tr}(A) + \text{trace}(B)$ where $\begin{bmatrix}A& X\\X^T &B\end{bmatrix} \succeq 0.$. Hence, simply introduce the two symmetric matrices $A$ and $B$ with associated constraint, and use the sum of traces instead of your square-root expression in the objective.