Recovery of a Sparse Integer Solution to an Underdetermined System of
  Linear Equations
  We consider a system of m linear equations in n variables Ax=b where A is a
given m x n matrix and b is a given m-vector known to be equal to Ax' for some
unknown solution x' that is integer and k-sparse: x' in {0,1}^n and exactly k
entries of x' are 1. We give necessary and sufficient conditions for recovering
the solution x exactly using an LP relaxation that minimizes l1 norm of x. When
A is drawn from a distribution that has exchangeable columns, we show an
interesting connection between the recovery probability and a well known
problem in geometry, namely the k-set problem. To the best of our knowledge,
this connection appears to be new in the compressive sensing literature. We
empirically show that for large n if the elements of A are drawn i.i.d. from
the normal distribution then the performance of the recovery LP exhibits a
phase transition, i.e., for each k there exists a value m' of m such that the
recovery always succeeds if m > m' and always fails if m < m'. Using the
empirical data we conjecture that m' = nH(k/n)/2 where H(x) = -(x)log_2(x) -
(1-x)log_2(1-x) is the binary entropy function.
