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

$\endgroup$
2
  • 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$ Jun 27, 2015 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, 2015 at 13:16

1 Answer 1

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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