How to Convert Matrix Completion Problem to Standard SDP Form

convex optimizationconvex-analysismatrix completionnuclear normsemidefinite-programming

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})$$

Best Answer

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.

Related Question