Algorithm to compute Matrix Sign Rank? The (generalised) sign-rank of a (generalised) sign pattern $S\in \{+,-,0\}^{n\times m}$
is the minimum rank of all matrices with the same sign pattern, i.e.
$$
\min\left\{\operatorname{rank}(M)\ :\ M\in \mathbf{R}^{n\times m} \text{ and } \operatorname{sign}(M_{i,j}) = S_{i,j}\text{ for all }i,j\right\}
$$
This problem is known to be as hard as the existential theory of reals. Has there been any advances in computing this value, either exactly, or an approximation algorithm, or even a heuristic that is good in practice?
 A: Given positive integers $m$ and $n$, and sets $\mathcal P, \mathcal Z, \mathcal N$ that partition the set 
$$\{1, 2, \dots, m\} \times \{1, 2, \dots, n\}$$
and indicate which entries of the matrix are positive, zero or negative, respectively, we have the following constrained rank-minimization problem
$$\begin{array}{ll} \text{minimize} & \mbox{rank} (\mathrm X)\\ \text{subject to} & \mathrm X_{ij} > 0 \quad \forall (i,j) \in \mathcal P\\ & \mathrm X_{ij} = 0 \quad \forall (i,j) \in \mathcal Z\\ & \mathrm X_{ij} < 0 \quad \forall (i,j) \in \mathcal N\end{array}$$
which is non-convex, unfortunately. However, a convex relaxation of the rank-minimization problem is to minimize the nuclear norm of $\mathrm X$, which is denoted by $\| \mathrm X \|_*$. We introduce $0 < \epsilon \ll 1$ so that we have non-strict inequalities. Hence,
$$\boxed{\begin{array}{ll} \text{minimize} & \| \mathrm X \|_*\\ \text{subject to} & \mathrm X_{ij} \geq \epsilon \quad \forall (i,j) \in \mathcal P\\ & \mathrm X_{ij} = 0 \quad \forall (i,j) \in \mathcal Z\\ & \mathrm X_{ij} \leq -\epsilon \,\,\, \forall (i,j) \in \mathcal N\end{array}}$$
The $\| \cdot \|_*$-minimization problem can be formulated as a semidefinite program (SDP) [MG14] in matrices $\mathrm X \in \mathbb R^{m \times n}$, $\mathrm W_1 \in \mathbb R^{m \times m}$ and $\mathrm W_2 \in \mathbb R^{n \times n}$
$$\begin{array}{ll} \text{minimize} & \frac 12 \mbox{tr} (\mathrm W_1) + \frac 12 \mbox{tr} (\mathrm W_2)\\ \text{subject to} & \begin{bmatrix} \mathrm W_1 & \mathrm X\\ \mathrm X^{\top} & \mathrm W_2\end{bmatrix} \succeq \mathrm O_{m+n}\\ & \mathrm X_{ij} \geq \epsilon \quad \forall (i,j) \in \mathcal P\\ & \mathrm X_{ij} = 0 \quad \forall (i,j) \in \mathcal Z\\ & \mathrm X_{ij} \leq -\epsilon \,\,\, \forall (i,j) \in \mathcal N\end{array}$$

[MG14] Michael Grant, Derivative of the nuclear norm with respect to its argument, Mathematics Stack Exchange, April 2014.
