One-bit compressed sensing (1bCS) is an extreme-quantized signal acquisition method that has been widely studied in the past decade. In 1bCS, linear samples of a high dimensional signal are quantized to only one bit per sample (sign of the measurement). Assuming the original signal vector to be sparse, existing results either aim to find the support of the vector, or approximate the signal within an $\epsilon$-ball. The focus of this paper is support recovery, which often also computationally facilitates approximate signal recovery. A universal measurement matrix for 1bCS refers to one set of measurements that work for all sparse signals. With universality, it is known that $\tilde{\Theta}(k^2)$ 1bCS measurements are necessary and sufficient for support recovery (where $k$ denotes the sparsity). In this work, we show that it is possible to universally recover the support with a small number of false positives with $\tilde{O}(k^{3/2})$ measurements. If the dynamic range of the signal vector is known, then with a different technique, this result can be improved to only $\tilde{O}(k)$ measurements. Further results on support recovery are also provided.
翻译:1BCS中,高维信号的线性样本被量化为每个样本只有一位数(表示测量量)。假设最初的信号矢量是稀疏的,现有结果或者旨在找到矢量的支持,或者接近以美元计球内的信号。本文的重点是支持恢复,而这往往也计算出接近信号恢复。1BCS的通用测量矩阵是指为所有稀有信号工作而使用的一套测量方法。在普遍性方面,已知 $\tilde\theta}(k ⁇ 2)$ 1BCS 的测量方法对于支持恢复是必要和足够的(美元表示偏差)。在这项工作中,我们表明,如果知道信号矢量的动态范围,然后以不同的技术支持,那么这一结果也只能改进到$\tilde{O}。