Linear equations with absolute values

The problem is NP-hard over any field not of characteristic 2. We show this by reduction from an NP-complete NAE-3-SAT problem of checking satisfiability of a boolean formula $\land_{i} \mathrm{NAE}(z_{i, 1}, z_{i, 2}, z_{i, 3})$, where $z_{i, j}$ are variables $x_{\cdot}$ or their negations, and $\mathrm{NAE}(\ldots)$ is true iff not all of its arguments have the same value.

The reduction is as follows: introduce variables $x_i$ subject to $x_i = \pm 1$, where we interpret values $1$ and $-1$ as $\top$ and $\bot$, respectively. For each $\mathrm{NAE}(\ldots)$ we impose a condition $s_a x_a + s_b x_b + s_c x_c = \pm 1$, where $x_a, x_b, x_c$ are variables in arguments of NAE, and each of the signs $s_a, s_b, s_c$ is $\pm 1$ depending on whether the corresponding variable was taken with negation. It is easy to check that the imposed conditions are equivalent to the original formula, hence the reduction is proper (and of course, polynomial). The reduction works both for machines with precise and approximate real registers (as long as it handles numbers with $O(1 / n)$ relative precision). It also works for any field $F$ not of characteristic 2 if we take $1 \in F$ to be any element of order at least 3, or zero.

In fields of characteristic 2 the given equations (treated as $a_i \cdot x = \pm b_i$) are equivalent to $a_i x = b_i$, which can be solved with any standard LES solving algorithm (for instance, Gaussian elimination).

If you square your equations to get $|\langle x,a_i\rangle|^2 = b_i^2$ your problem is the so-called phase retrieval problem (which was motivated by the problem of recovering a function (up to global phase) from the magnitude of its Fourier transform). There are several results here (besides the general NP-hardness). I would like to point out some blog posts by Dustin Mixon, e.g.:

• Saving phase: Injectivity and stability for phase retrieval
• Phase retrieval: Stability and recovery guarantees
• Phase retrieval from very few measurements

In these posts and the reference given there, Dustin discussion issues of solvabilty and indeed, the squared system is often solvable even if not quadratically overdetermined. There are also some algorithms around, e.g DOLPHin, PhaseMax or PhaseLift.