# Minimize $\|Ax-b\|$ where $x$ is a binary vector

For a software project I'm involved on, I have a situation where I have a large vector that is the sum of some smaller vectors. I know all the possible small vectors, and I know that no two of them start at the same place. Therefore, I think I can solve the problem (determine which small vectors are in the large one) if I put each small vector into each possible position as columns in a large matrix $A$. If $b$ is the signal (a particular sum of parts), I would need to solve this: $$\min \|x\|_1 \text{ where } Ax = b \text{ and } x_i\in\{0,1\} \text{ for all } i.$$ From what I've read from Stanford, I should be able to get the solution that minimizes the sum of x using $A^T (AA^T)^{−1}b$. Indeed that solution seems to have, um, hills where I should have a 1. However, it is not what I would call a sparse solution. And there is no way for me to threshold the data to get the right answer as it varies too much. Any ideas on how to solve this more effectively?

Here's an example:

Suppose I have two small vectors: $[3, 4, 5]$ and $[2, -1, -2]$. Suppose that the first starts at position 0 and 3 and the second starts at position 2 in the final signal. You would then have this sum/signal/$b$: $[3, 4, 7, 2, 2, 5]$. The $A$ in this scenario would be drawn up like this:

$$\left[\begin{array}{rrrrrr} 3 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ 4 & 3 & 0 & 0 &-1 & 2 & 0 & 0 \\ 5 & 4 & 3 & 0 &-2 &-1 & 2 & 0 \\ 0 & 5 & 4 & 3 & 0 &-2 &-1 & 2 \\ 0 & 0 & 5 & 4 & 0 & 0 &-2 &-1 \\ 0 & 0 & 0 & 5 & 0 & 0 & 0 &-2 \end{array}\right]$$

I want to perform some kind of solve operation to return me this $x$: $[1, 0, 0, 1, 0, 0, 1, 0]$.

-
What do you mean by "no two of them start at the same place"? If you mean each vector looks like $(0,\dots,0,1,\dots)$, and no two have the same number of zeros before that first 1, then you can just order your vectors lexicographically, and match them up to your target vector, one component at a time. But maybe you mean something else. – Gerry Myerson Oct 6 '13 at 4:13
There's no closed form solution for the problem of minimizing $\|x\|_1$ subject to $Ax = b, x_i \in \{0,1\} \, \forall i$. You could try relaxing the second constraint and minimizing $\|x\|_1$ subject to $Ax = b, 0 \leq x_i \leq 1 \, \forall i$. This is a convex problem and could be solved with CVX in Matlab or with some other software. – littleO Oct 6 '13 at 4:23
The question title and question body don't match. What you want to minimise is not $\|Ax-b\|$ --- $\|Ax-b\|$ is required to be zero in your constraint! You are minimising the 1-norm of $x$ subject to the constraint $Ax=b$. – user1551 Oct 6 '13 at 7:09
@GerryMyerson, I have added an example that should help answer your question. – Brannon Oct 6 '13 at 18:27
Looking at your example, it's almost (but not quite) as if $Ax = A_1 x_1 + A_2 x_2$, where $x = \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ (using block notation), and $A_1$ convolves with the kernel $\begin{bmatrix} 3 & 4 & 5\end{bmatrix}^T$ and $A_2$ convolves with the kernel $\begin{bmatrix} 2 & -1 & -2 \end{bmatrix}^T$. I wonder if it might be helpful to look at it that way. – littleO Oct 6 '13 at 23:49