Compute lowest dimensional polytope from a given set of sign vectors

Question

Given a set of hyperplanes determined by the normal vectors $h_1,\dots,h_m \in \mathbf R^d$, its cell types (or sign vectors) are all vectors $t\in\{+,-\}^m$ for which there exists a vector $v\in\mathbf R^d$ so that $\langle v,h_i \rangle \neq 0$ and $t_i = \text{sign}( \langle v,h_i \rangle )$ holds for all $i$. Here, $\langle u,v\rangle$ denotes the inner product and $\text{sign}(x)$ denotes the sign ($+$ or $-$) of the non-zero real number $x$.

Question: What is the fastest known algorithm for the inverse operation? Given a set $t_1,\dots,t_n$ of cell types, we want to compute some set of hyperplanes in as few dimensions as possible, so that its cell types are a superset of $t_1,\dots,t_n$.

Answer 1

This is equivalent to computing the sign rank of a matrix, which is NP-hard as shown in this paper. So you cannot expect too efficient of an algorithm.