Closest corner of hypercube to another on the positive side of an affine transform

Question

Consider the affine transform $f(x) = a \cdot x + b$, where $x \in \mathbb{R}^n$, $a \in \mathbb{R}^n$, and $b \in \mathbb{R}$. Say we are given some corner of the hypercube $c^{(0)} \in \{-1, 1\}^n$. Find a corner $c \in \{-1, 1\}^n$ that minimizes the hamming distance between $c^{(0)}$ and $c$ subject to the constraint $f(c) > 0$. If no such $c$ exists, show it does not exist.

Answer 1

First, we observe that

$$a \cdot x + b > 0 \Rightarrow a \cdot x > -b$$

When minimizing hamming distance, each bit flip incurs a cost of $1$ in distance. Thus we want to minimize the number of bit flips required to make the above inequality true.

Note that the $c \in \{-1, 1\}^n$ that makes the $a \cdot c$ the maximally positive is:

$$c = \text{sign}(a)$$

To see this, consider

$$a \cdot \text{sign}(a) = \sum_{i=1}^n|a_i|$$

Flipping bit $i$ in $\text{sign}(a)$ would make $|a_i|$ turn into $-|a_i|$ in the above sum, thus making the summation smaller. This property gives us our test to see if a $c \in \{-1, 1\}^n$ exists such that $f(c) > 0$. Simply test $c = \text{sign}(a)$, and if $f(c) \leq 0$, then we know no such $c$ exists that satisfies our constraint.

From here on out, assume a $c$ exists such that $f(c) > 0$. Since we are minimizing Hamming distance, we want to flip the fewest number of bits of $c^{(0)}$ that makes $a \cdot c$ larger than $-b$. Here, I present a greedy algorithm to do so:

1. Initialize $c \leftarrow c^{(0)}$. If $c^{(0)}$ is a solution, we're done, so return $c^{(0)}$.
2. Find the largest $|a_i|$ such that $c_i \neq \text{sign}(a_i)$.
3. Flip the sign of $c_i$. Use this as our new $c$.
4. Evaluate $a \cdot c$. If $a \cdot c > -b$, then we're done and return $c$. Otherwise, repeat the algorithm using $c$ as $c^{(0)}$.

Proof of Algorithm's Correctness: To show the algorithm is guaranteed to terminate, remember we already verified that $c = \text{sign}(a)$ is a solution. As we continue to flip bits of $c$ that differ from $\text{sign}(a)$, in $O(n)$ steps $c$ will be $\text{sign}(a)$. Thus, the algorithm will (in the worst case) terminate to $c=\text{sign}(a)$ in $O(n)$ steps.

Now we show that $c$ is the solution that minimizes the Hamming distance with $c^{(0)}$. Consider the following two cases:

Case 1: $c^{(0)}$ is a valid solution. Note that in the special case where $c^{(0)}$ is a valid solution it has a Hamming distance of $0$ to itself (thus minimizing the Hamming distance). When $c^{(0)}$ is a valid solution, our algorithm correctly returns it in the first step.

Case 2: $c^{(0)}$ is not a valid solution. In this case, there exists some other $c$ that is a valid solution. Since we considered the worst case where the only such $c$ is $\text{sign}(a)$ already, we'll consider the more general case here: there is at least one $c \in \{-1, 1\}^n$ that satisfies our constraints, and we want to choose the one that minimizes the Hamming distance. Consider some other optimal algorithm that flipped a bit $i'$ at iteration $j$ different from the bit $i \neq i'$ that our greedy algorithm flipped ($i, i', j \in \{1, \dots, n\}$). Note that we chose $i$ to be the bit with the largest $|a_i|$ such that $c_i \neq sgn(a_i)$. Thus, by flipping bit $i$, we are increasing $a \cdot c$ by $2|a_i|$. In general, when we flip a bit $k \in \{1,\dots,n\}$ of $c$, there are two cases:

1. $c_k \neq \text{sign}(a_k) \Rightarrow$ flipping bit $k$ increases $a \cdot c$ by $2|a_k|$
2. $c_k = \text{sign}(a_k) \Rightarrow$ flipping bit $k$ decreases $a \cdot c$ by $2|a_k|$

Thus the other optimal algorithm will either increase $a \cdot c$ by less than or equal to our greedy algorithm or it will decrease $a \cdot c$ (pushing us further from our goal of finding $c$ such that $a \cdot c > -b$). Therefore, at each step (and correspondingly each increment of Hamming distance from $c^{(0)}$) the greedy algorithm will be at least as close as the other optimal algorithm to increasing $a \cdot c$ to greater than $-b$. $$\tag*{$\blacksquare$}$$