Nuclear norm (convex) minimization with complex-valued matrices?

Question

Rank minimization subject to some constraints can be accomplished in many cases through the nuclear norm. \begin{align} \min_{X}.\,\,& \left\|X\right\|_* \\ \text{s.t. }& X\in\mathcal{C} \end{align} where $\mathcal{C}$ is some convex set and $X$ is a Real matrix. According to Recht et al., this can be accomplished by the Semidefinite Program: \begin{align} \min_{X}.\,\,& \operatorname{trace}\frac{1}{2}\left(W_1+W_2\right) \\ \text{s.t. }& X\in\mathcal{C} \\ & \begin{bmatrix} W_1 & X \\ X^T & W_2 \end{bmatrix} \geq0. \end{align}

My question is there a SDP formulation for complex-valued matrices???

Thank you

Answer 1

Yes, the same approach can be used for complex matrices, with the constraint becoming

$\left[ \begin{array}{rr} W_{1} & X \\ X^{H} & W_{2} \\ \end{array} \right] \succeq 0 $

Here, the constraint says that the matrix must be Hermitian (rather than symmetric) and positive definite.

However, not all SDP solvers directly support complex matrices. You can reformulate any SDP involving complex Hermitian matrices into an SDP with real symmetric matrices. A constraint of the form

$Z \succeq 0$

where $Z$ is complex and Hermitian becomes

$\left[\begin{array}{rr} \mbox{real}(Z) & -\mbox{imag}(Z) \\ \mbox{imag}(Z) & \mbox{real(Z)} \\ \end{array} \right] \succeq 0 $

The resulting problem has a matrix variable of size $2n$ by $2n$ but this only doubles the required storage, since each complex number in $Z$ requires twice as much storage as each real in the reformulation.