# How to transform this into a standard SDP problem?

How to transform this problem, $$\min_{x_1, x_2} x_1 + x_2$$

$$\text{subject to} \\ \|P_\Omega(X-Z)\|_{F}^2 \leq x_1\\ \lambda\| X \|_{\text{tr}} \leq x_2$$

to the standard SDP problem, \begin{equation*} \begin{array}{ll} \min_{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*}

Given that solving $\| X \|_{\text{tr}}$ is equivalent to the optimization problem defined as, $$\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$$

I know that $\text{trace}(X^T Y) = \langle X,Y\rangle$, so solving $\| X \|_{\text{tr}}$, so it actually looks very much like the conic problem, but how to transform that into standard SDP, where $c$ and $x$ are vectors?

• Have you taken a look at Maryam Fazel's PhD thesis? Matrix Rank Minimization with Applications (pdf)? – Rodrigo de Azevedo Nov 3 '16 at 18:40
• don't you have constraints? I mean the minimum of every norm is $0$... – user251257 Nov 3 '16 at 18:41
• @RodrigodeAzevedo I didn't have chance to look at it yet. Could you tell me which part might be important for this proof? – good2know Nov 3 '16 at 18:49
• @user251257 Actually I have $\|\left(P_\Omega(X-Z)\right)^TP_\Omega(X-Z)\|_{tr} \leq \epsilon$. – good2know Nov 3 '16 at 18:53
• @v-2 you should include it in your question. – user251257 Nov 3 '16 at 18:54