AI summaryⓘ
The authors study Binary Compressive Sensing (BCS), which aims to find a sparse binary vector from fewer measurements than its length. Traditional methods struggle when the number of measurements is less than the sparsity level, and common algorithms with random matrices do not work well. They propose a new approach called ISDP-MVSIC, combining randomized semidefinite programming, majority voting, and successive interference cancellation over a few stages, with a retry mechanism based on residual cost. Their method allows a balance between complexity and performance and shows good recovery results even when measurements are less than the sparsity. They test it for vector lengths 100 and 144, demonstrating effective recovery as sparsity decreases.
Binary Compressive SensingSparse RecoverySemidefinite ProgrammingRandomized AlgorithmsMajority VotingSuccessive Interference CancellationUndersampled RegimeSparsity RatioLinear Measurements
Authors
Ece Abay, Burhan Gulbahar, Fatih Alagoz
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.