Support Recovery in 1-Bit Compressed Sensing with Burst Sparse Noise

Abstract

1-bit compressed sensing (1bCS) is a quantized signal acquisition technique to compress high-dimensional sparse signals. The goal is to design sensing matrices A ∈ ℝ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m×n</sup> with the fewest possible rows that enable efficient and accurate recovery of sparse signals x ∈ ℝ<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> from 1-bit measurements of the form sign(Ax). This work focuses on recovering the support of sparse signals from noisy 1-bit measurements, specifically in presence of adversarial noise. Existing methods handle random noise, or small number of adversarial sign flips. We demonstrate that exact support recovery is impossible when a constant fraction of measurements are affected by adversarial noise. Hence, we design sensing matrices that can reliably recover support in presence of (b, c)-burst noise, tolerating a constant fraction of errors concentrated in O(log m) blocks.