1. Improved Support Recovery in Universal 1-bit Compressed Sensing
- Author
-
Matsumoto, Namiko, Mazumdar, Arya, and Pal, Soumyabrata
- Abstract
One-bit compressed sensing (1bCS) is an extremely quantized signal acquisition method that has been proposed and studied rigorously 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 allowing a small error. 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
$\tilde {\Theta }(k^{2})~1$ $k$ $\epsilon >0$ $\epsilon $ $\tilde {O}(k/\epsilon )$ $\tilde {O}(\max \{k/\epsilon ,k^{3/2}\}) ^{^{^{^{}}}}$ $\Omega (k/\epsilon )$ $\tilde {O}(k/\epsilon )$ - Published
- 2024
- Full Text
- View/download PDF