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 1-bit compressed sensing framework enables the recovery of a sparse
vector x from the sign information of each entry of its linear transformation.
Discarding the amplitude information can significantly reduce the amount of
data, which is highly beneficial in practical applications. In this paper, we
present a Bayesian approach to signal reconstruction for 1-bit compressed
sensing, and analyze its typical performance using statistical mechanics.
Utilizing the replica method, we show that the Bayesian approach enables better
reconstruction than the L1-norm minimization approach, asymptotically
saturating the performance obtained when the non-zero entries positions of the
signal are known. We also test a message passing algorithm for signal
reconstruction on the basis of belief propagation. The results of numerical
experiments are consistent with those of the theoretical analysis.

本文提出了一种贝叶斯方法来解决 1 比特压缩感知问题的信号重建，并使用统计力学分析了其性能。其中，利用信念传播算法进行信号重建的数值实验结果与理论分析结果一致。

用贝叶斯方法对一位压缩感知进行信号重建

Bayesian signal reconstruction for 1-bit compressed sensing

Compressed sensing is a technique for recovering a high-dimensional signal
from lower-dimensional data, whose components represent partial information
about the signal, utilizing prior knowledge on the sparsity of the signal. For
further reducing the data size of the compressed expression, a scheme to
recover the original signal utilizing only the sign of each entry of the
linearly transformed vector was recently proposed. This approach is often
termed the 1-bit compressed sensing. Here we analyze the typical performance of
an L1-norm based signal recovery scheme for the 1-bit compressed sensing using
statistical mechanics methods. We show that the signal recovery performance
predicted by the replica method under the replica symmetric ansatz, which turns
out to be locally unstable for modes breaking the replica symmetry, is in a
good consistency with experimental results of an approximate recovery algorithm
developed earlier. This suggests that the L1-based recovery problem typically
has many local optima of a similar recovery accuracy, which can be achieved by
the approximate algorithm. We also develop another approximate recovery
algorithm inspired by the cavity method. Numerical experiments show that when
the density of nonzero entries in the original signal is relatively large the
new algorithm offers better performance than the abovementioned scheme and does
so with a lower computational cost.

本文采用统计力学方法分析了基于 L1 范数的信号恢复方案在 1 比特压缩感知中的应用，发现该方案通常具有许多相似恢复准确度的局部最优解，并提出了借鉴空洞方法的近似恢复算法。数值实验表明，在非零元素密度相对较大的情况下，所提出的算法比已有方案具有更好的性能和更低的计算成本。