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

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\mathrm{/}k\in [0.4,5.0]$ as the sparsity ratio $s=k\mathrm{/}n$ decreases from $0.5$ to $0.1$, by practically targeting the undersampled regime.