Introduction
Recovering a sparse solution from an underdetermined system of linear equations ($Ax = b$ with $m < n$) is a fundamental challenge in signal processing and data science. While standard compressed sensing focuses on continuous sparse signals, many practical applications involve discrete, binary constraints. For instance, in smart grid phase identification, a household is either connected to a specific power phase or not, leading to a $k$-sparse binary solution vector $x \in \{0, 1\}^n$. This paper explores the conditions under which a specific linear programming (LP) relaxation can efficiently and perfectly recover such binary signals.
Methods and Theoretical Framework
To circumvent the NP-hardness of combinatorial search, the authors employ an LP relaxation that minimizes the $\ell_1$ norm of $x$ (equivalent to $e^T x$ for non-negative $x$) subject to $Ax = b$ and the box constraint $0 \le x \le 1$.
A key theoretical contribution of this work is the mapping of algebraic uniqueness to discrete geometry. The authors prove that the binary solution is uniquely recovered if and only if a hyperplane through the origin can strictly separate the columns of $A$ corresponding to the zeros in $x$ from those corresponding to the ones. For matrices with columns drawn from exchangeable distributions, the probability of successful recovery is shown to be proportional to the expected number of $k$-sets in a random point cloud in $\mathbb{R}^m$.
Empirical Results and the Phase Transition Conjecture
Through extensive Monte-Carlo simulations on synthetic datasets, the authors identify a sharp phase transition in recovery performance. As shown in Figure 1, the number of measurements $m$ required for a 50% success rate closely follows a curve defined by the binary entropy function.
Specifically, the authors conjecture that for large $n$, the LP exactly recovers the binary $k$-sparse solution if $m > nH(k/n)/2$, where $H$ is the binary entropy function. This threshold is significantly lower than the standard compressed sensing bound of $k \log_2(n/k)$ for sparsity ratios $\eta = k/n < 0.5$, demonstrating that the box constraint $0 \le x \le 1$ effectively exploits the binary nature of the signal.
Further analysis of the phase transition, depicted in Figure 2, reveals that the boundary between failure and success becomes increasingly sharp as the system size grows. The figure also highlights the performance gains of the proposed LP formulation over standard non-negative relaxations.
Conclusion
This work bridges compressive sensing and computational geometry through the $k$-set problem. While the proposed phase transition formula remains a conjecture due to the long-standing open nature of the $k$-set problem in geometry, the empirical evidence strongly supports its validity. Future research will focus on formalizing this proof and extending the framework to handle noisy measurements typical of real-world smart grid environments.
Summary updated