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.

研究了在有噪声的情况下通过最小数量的线性测量以及量化后的符号来估计稀疏单位向量，证明了 Binary Iterative Hard Thresholding 算法在这种情况下提供了比所有已知方法更好的结果，实现了迭代硬阈值法在存在测量误差下的稳定性。

迭代硬阈值稳健的 1 位压缩感知

Robust 1-bit Compressed Sensing with Iterative Hard Thresholding

The Compressive Sensing (CS) framework aims to ease the burden on
analog-to-digital converters (ADCs) by reducing the sampling rate required to
acquire and stably recover sparse signals. Practical ADCs not only sample but
also quantize each measurement to a finite number of bits; moreover, there is
an inverse relationship between the achievable sampling rate and the bit depth.
In this paper, we investigate an alternative CS approach that shifts the
emphasis from the sampling rate to the number of bits per measurement. In
particular, we explore the extreme case of 1-bit CS measurements, which capture
just their sign. Our results come in two flavors. First, we consider ideal
reconstruction from noiseless 1-bit measurements and provide a lower bound on
the best achievable reconstruction error. We also demonstrate that i.i.d.
random Gaussian matrices describe measurement mappings achieving, with
overwhelming probability, nearly optimal error decay. Next, we consider
reconstruction robustness to measurement errors and noise and introduce the
Binary $\epsilon$-Stable Embedding (B$\epsilon$SE) property, which
characterizes the robustness measurement process to sign changes. We show the
same class of matrices that provide almost optimal noiseless performance also
enable such a robust mapping. On the practical side, we introduce the Binary
Iterative Hard Thresholding (BIHT) algorithm for signal reconstruction from
1-bit measurements that offers state-of-the-art performance.

该论文研究了利用压缩感知技术来减少模数转换器的采样率，着重探讨了只捕捉信号符号的 1 比特压缩感知技术，提出了能在噪声较小及容易受干扰的情况下实现逆向恢复的二进制 ε- 稳定嵌入特性，并引入了适用于 1 比特采样的算法 —— 二进制迭代硬阈值算法，提高了采样性能。