Support Recovery in Universal One-bit Compressed Sensing

One-bit compressed sensing (1bCS) is an extreme-quantized signal acquisition method that has been intermittently 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). The extreme quantization makes it an interesting case study of the more general single-index or generalized linear models. At the same time it can also be thought of as a `design' version of learning a binary linear classifier or halfspace-learning. Assuming the original signal vector to be sparse, existing results in 1bCS either aim to find the support of the vector, or approximate the signal within an ε-ball. The focus of this paper is support recovery, which often also computationally facilitate 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 tildeTheta(k2) 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 tildeO(k3/2) measurements. If the dynamic range of the signal vector is known, then with a different technique, this result can be improved to only tildeO(k) measurements. Other results on universal but approximate support recovery are also provided in this paper. All of our main recovery algorithms are simple and polynomial-time.