Robust 1-bit Compressed Sensing with Iterative Hard Thresholding
Namiko Matsumoto Arya Mazumdar
In 1-bit compressed sensing, the aim is to estimate a $k$-sparse unit vector
$x\in S^{n-1}$ within an $\epsilon$ error (in $\ell_2$) from minimal number of
linear measurements that are quantized to just their signs, i.e., from
measurements of the form $y = \mathrm{Sign}(\langle a, x\rangle).$ In this
paper, we study a noisy version where a fraction of the measurements can be
flipped, potentially by an adversary. In particular, we analyze the Binary
Iterative Hard Thresholding (BIHT) algorithm, a proximal gradient descent on a
properly defined loss function used for 1-bit compressed sensing, in this noisy
setting. It is known from recent results that, with
$\tilde{O}(\frac{k}{\epsilon})$ noiseless measurements, BIHT provides an
estimate within $\epsilon$ error. This result is optimal and universal, meaning
one set of measurements work for all sparse vectors. In this paper, we show
that BIHT also provides better results than all known methods for the noisy
setting. We show that when up to $\tau$-fraction of the sign measurements are
incorrect (adversarial error), with the same number of measurements as before,
BIHT agnostically provides an estimate of $x$ within an
$\tilde{O}(\epsilon+\tau)$ error, maintaining the universality of measurements.
This establishes stability of iterative hard thresholding in the presence of
measurement error. To obtain the result, we use the restricted approximate
invertibility of Gaussian matrices, as well as a tight analysis of the
high-dimensional geometry of the adversarially corrupted measurements.