Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations

T. S. Jayram, Soumitra Pal, Vijay AryaarXiv 2011 · arXiv

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.

Recovery thresholds for various LP methods compared against the binary entropy function and standard compressed sensing bounds.

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.

Phase transition behavior showing the relationship between measurement rate and sparsity for different success thresholds.

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

Abstract

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.
BibTeX
@misc{jayram2011recovery,
  author = {T. S. Jayram and Soumitra Pal and Vijay Arya},
  title = {{Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations}},
  year = {2011},
  eprint = {1112.1757},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1112.1757},
}
Figure