11
$\begingroup$

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$.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ BTW it is not clear what is the inner product of a hyperplane and a vector. Did you intend $h_i$ to be the normal vector of the $i$-th hyperplane? $\endgroup$ – Sasho Nikolov Jun 27 '15 at 0:20
  • $\begingroup$ Yes, they're supposed to be the normal vectors - I stated formally exactly what I'm looking for. $\endgroup$ – Holger Jun 28 '15 at 13:16
5
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.