Solving a sign-constrained linear system

Question

Let ${\bf A}\in\mathbb{R}^{D\times D}$ and ${\bf b}\in [-1, 0, 1]^D$ be a binary vector. I am trying to solve:

$$\operatorname{sign}\left({\bf A}^\top {\bf x}\right) = {\bf b}.$$

What's the best approach to solving this problem? Any hints are appreciated.

Answer 1

As $\text{sgn}(b)=b$, the solution of

$$Ax=b$$ is automatically such that $$\text{sgn}(Ax)=b.$$

Answer 2

Let $i$ be the set of rows for which $b<0$, $j$ be the set of rows for which $b=0$ and $k$ be the set of rows for which $b>0$. You want to find an $x$ such that

$$A_i x \leq 1, A_j x = 0, A_k x \geq 1$$

The value 1 is chosen arbitrarily to obtain a closed set. It does not restrict the solution space, since if $A_i x < 0$, you can always scale $x$ such that $A_i x \leq 1$.

You can find an $x$ by solving the following linear optimization problem: $$\min_{x}\{ 0 : A_i x \leq 1, A_j x = 0, A_k x \geq 1\},$$ for which many algorithms are available.