Binary Signal Recovery in Undersampling: Iterative SDP with Majority Voting and Successive Interference Cancellation

Abstract

Binary compressive sensing (BCS) seeks to recover a $k$-sparse binary vector of length $n$ from $m$ linear measurements. Classical CS guarantees break down for $m<k$ and convex/greedy BCS algorithms with random Gaussian sensing matrices perform poorly. We introduce ISDP-MVSIC, which combines randomized semidefinite programming (SDP) sampling, majority voting (MV) and successive interference cancellation (SIC) across $L\ll n$ stages, wrapped in a residual-cost driven retry loop. The method exposes a tunable complexity--performance trade-off: for $n=100,144$, raising the worst-case complexity ${\mathcal{C}}_{max}$ from $7.9\times 10^9$ to $2.0\times 10^{10}$ enables empirical exact recovery over $m/k\in [0.4,5.0]$ as the sparsity ratio $s=k/n$ decreases from $0.5$ to $0.1$, by practically targeting the undersampled regime.

5 pages, 5 figures, 2 tables